Advent of Code 2024, Day 14

Day 14 is another linear algebra problem with some classification spice thrown on top:

n←¯1↓⊃⊢⍤⌿⌿(', '⍪LF)⎕VFI'¯'@{⍵='-'}(⊃⎕NGET'aoc.txt'0)∩⎕D⍪'-, '⍪LF←⎕UCS 10
p←msk⌿m⊣v←(~msk←1000⍴1 0)⌿m←1000 2⍴n
r←101 103|⍤1⊢p+100×v
×⌿(50 51>⍤1⊢r)⊢∘≢⌸r⊣r⌿⍨←∧/50 51≠⍤1⊢r

The input data is helpfully regular, i.e. all information about integers can be inferred from their index, so we take the standard approach of eliding everything but integers and separators, feeding the result to ⎕VFI:

      ⊢n←¯1↓⊃⊢⍤⌿⌿(', '⍪LF)⎕VFI'¯'@{⍵='-'}(⊃⎕NGET'aoc.txt'0)∩⎕D⍪'-, '⍪LF←⎕UCS 10
67 43 80 86 47 24 ¯9 ¯96 6 38 10 81 73 92 36 ¯93 74 10 ¯35 19 57 59 ¯5 71 ···

We know the integers must encode pairs of position and velocity vectors, which is straightforward to extract:

      p←msk⌿m⊣v←(~msk←1000⍴1 0)⌿m←1000 2⍴n
      5↑p,'|',v
67 43 |  80  86
47 24 |  ¯9 ¯96
 6 38 |  10  81
73 92 |  36 ¯93
74 10 | ¯35  19

Now we get to the meat. Conceptually, we just calculate an affine offset on a torus (i.e. modulo the circumfrences), which is nicely reflected directly in the code:

      5↑r←101 103|⍤1⊢p+100×v
88 94
56  3
97  1
37 62
 8 56

After filtering out the centerline positions, note that identifying quadrants corresponds to a simple bitmask that marks which side of each centerline a position lies.

      q←50 51>⍤1⊢r←r⌿⍨∧/50 51≠⍤1⊢r
      5↑q,'|',r
0 0 | 88 94
0 1 | 56  3
0 1 | 97  1
1 0 | 37 62
1 0 |  8 56

The solution is then just a matter of counting up each quadrant:

×⌿q⊢∘≢⌸r

One reasonable objection is the use of Key (⌸) since it performs a sort, whereas tallying groups membership is sufficient. The latter is just ≢∪q reductions over q, meaning it has \(\mathcal{O}(\)(≢q)×≢∪q\()\) complexity. What about Key? Well, it effectively performs a radix sort over q, giving the same complexity!

In fact, the constant overheads in this case cause the Key solution to win:

      )copy dfns cmpx
      g←2 2⊥⍉q
      cmpx '×⌿q⊢∘≢⌸r' '×⌿(∪g)∘.{+⌿⍺=⍵}⊂g'
  ×⌿q⊢∘≢⌸r          → 1.5E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ×⌿(∪g)∘.{+⌿⍺=⍵}⊂g → 2.0E¯6 | +38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕