You need to check your reached_target? function, the logic there looks wrong.
At the moment your only “don’t win” case is if you reach 100 presses without winning.
2 Likes
Yes, it is the same, but because how the task works, there will be only one way to win each game, so the minimum will be at the same time the only way to win.
Used the same linear algebra approach as other solutions here, though I chose to always keep things as integers until they were confirmed to be exactly divisible.
Also uses Regex.run to parse a whole problem at once.
defmodule TheClaw do
@problem_format ~r/Button A: X\+(\d+), Y\+(\d+)\nButton B: X\+(\d+), Y\+(\d+)\nPrize: X=(\d+), Y=(\d+)/
defstruct [:xa, :xb, :ya, :yb, :x0, :y0]
def read(filename) do
File.read!(filename)
|> String.split("\n\n")
|> Enum.map(&Regex.run(@problem_format, &1, capture: :all_but_first))
|> Enum.map(fn vs -> Enum.map(vs, &String.to_integer/1) end)
|> Enum.map(fn [xa, ya, xb, yb, x0, y0] ->
%__MODULE__{xa: xa, xb: xb, ya: ya, yb: yb, x0: x0, y0: y0}
end)
end
def offset(c, off) do
%{c | x0: c.x0 + off, y0: c.y0 + off}
end
def solution(c) do
discriminant = c.xb*c.ya - c.xa*c.yb
{
discriminant,
c.y0*c.xb - c.x0*c.yb,
c.x0*c.ya - c.y0*c.xa
}
end
def possible?({d, na, nb}) do
rem(na, d) == 0 and rem(nb, d) == 0
end
@cost_a 3
@cost_b 1
def cost({d, na, nb}) do
div(na * @cost_a + nb * @cost_b, d)
end
end
TheClaw.read("input.txt")
|> Enum.map(&TheClaw.offset(&1, 10000000000000))
|> Enum.map(&TheClaw.solution/1)
|> Enum.filter(&TheClaw.possible?/1)
|> Enum.map(&TheClaw.cost/1)
|> Enum.sum()
|> IO.inspect()
1 Like
dam! THANKS! It was just “off by one” issue … removing greater than and using ===
defp reached_target?(
{presses_a, presses_b, _},
{x_inc_a, y_inc_a},
{x_inc_b, y_inc_b},
{target_x, target_y}
) do
current_x = presses_a * x_inc_a + presses_b * x_inc_b
current_y = presses_a * y_inc_a + presses_b * y_inc_b
current_x === target_x and current_y === target_y
end
now i probably will need to go off into the linear algebra territory also …I just hate it when i cant use normal dynamic programming for part1
1 Like
Linear algebra tells us there is at most one solution to this system of equations (that it’s integer division doesn’t play into it). We can solve with a simple application of Cramer’s rule or any equivalent method.
LOC: 13
defmodule Aoc2024.Day13 do
import Enum
def part1(file), do: main(file, 0)
def part2(file), do: main(file, 10_000_000_000_000)
def main(f, z), do: f |> File.read!() |> String.split("\n\n") |> map(&p/1) |> sum_by(&s(&1, z))
@r ~r/Button A: X\+(\d+), Y\+(\d+)\nButton B: X\+(\d+), Y\+(\d+)\nPrize: X=(\d+), Y=(\d+)/
def p(s), do: Regex.scan(@r, s, capture: :all_but_first) |> hd |> map(&String.to_integer/1)
def s([ax, ay, bx, by, px, py], z) do
{d, x, y} = {ax * by - ay * bx, (px + z) * by - bx * (py + z), ax * (py + z) - (px + z) * ay}
if d == 0 or rem(x, d) != 0 or rem(y, d) != 0, do: 0, else: 3 * div(x, d) + div(y, d)
end
end
1 Like
Ah I see @hauleth beat me to this observation! An incident at work kept me from this puzzle until today.
I solved part2 today with the use of linear algebra. But it was a blatant copy paste. I think this and maybe the previous day (12) marks the end of where i can use dynamic programming alone to solve the puzzles. Its a bit sad i had to resort to math, but hey advent of code cant just be Enum.reduce 
i solved myself some cognitive overhead by actually naming the variables to match what the function actually takes in … still doesnt “make sense”, but its easier to following the x’s and y’s i guess …
haha just found the spoiler functionality 
would be REALLY nice actually to avoid scrolling past posts to not get the answer thrown into your face haha …
def solve_machine({{aX, aY}, {bX, bY}, {tX, tY}}) do
x = (bY * tX - bX * tY) / (aX * bY - bX * aY)
y = (aX * tY - aY * tX) / (aX * bY - bX * aY)
if floor(x) == x and floor(y) == y do
[trunc(x), trunc(y)]
end
end
I feel like I just took a college class. It’s been years since I visited linear algebra, but I’m gonna get a book on it cuz this was fun.
3-blue,1-brown’s series on linear algebra explains things in a visual way that makes a lot of sense. Not sure I understood it back in college as well as I had to for solving this problem. Didn’t help that we were forced to do pen/paper solutions. Kept me from seeing “the joy of linear algebra,” so to speak.
I noted down my thoughts as I wrestled with the concepts. If anyone would like to correct or add to my understanding, I’m all ears.
defmodule Day13.Part2 do
@moduledoc """
This puzzle will be solved easier if I understand linear algebra.
After speed-running 3-blue-1-brown's series on the essence of linear algebra
(up to Cramer's rule) and wrestling with the concepts, here's what I've come up with
"""
@a_cost 3
@b_cost 1
@adjustment 10_000_000_000_000
defp parse_machine_args(machine_args) when is_list(machine_args) do
machine_args
|> Enum.reduce(
%{},
fn arg, machine ->
{key, value} = parse_arg(arg)
machine |> Map.put(key, value)
end
)
end
defp parse_arg("Button A: " <> a_vector), do: {:a, parse_point(a_vector)}
defp parse_arg("Button B: " <> b_vector), do: {:b, parse_point(b_vector)}
defp parse_arg("Prize: " <> point) do
{p_x, p_y} = parse_point(point)
{:prize, {p_x + @adjustment, p_y + @adjustment}}
end
defp parse_point("X" <> rest) do
~r/\d+/
|> Regex.scan(rest)
|> List.flatten()
|> Enum.map(&String.to_integer/1)
|> List.to_tuple()
end
defp parse(str) do
str
|> String.split("\n")
|> Stream.chunk_by(&(&1 == ""))
|> Stream.filter(&(&1 != [""]))
|> Enum.map(&parse_machine_args/1)
end
defp determinant_2d([[a, b], [c, d]]) do
a * d - b * c
end
defp min_cost(%{a: {a_x, a_y}, b: {b_x, b_y}, prize: {c_1, c_2}} = _machine) do
# a_xx + b_xy = c_1 <- how many xs from button A + how many xs from button b to reach c_1?
# a_yx + b_yy = c_2 <- how many ys from button A + how many ys from button b to reach c_2?
# 2x2 Square Matrix
# _ _ _ _ _ _
# | a_x b_x || x | | c_1 |
# | a_y b_y || y | = | c_2 |
# - - - - - -
# Target vector
#
# [c_1 c_2]
#
# This 1x2 matrix of constants can be seen as a vector.
# target_vector = [c_1, c_2]
# Free-variable vector
#
# [x y]
#
# This 1x2 matrix of free-variables can be seen as a vector.
# Variable Transform
#
# a_x b_x
# a_y b_y
#
# The variable transform is the matrix of constants that is multiplied by the
# free-variable vector in the matrix-multiplication representation of the linear system.
variable_transform = [[a_x, b_x], [a_y, b_y]]
# Columns
#
# A = [a_x a_y] = i-hat
# B = [b_x b_y] = j-hat
#
# Each column corresponds to the vector described by pressing a given button.
# Basis Vectors
#
# Typically i-hat and j-hat in 2-d vector space. These represent the initial state of
# vector space to which you would like to apply transformations.
# The Determinant
#
# The determinant is a function of a square matrix that tells us a scalar value. This
# value is equivalent to the area of the unit square once transformed by the matrix,
# in relation to some basis vectors. This scalar can be used to determine the scale of
# one matrix/transform in proportion to another.
# Carmine's Rule
#
# Used to evaluate the constituent variables of a linear system when said linear system
# is representable by a square matrix. The square nature of the matrix means that each
# linear equation represents a vector orthogonal to the other n-1 linear equations in
# n-dimensional space.
# When dealing with such a linear system, we can find the values of its constituent
# variables one-at-a-time by finding a ratio of determinants.
# For each n-th variable, the denominator is the determinant of the variable transform.
# For each n-th variable, the numerator is the determinant of the target transform.
# A target transform is the matrix formed by taking the variable transform and replacing
# the n-th column's constants (the vector described by pressing that column's button)
# with the constants from the target vector. I.e. we replace the vector described by
# [n_x n_y] with [c_1 c_2].
target_transform_x = [[c_1, b_x], [c_2, b_y]]
target_transform_y = [[a_x, c_1], [a_y, c_2]]
# x = determinant(target_transform_x)/determinant(variable_transform)
# y = determinant(target_transform_y)/determinant(variable_transform)
# x = by how much do I have to multiply the determinant of the variable transform to reach the determinant of the target x (i-hat) transform?
# y = by how much do I have to multiply the determinant of the variable transform to reach the determinant of the target y (j-hat) transform?
target_determinant_x = determinant_2d(target_transform_x)
target_determinant_y = determinant_2d(target_transform_y)
variable_determinant = determinant_2d(variable_transform)
# For this puzzle, we want to find all integer solutions for x and y, since a button can't be partially pressed.
# If all target determinants are evenly divisible by the variable determinant, we've found an integer solution to the linear system.
# For that reason, we can filter by rem(target_determinant / variable_determinant) == 0 for all target_determinants
# Cases where determinant(variable_transform) is 0 can't be divided, so skip those machines. Visually,
# this would mean that the vector space described by the variable transform already squeezes down to a line or dot (starts out ortholinear?).
if variable_determinant != 0 and
rem(target_determinant_x, variable_determinant) == 0 and
rem(target_determinant_y, variable_determinant) == 0 do
# In the case we've found an integer solution to the linear equation, we've found how many button presses of A and B we need.
# Multiply each by its cost and report their sum to be added to the overarching accumulator
div(target_determinant_x, variable_determinant) * @a_cost +
div(target_determinant_y, variable_determinant) * @b_cost
else
# Add nothing to the accumulator
0
end
end
defp score_min_costs(machines) do
machines
|> Task.async_stream(&min_cost/1)
|> Enum.reduce(0, fn {:ok, min_cost}, acc ->
acc + min_cost
end)
end
def solve() do
File.read!("lib/advent_of_code/year/2024/day/13/input.txt")
|> parse()
|> score_min_costs()
|> IO.puts()
end
end
Here is my solution for Parts 1 & 2 using the equation-solving approach.
I didn’t enjoy this challenge very much, I prefer more algorithmic ones (and I struggled a bit at simplifying my equation 
)
My code (more parsing than solving)
defmodule Advent.Y2024.Day13 do
defmodule Machine do
defstruct [:x, :y, :a, :b, :x1, :x2, :y1, :y2, :prize]
end
def run(puzzle) do
puzzle
|> parse()
|> Enum.map(&solve/1)
|> Enum.map(& &1.prize)
|> Enum.sum()
end
def parse(puzzle, error \\ 0) do
puzzle
|> String.split("\n\n")
|> Enum.map(fn machine ->
[a_btn, b_btn, prize] = String.split(machine, "\n")
[[_, x1, y1]] = Regex.scan(~r/Button A: X\+(\d+), Y\+(\d+)/, a_btn)
[[_, x2, y2]] = Regex.scan(~r/Button B: X\+(\d+), Y\+(\d+)/, b_btn)
[[_, x, y]] = Regex.scan(~r/Prize: X=(\d+), Y=(\d+)/, prize)
%Machine{
x: String.to_integer(x) + error,
y: String.to_integer(y) + error,
x1: String.to_integer(x1),
x2: String.to_integer(x2),
y1: String.to_integer(y1),
y2: String.to_integer(y2)
}
end)
end
def solve(m = %Machine{x: x, y: y, x1: x1, x2: x2, y1: y1, y2: y2}) do
a = (y - y2 / x2 * x) / (y1 - y2 * x1 / x2)
b = (x - a * x1) / x2
if Float.round(a, 3) == round(a) and Float.round(b, 3) == round(b) do
%Machine{m | a: round(a), b: round(b), prize: round(3 * a + b)}
else
%Machine{m | prize: 0}
end
end
end
#!/usr/bin/env elixir
# AoC 2024. day 13.
Mix.install([
{:nx, "~> 0.9.2"}
])
to_i = &String.to_integer/1
###########################################################
# Part 1
start = System.monotonic_time(:microsecond)
File.stream!("../day13.txt")
|> Stream.map(fn line -> Regex.run(~r/^(?:Button (A|B): X\+(\d+), Y\+(\d+))|(?:Prize: X=(\d+), Y=(\d+)$)/, line, capture: :all_but_first) end)
|> Enum.reduce({[], %{}}, fn
nil, {lst, curr} -> {[curr | lst], %{}}
["", "", "", n1, n2], {lst, curr} -> {lst, Map.put(curr, :prize, {to_i.(n1), to_i.(n2)})}
[what, n1, n2], {lst, curr} -> {lst, Map.put(curr, String.to_atom(String.downcase(what)), {to_i.(n1), to_i.(n2)})}
end)
|> then(fn {lst, curr} -> Enum.map([curr | lst], fn %{a: {ax,ay}, b: {bx,by}, prize: {x,y}} ->
Nx.LinAlg.solve(Nx.tensor([[ax, bx], [ay, by]], type: {:f, 64}), Nx.tensor([x, y], type: {:f, 64}))
|> Nx.round()
|> Nx.as_type(:s64)
|> Nx.to_list()
|> then(fn [a,b] ->
if a*ax+b*bx==x && a*ay+b*by==y do
[a,b]
else
[-1,-1]
end
end)
end) end)
|> Enum.filter(fn [a,b] -> a >= 0 && b >= 0 && a <= 100 && b <= 100 end)
|> Enum.map(fn [a,b] -> a*3+b end)
|> Enum.sum()
|> IO.inspect(label: "Part 1")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"
###########################################################
# Part 2
start = System.monotonic_time(:microsecond)
File.stream!("../day13.txt")
|> Stream.map(fn line -> Regex.run(~r/^(?:Button (A|B): X\+(\d+), Y\+(\d+))|(?:Prize: X=(\d+), Y=(\d+)$)/, line, capture: :all_but_first) end)
|> Enum.reduce({[], %{}}, fn
nil, {lst, curr} -> {[curr | lst], %{}}
["", "", "", n1, n2], {lst, curr} -> {lst, Map.put(curr, :prize, {to_i.(n1)+10000000000000, to_i.(n2)+10000000000000})}
[what, n1, n2], {lst, curr} -> {lst, Map.put(curr, String.to_atom(String.downcase(what)), {to_i.(n1), to_i.(n2)})}
end)
|> then(fn {lst, curr} -> Enum.map([curr | lst], fn %{a: {ax,ay}, b: {bx,by}, prize: {x,y}} ->
Nx.LinAlg.solve(Nx.tensor([[ax, bx], [ay, by]], type: {:f, 64}), Nx.tensor([x, y], type: {:f, 64}))
|> Nx.round()
|> Nx.as_type(:s64)
|> Nx.to_list()
|> then(fn [a,b] ->
if a*ax+b*bx==x && a*ay+b*by==y do
[a,b]
else
[-1,-1]
end
end)
end) end)
|> Enum.filter(fn [a,b] -> a >= 0 && b >= 0 end)
|> Enum.map(fn [a,b] -> a*3+b end)
|> Enum.sum()
|> IO.inspect(label: "Part 2")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"
Man that’s elegant. I tried similar but with float operations and conditions and such… complications and of course it didn’t work out for part 2; although I got correct results for part 1 input data. 
Anyway, I’ll try to sear this into my memory:
Solve the following equation system for integers (with integers)
1 Like
Thought about rewriting part 1 to use Cramer’s rule like part 2 does but I quite like my comprehension use, actually, even if it’s not terribly efficient (part 2 finishes faster than part 1 lol). And no, I didn’t know Cramer’s rule. Reddit to the rescue again. I like it when I learn something new. Or something I may have known 30 years ago and forgot all about since linear algebra is not exactly prominent in my day to day life.
defmodule Day13 do
@re ~r/(?<=[A|B|Prize][:|=] X[\+|\=])(\d*).*(?<=^|Y[\+|\=])(\d*)/
@real File.read!(__DIR__ <> "/input.txt") |> String.trim()
def run(input \\ @real) do
data =
input
|> parse()
:timer.tc(fn -> solve_1(data) end) |> IO.inspect(label: :part_1)
:timer.tc(fn -> solve_2(data) end) |> IO.inspect(label: :part_2)
end
defp parse(input) do
input
|> String.split("\n\n", trim: true)
|> Enum.map(fn machine -> Regex.scan(@re, machine) end)
|> Enum.map(fn machine ->
machine |> Enum.map(fn line -> line |> tl() |> Enum.map(&String.to_integer/1) end)
end)
end
defp solve_1(machines, limit \\ 100) do
machines
|> Task.async_stream(fn machine -> calc_min_cost(machine, limit) end, timeout: 10_000_000)
|> Enum.filter(fn {:ok, cost} -> is_integer(cost) end)
|> Enum.sum_by(&elem(&1, 1))
end
@doc """
[[ax, ay],[bx,by],[px,py]] = machine
A * ax + B * bx == px AND A * ay + B * by == py
solve for all values of A and B
get_b = fn a -> (px + py - a * (ax + ay)) / (bx + by) end
"""
def calc_min_cost([[ax, ay], [bx, by], [px, py]], limit) do
max_moves_a = min(div(px, ax), div(py, ay))
max_moves_b = min(div(px, bx), div(py, by))
for a <- 0..min(limit, max_moves_a),
b <- 0..min(limit, max_moves_b),
a * ax + b * bx == px,
a * ay + b * by == py,
reduce: :infinity do
acc -> min(3 * a + b, acc)
end
end
defp solve_2(machines) do
machines
|> Enum.map(fn [axay, bxby, [px, py]] ->
[axay, bxby, [px + 10_000_000_000_000, py + 10_000_000_000_000]]
end)
|> Enum.map(&cramers_rule/1)
|> Enum.filter(&is_integer/1)
|> Enum.sum()
end
defp cramers_rule([[ax, ay], [bx, by], [px, py]]) do
a = div(px * by - py * bx, ax * by - ay * bx)
b = div(py * ax - px * ay, ax * by - ay * bx)
if a * ax + b * bx == px and a * ay + b * by == py do
3 * a + b
else
:infinity
end
end
end
I also finally decided to structure this day with the test data as an actual test that is run with mix test. Rather than running it as a script I’m compiling it and running from iex with iex -S mix and then calling the Day13.run function from there.
What is this pattern matching wizardry:
<<ax::2-binary>> <> ", Y+" <> <<ay::2-binary>>
Also your explanation of the linear algebra concepts is fantastic. Thanks for sharing!
1 Like
