Advent of Code 2024, Day 13

This problem is a standard basis transformation from linear algebra. To see this, consider a specialization to one dimension:

\[ P = NA \]

where \(P\) is the prize \(x\)-coordinate, \(A\) is the offset vector of the button and \(N\) is the solution to the number of presses. Solving for \(N\) is trivial:

\[ N = P/A \]

The magic of linear algebra is that the same algebra essentially holds when we move to higher dimensions as well; we just consider division to be multiplication by a matrix inverse.

Here is the full solution:

      n←⊃⊢⍤⌿⌿⎕VFI(⊃⎕NGET'aoc2024-13.txt'0)∩⎕D⍪' '
      ab←(320 2 2)⍴msk⌿n⊣pz←(320 2)⍴n⌿⍨~msk←(≢n)⍴1 1 1 1 0 0
      +⌿(⊢×⊢=⌊)3 1+.×⍉pz⌹⍤1 2⊢(0 2 1)⍉ab

Below, I sketch my thought process:

Typical APL data ingestion starts with a data normalization pass. In this case, the input format is very regular, embedding integers in a pre-defined order, letting us leverage ⎕VFI to precisely extract the numeric data:

      n←⊃⊢⍤⌿⌿⎕VFI(⊃⎕NGET'aoc2024-13.txt'0)∩⎕D⍪' '

This gives us an integer vector that are logically grouped into units of six: the first four integers define the A-B coordinates which provide the \(2\times 2\) basis transformation matrix, and the last two integers, which define coordinates for the prize.

      pz←(320 2)⍴n⌿⍨~msk←(≢n)⍴1 1 1 1 0 0
      ab←(320 2 2)⍴msk⌿n

      3↑ab
75 30
57 75

48 12
20 52

20 86
46 33

      3↑pz
9885 8130
1320 5260
 370  767

Notice the hard-coded numbers: Logically, we have 320 records, each containing a \(2\times 2\) matrix and a \(2\)-element vector. These serve as a nice visual signal that we are only concerned with one-off static data, instead of a more complex problem domain requiring particular kinds of generalization. Specifically, we’re using an inverted table format but storing columns as type-homogenous variables instead of type-homogenous rows in a single array.

After transposing the A-B matrices, our data is nicely normalized such that the solution simply becomes a direct matrix division:

      +⌿(⊢×⊢=⌊)3 1+.×⍉pz⌹⍤1 2⊢(0 2 1)⍉ab

How nice! This is a toy problem, but the utility of data normalization holds true in real systems as well. That is a writeup for another day, however.