Advent of Code 2024 - Day 13

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!

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day13.ex

(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.

https://github.com/jbonet/advent_of_code_2024/blob/main/lib/advent_of_code_2024/days/13.ex

https://github.com/bjorng/advent-of-code/blob/main/2024/day13/lib/day13.ex

Ahh, solving simul equations using matrix math. Solved Part 1 that way, so Part 2 didn’t require any code.

https://github.com/rvnash/aoc2024/blob/main/lib/d13.ex

Solved w/ Nx:
https://gitea.codingthemsoftly.com/caleb/advent_of_code/src/branch/main/elixir/livebook/2024/day13.livemd

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.