I wrote the simple algebraic solution that Part 2 needed first, but assumed it was going to miss the cheapest solution if there were multiple, so I ran an exhaustive search to solve Part 1.
That was obviously not going to be suitable for Part 2 so I went back to see how much massageing it was going to need, and the answer was None!
def parse(input) do
input
|> String.split("\n", trim: true)
|> Enum.chunk_every(3)
|> Enum.map(fn [a, b, p] ->
[ax, ay] =
String.split(a, ["Button A: X+", ", Y+"], trim: true) |> Enum.map(&String.to_integer/1)
[bx, by] =
String.split(b, ["Button B: X+", ", Y+"], trim: true) |> Enum.map(&String.to_integer/1)
[px, py] =
String.split(p, ["Prize: X=", ", Y="], trim: true) |> Enum.map(&String.to_integer/1)
{{ax, ay}, {bx, by}, {px, py}}
end)
end
def part1(input) do
input
|> parse()
|> Enum.map(fn {{ax, ay}, {bx, by}, {px, py}} ->
na = div(by * px - bx * py, by * ax - bx * ay)
nb = div(ay * px - ax * py, ay * bx - ax * by)
x = na * ax + nb * bx
y = na * ay + nb * by
if x == px and y == py do
3 * na + nb
else
0
end
end)
|> Enum.sum()
end
@scale 10_000_000_000_000
def part2(input) do
input
|> parse()
|> Enum.map(fn {{ax, ay}, {bx, by}, {px, py}} ->
na = div(by * (px + @scale) - bx * (py + @scale), by * ax - bx * ay)
nb = div(ay * (px + @scale) - ax * (py + @scale), ay * bx - ax * by)
x = na * ax + nb * bx
y = na * ay + nb * by
if x == px + @scale and y == py + @scale do
3 * na + nb
else
0
end
end)
|> Enum.sum()
end
You ever have those days where your brain forgets how to brain? That was today.
I looked at the problem, realized pretty quickly it was about solving simultaneous equations, and then… totally forgot there are formulas out there for solving generally. So I tried all kinds of things and massively over-complicated the situation. Sigh.
Anyway here’s some code!
(benchmarks are like 753.73 ÎĽs - most of the time is probably in the parsing)
I think, in the end I got a somewhat nice solution.
I solved it like this for Part 1, I thought part2 was going to involve some kind of optimization in the mix, but hey, simple works.
Ahh, solving simul equations using matrix math. Solved Part 1 that way, so Part 2 didn’t require any code.
Solved w/ Nx:
What I don’t understand is why the puzzle master did not include any problems with more than one solution, where we would have to find the one with the lowest cost. In each case, there is only one or zero integer solutions.
One example, if button A moved 1x1 space, and button B moved 2x2, then there are numerous ways to do that for any given position of the prize. And then we would be challenged to use B as often as possible, and then only use A at the end. The matrix math would have failed with a 1/0 error. It would have taken a lot more code for this case.
If I had to guess:
As a puzzle master, it might be better to assume that some (maybe most) of the people solving the puzzle, won’t be familiar with linear algebra. Those unfamiliar will need to write their own algos to find the solution space and writing an algorithm to minimize the cost s.t. both coordinates (e.g., button presses) are positive may be an unwelcome addition of difficulty to the problem.
Solving a 2x2 is a nice little demo of using Nx as an introduction.
Thanks! I was up until 2 a.m. trying to do this by hand following these lectures:
Every time I tried to use these algo’s on paper/pen I didn’t get the write answer, so I gave up and used Nx. 
Edit: Oh! And relevant to your earlier query about systems w/ infinite solns - this may be why. I haven’t done the math myself, but I wonder if such systems will always have some non-integer solutions? If that were the case, then one would need a matrix solver that only gives integer solutions - which would require implementing one of the algos I linked, or finding one prebuilt. I’m not sure how readily available the latter is - it isn’t a feature of Nx.
I think that the infinite solns problems would always have the nature that the two lines described by the rows of the matrices would be parallel. Meaning “they never cross”, hence the determinant is 0. The only way to get a solution, therefore, is if both the X and Y coordinate equations are right on top of each other. So, then you only need to hit as many A’s as you need to to get to an even multiple of B distance, and then use B from then on out. It wouldn’t be hard to solve, sort of a remainder type problem. But that would have added another twist. One twist too many perhaps, as you pointed out.
My solution:
# Parsing
puzzles =
puzzle_input
|> String.split("\n", trim: true)
|> Enum.chunk_every(3)
|> Enum.map(fn machine ->
Enum.map(machine, fn row ->
[[_patternx, x], [_patterny, y]] = Regex.scan(~r/[XY][+=](\d+)/, row)
{String.to_integer(x), String.to_integer(y)}
end)
end)
defmodule ClawContraption do
# ax * x + bx * y = px
# ay * x + by * y = py
def solve([{ax, ay}, {bx, by}, {px, py}]) do
case ax * by - bx * ay do
0 ->
0
determinant ->
num_x = px * by - bx * py
num_y = ax * py - px * ay
if rem(num_x, determinant) == 0 and rem(num_y, determinant) == 0 do
x = div(num_x, determinant)
y = div(num_y, determinant)
{x, y}
else
0
end
end
end
def calculate_cost({x, y}), do: x * 3 + y
def calculate_cost(_result), do: 0
end
# Puzzle 1
Enum.map(puzzles, fn puzzle ->
puzzle
|> ClawContraption.solve()
|> ClawContraption.calculate_cost()
end)
|> Enum.sum()
# Puzzle 2
Enum.map(puzzles, fn puzzle ->
[{ax, ay}, {bx, by}, {px, py}] = puzzle
[{ax, ay}, {bx, by}, {px + 10_000_000_000_000, py + 10_000_000_000_000}]
|> ClawContraption.solve()
|> ClawContraption.calculate_cost()
end)
|> Enum.sum()
Full code:
I liked that you didn’t introduce any floating point math.
Simple Cramer’s rule for solving linear equations, and some small writeup about it.
Love that you have notes in your livemd!
The async stream and the cartesian iteration limit for j were a bit extra, but it works for part 1:
defmodule Day13.Part1 do
@max_presses 100
@a_cost 3
@b_cost 1
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: {:prize, parse_point(point)}
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 treasure_maps(%{a: {x_a, y_a}, b: {x_b, y_b}, prize: {target_x, target_y}} = _machine) do
for i <- 0..@max_presses do
leftover_x = target_x - (x_a * i)
js_that_can_fit_x = div(leftover_x, x_b)
j_limit = min(target_x, js_that_can_fit_x)
leftover_y = target_y - (y_a * i)
js_that_can_fit_y = div(leftover_y, y_b)
j_limit = min(j_limit, js_that_can_fit_y)
j_limit = min(j_limit, @max_presses)
for j <- 0..j_limit do
x_combined = i * x_a + j * x_b
y_combined = i * y_a + j * y_b
{x_combined, y_combined, i, j}
end
|> Enum.filter(fn {x, y, _i, _j} -> x == target_x and y == target_y end)
end
|> Enum.flat_map(& &1)
end
defp min_cost(machine) do
case treasure_maps(machine) do
[] ->
0
hits ->
hits
|> Enum.map(fn {_x, _y, a, b} -> a * @a_cost + b * @b_cost end)
|> Enum.min()
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
Still working on part 2 =]
Oof- yeah, I need to review ~matrices~ linear algebra in general.
Lets hope day 13 is not evil and destroys my brain 
like day12
I got the example input with four machines to work. My code returns 480 for that input
but it seems its returning a false cost for the actual input. Which tells me i need to go back to the drawing board
Nope. Brain failing to understand. IF I understand the requirements correctly, the first example that cost 480 tokens should be a minimal example for the bigger answer. Is that a wrong assumption? I might not able to parse the English in the text, even though I’m pretty fluent.
da code:
Hints?
for ex is this
So, the most prizes you could possibly win is two; the minimum tokens you would have to spend to win all (two) prizes is `480`.
the same as this
Figure out how to win as many prizes as possible. *What is the fewest tokens you would have to spend to win all possible prizes?
