Advent of Code 2024 - Day 13

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!

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.

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)

#!/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"

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

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

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

if floor(x) == x and floor(y) == y do
  [trunc(x), trunc(y)]
end

Ah I see @hauleth beat me to this observation! An incident at work kept me from this puzzle until today.

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

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