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

Performance

One reasonable objection is the use of Key (⌸) since it performs a sort, whereas tallying groups membership is sufficient. In fact, a direct tally is completely straightforward if we first convert the quadrant selector pairs into integer ids:

      +/(∪g)∘.=g←2 2⊥⍉q

Notice that this performs ≢∪q reductions over q, giving it \(\mathcal{O}(\)(≢q)×≢∪q\()\) complexity. On the other hand, the Key solution performs a radix sort over the keys q, resulting in the exact same complexity!

That said, ∘.= over scalar arrays has all kinds of opportunities for SIMD optimizations, making it generally faser than Key, and indeed, comparing the two core expressions bears this out:

      )copy dfns cmpx
      g←2 2⊥⍉q
      cmpx 'q⊢∘≢⌸r' '+/(∪g)∘.=g'
  ×⌿q⊢∘≢⌸r     → 1.5E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ×⌿+/(∪g)∘.=g → 7.9E¯7 | -48% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

However, notice that we bias in favor of ∘.= above by ignoring the overhead of calculating g, which turns out to overwhelm any advantage, making Key come out faster in the overall problem solution here:

      cmpx 'q⊢∘≢⌸r' '+/(∪g)∘.=g←2 2⊥⍉q'
  ⊢∘≢⌸q             → 1.9E¯6 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  +/(∪g)∘.=g←2 2⊥⍉q → 4.2E¯6 | +117% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Acknowledgements

Thank you to Adám for pointing out the potential speedup with ∘.=. Originally, I had a naïve outer product which slowed it down considerably:

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

Even though ∘.{+⌿⍺=⍵} and +/⍺∘.=⍵ are performing the same work, apparently the former expression falls back to a generic implementation of a scalar loop, whereas the latter is a recognized pattern with special optimized code.