Advent of Code 2024 - Day 13Claw Contraption

| Problem statement | Source code | Tags: Mathematics

This problem pays tribute to 2020 day 24.

For each prize, we want to press button A $n_A$ times and button B $n_B$ times, such that $d_{AX} n_A + d_{BX} n_B = p_X$ , $d_{AY} n_A + d_{BY} n_B = p_Y$ . We can rewrite this as a matrix equation:

\begin{bmatrix}d_{AX} & d_{BX} \\ d_{AY} & d_{BY}\end{bmatrix} \begin{bmatrix}n_A \\ n_B\end{bmatrix} = \begin{bmatrix}p_X \\ p_Y\end{bmatrix}

I define a matrix type, based on rationals.

open Q

type mat22 = { a : Q.t; b : Q.t; c : Q.t; d : Q.t }

ocaml

Then I parse my input into a (mat22 * (Q.t * Q.t)) list.

For each prize, I solve it by inverting the matrix:

\begin{aligned} \begin{bmatrix}n_A \\ n_B\end{bmatrix} &= \begin{bmatrix}d_{AX} & d_{BX} \\ d_{AY} & d_{BY}\end{bmatrix}^{-1} \begin{bmatrix}p_X \\ p_Y\end{bmatrix}\\ &= \frac{1}{d_{AX} d_{BY} - d_{AY} d_{BX}} \begin{bmatrix}d_{BY} & -d_{BX} \\ -d_{AY} & d_{AX}\end{bmatrix} \begin{bmatrix}p_X \\ p_Y\end{bmatrix} \end{aligned}

If the inverse doesn't exist, then there are two possibilities: (1) the equations are inconsistent (e.g., nA + nB = 1 and 2nA + 2nB = 3); (2) the equations are degenerate (e.g., nA + nB = 1 and 2nA + 2nB = 2). Now theoretically for the second case, there still remains a relationship between $n_A$ and $n_B$ , which is $d_{AX} n_A + d_{BX} n_B = p_X$ (the other is equivalent to it), which should minimize the cost $3n_A + n_B$ ; however, I found that actually this case never happens in the input, so I just ignore it.

Here's the function for inverting the matrix:

let det { a; b; c; d } = (a * d) - (b * c)

let inv m =
  let d = det m in
  if d = Q.zero then None
  else Some { a = m.d / d; b = -m.b / d; c = -m.c / d; d = m.a / d }

ocaml

And here, for solving one equation:

let solve_lp mat (prize_x, prize_y) =
  match inv mat with
  | None ->
      if mat.a / mat.c = prize_x / prize_y then (
        Printf.printf "LP problem: %s*nA + %s*nB = %s\n" (to_string mat.a)
          (to_string mat.b) (to_string prize_x);
        failwith "Unimplemented")
      else None
  | Some inv_mat ->
      let x = (inv_mat.a * prize_x) + (inv_mat.b * prize_y) in
      let y = (inv_mat.c * prize_x) + (inv_mat.d * prize_y) in
      if
        x >= of_int 0
        && y >= of_int 0
        && Z.equal x.den (Z.of_int 1)
        && Z.equal y.den (Z.of_int 1)
      then Some (x, y)
      else None

ocaml

The cost is straightforward to compute.

let solutions =
  List.filter_map (fun (mat, prize) -> solve_lp mat prize) blocks
in
let total =
  List.map (fun (x, y) -> (of_int 3 * x) + y) solutions
  |> List.fold_left ( + ) (of_int 0)

ocaml

Part 2 just shifts all prizes by 10000000000000, but does not change the above logic at all. It was purely used to shoot down brute-force solutions.