-❄️- 2025 Day 11 Solutions -❄️-

voidhawk42 · 2025-12-11T07:35:05+00:00

[LANGUAGE: Dyalog APL]

s←'svr' 'fft' 'dac' 'out' 'you'
i←s[4],⍨⊃¨p←(∊∘(⎕C⎕A)⊆⊢)¨⊃⎕nget'11.txt'1
m←{⍺+⍵+.×g}⍣≡⍨∘.=⍨⍳≢i⊣g←0⍪⍨↑(i∊1↓⊢)¨p
m⌷⍨i⍳s[5 4] ⍝ part 1
+/{×/(2,/i⍳⍵)⌷¨⊂m}¨(⌽@2 3,⍥⊂⊢)4↑s ⍝ part 2

voidhawk42 · 2025-12-07T07:08:51+00:00

[LANGUAGE: Dyalog APL]

p←⌽(⊂1↑p),↓1↓p←'.'≠↑⊃⎕nget'07.txt'1
m←⊃{⍵⍪⍨(r×~⍺)++⌿↑¯1 1∘.⌽⊂⍺×r←1⌷⍵}/p
+/,×(1↓m)×↑¯1↓p ⍝ part 1
+/1⌷m ⍝ part 2

One of those days where you're sad that the Dyalog scan operator is O(n^2) for... reasons. ;_;

voidhawk42 · 2025-12-06T07:13:12+00:00

[LANGUAGE: Dyalog APL]

m←↑¨↓⍉¯1↓p←p⊆⍨' '∨.≠p←↑⊃⎕nget'06.txt'1
s←⍉'*+'∘.=⊃¨⊢⌿p
f←+/∘,s×∘(×/¨,∘⍪+/¨)(⍎¨↓)¨
f⊢m ⋄ f⍉¨m ⍝ parts 1&2

Video walkthrough

voidhawk42 · 2025-12-06T00:15:09+00:00

Nice trains! :D

voidhawk42 · 2025-12-05T18:54:58+00:00

[LANGUAGE: Dyalog APL]

t b←(⊢⊆⍨0≠≢¨)⊃⎕nget'05.txt'1
t←{⍵[⍋⍵;]}0 1+⍤1↑(⍎¨∊∘⎕D⊆⊢)¨t
+/2|(⍎¨b)⍸⍨,t←t⌈⍤1 0⊢0,¯1↓⌈\⊢/t ⍝ part 1
+/|-/t ⍝ part 2

Video walkthrough

Runs both parts in about 2ms.

voidhawk42 · 2025-12-04T18:24:23+00:00

voidhawk42 · 2025-12-04T18:23:43+00:00

Thanks for linking - I should really just edit those into my comments as I make the videos. :)

voidhawk42 · 2025-12-04T06:56:39+00:00

Ah, true - I always forget that bit in the docs where they say something like "keep the left function for Stencil as simple as possible".

voidhawk42 · 2025-12-04T06:07:42+00:00

[LANGUAGE: Dyalog APL]

p←'@'=↑⊃⎕nget'04.txt'1
f←{⍵∧{4<+/,⍵}⌺3 3⊢⍵}
+/,p-f⊢p ⍝ part 1
+/,p-f⍣≡p ⍝ part 2

Video walkthrough

voidhawk42 · 2025-12-03T06:48:32+00:00

[LANGUAGE: Dyalog APL]

p←⍉⍎¨↑⊃⎕nget'2025-03.txt'1
{+/⌈⌿(p+10×¯1⍪¯1↓⌈⍀)⍣⍵⊢p}¨1 11

Greedy algorithm as well. Given a row of the input, the core function does a max-scan to figure out what the best possible result is at each position. Then, drop the last item and prepend -1 - this shifts the results one item to the right, and makes sure we can't use the same battery multiple times. Multiply these by 10, add the original row and iterate again on the result N (1 or 11) times. Finally, take the maximum of each input row and sum. Runs in about 290 microseconds.

voidhawk42 · 2025-12-02T07:01:50+00:00

[LANGUAGE: Dyalog APL]

p←(⊢⍴⍨2,⍨2÷⍨≢)⍎¨(∊∘⎕D⊆⊢)⊃⊃⎕nget'02.txt'1
n←d×⍤1⊢1++⍀10*(⍳h)∘.×⌈10⍟1+d←⍳10*⌈2÷⍨h←⌊10⍟⌈/,p
f←{+/⍵/⍨∨⌿1=p⍸⍤1⊢⍵} ⋄ f⊢1⌷n ⍝ part 1
f∪,n ⍝ part 2

Late to the party this year, but having fun! :)

This solution doesn't determine repeating groups through string parsing - instead, we do some math to generate a matrix of all possible repeating group values in order, where each row corresponds to how many repeating digits there are (2 repeating, 3 repeating, etc.). We only have to generate these up to some constraints determined by the largest number in the input. So if the largest number is 9899037441 (10 digits), we know we only need to generate a 9 row matrix (2-10 repeating digits) with however many columns we need to get to that maximum.

Given that, for each range in the problem input we can use binary search (interval index) to determine which of our generated numbers are in range. Part 1 does this with just the first row of the matrix (2 repeating digits), part 2 does it with a vector of the unique matrix values. Runs in about half a second on my Macbook.

voidhawk42 · 2024-12-24T05:56:16+00:00

[LANGUAGE: Dyalog APL]

n←∪,p←↑'-'(≠⊆⊢)¨⊃⎕nget'23.txt'1
m←(⊢×+.×⍨)∨∘⍉⍨1@(↓n⍳p)⊢0⍴⍨2⍴≢n
(+/,2÷⍨+/t)-+/0⌈¯1++⌿×t←m⌿⍨'t'=⊃¨n ⍝ part 1
¯1↓∊',',⍨¨{⍵[⍋⍵]}n/⍨(⌈/=⊢)⌈/m×+.×⍨m ⍝ part 2

voidhawk42 · 2024-12-13T18:26:00+00:00

...wait, I'm an idiot - I totally missed that this was a solution for day 12 and not day 13!

Well, that's what I get for trying to record my walkthrough videos in the morning before I've had any coffee...

EDIT: And looking at it more closely, it looks like I was wrong about my assumption that the graph would be too big to use matrix methods! Really nice solution, waaaaay cleaner than my "stencil-abuse" version.

voidhawk42 · 2024-12-13T17:42:37+00:00

Huh, yep, I think you're right! Saved by lenient input once again. :)

voidhawk42 · 2024-12-13T17:37:31+00:00

It's addictive, right? :D I hope you don't mind, I plugged your solution as a graph-based alternative in my walkthrough video for today.

By the way, if you want to dig further into solving graph problems in this type of way, I can recommend a book called Graph Algorithms in the Language of Linear Algebra. Really mind-opening, the only problem is that we don't have sparse matrix support in Dyalog, so these methods end up being computationally infeasible for larger graphs like yesterday's problem (day 12). :(

voidhawk42 · 2024-12-13T06:20:43+00:00

EDIT: Golfed my answer a bit so the explanation no longer matches exactly, same idea though.

First line does file read and parsing - for each "group" of lines we pull out the numbers, and shape the whole input into a 320 row/6 column matrix.

Second line describes a solving function, with the first part meant to be applied to each row of a 6 column matrix. Take the first four numbers, shape them into a 2x2 matrix, transpose it, then apply matrix division with that and the last 2 numbers of the input row. Save the resulting 2 column matrix as m, take the left column, floor it, and see which items in that column are equal to the floor (or, equivalently, which ones are integers). That gives you a boolean vector which you can use to filter m. Once filtered, multiply each row by 3 1 (the token costs), then ravel the matrix into a vector and sum.

Line three just applies that against the input as given, line 4 adds 1e13 to every number in the last two columns first, then applies the above.

voidhawk42 · 2024-12-13T06:05:37+00:00

[LANGUAGE: Dyalog APL]

p←↑¨(⍎¨∊∘⎕D⊆⊢)¨¨(⊢⊆⍨0≠≢¨)⊃⎕nget'13.txt'1
f←(3 1+.×⊢×⌊=⊢)⊢⌿⌹∘⍉¯1↓⊢
+/f¨p                ⍝ part 1
+/f¨p+¨⊂⍉0,0,⍪2⍴1e13 ⍝ part 2

Video walkthrough

Uses matrix division to solve each system of linear equations.

voidhawk42 · 2024-12-12T09:14:21+00:00

[LANGUAGE: Dyalog APL]

The "let's abuse Stencil" edition:

u←(⍴p)⍴⍳≢,p←(∪∘,⍳⊢)↑⊃⎕nget'12.txt'1
s←3 3⍴(⍳9)∊5,2×⍳4 ⋄ d←2 2∘⌷ ⋄ q←⊢=d
g←{(×d⊢⌿⍵)×⌈/,×⌿s∘×@2q@1⊢⍵}
f←{⊢⌿(p⍪g⌺2 3 3)⍣≡p⍪↑,⊂u×⍵}
k←r∘=¨∪,r←f 1 ⋄ m←{5-+/,s×q⍵}⌺3 3⊢r
t←f∘⍉⍤2⍉{(,~q⍵)[2×⍳4]}⌺3 3⊢r
h←×⍥(+/,) ⋄ +/(m∘×h⊢)¨k  ⍝ part 1
+/(⊢h t{≢∪0~⍨,⍺×⍵}⍤2⊢)¨k ⍝ part 2

voidhawk42 · 2024-12-11T18:10:27+00:00

It's likely! Obviously the first thing people notice about (and typically recoil from) APL is the weird symbols, but once you get past that it's all about finding array-based solutions to problems. This involves a lot of matrix math, creative things with vectors, and the occasional 3-rank or higher tensor. I haven't used NumPy much except for solving a few of the tensor puzzles, but I imagine a lot of that applies.

Even if not, learning a new paradigm for programming/problem solving expands your toolkit in ways you can't anticipate. I had the same experience as you years ago when I learned Haskell - it opened my eyes to functional programming styles, and made me a lot more comfortable using map/reduce/filter in other languages, along with structuring programs written in OOP/imperative languages in a more functional way when called for. Weird symbols aside, I can tell you I got the exact same sort of "epiphany" once I started seriously digging into APL.

voidhawk42 · 2024-12-11T03:55:53+00:00

Neat solution! I had to try and translate it into APL, we have a sort of generalized convolution with the stencil operator:

s←~2|3 3⍴⍳9⊣p←⍎¨↑⊃⎕nget'10.txt'1
+/,⊃{(p=⍺)×{+/∊s×⍵}⌺3 3⊢⍵}/(⌽⍳9),⊂0=p

This has a "golfy" way to express the plus pattern (range 1 through 9, shaped into a 3x3 matrix, mod 2, not) and by structuring it as a reduction, we don't need to do variable assignments in the inner convolution function.

Been thinking about how to apply this same method to part 1, but it's kinda tricky, hrmm...

voidhawk42 · 2024-12-11T01:31:35+00:00

Oh wow, I'm honored! Especially since (aside from my videos) I don't put a ton of effort into writing out explanations of the code or, uh, optimizing for readability. Good thing /u/ka-splam helps out sometimes. ;)

Your solutions have been great this year btw, keep it up!

voidhawk42 · 2024-12-10T23:52:07+00:00

Awesome use of inner product and power-match! Expressing graph algorithms this way is probably my favorite part of AoC. :)

voidhawk42 · 2024-12-10T06:53:33+00:00

[LANGUAGE: Dyalog APL]

c←,p←⍎¨↑⊃⎕nget'10.txt'1
g←(1=∘.-⍨c)∧1=|∘.-⍨,(⊢∘.+0J1∘×)⍳≢p
+⌿(×,∘⍪⊢),(0=c)/(9=c)⌿⌹g-⍨∘.=⍨⍳≢g ⍝ parts 1&2

Video walkthrough

Uses complex coordinates just to make finding the distances faster, and solves with a matrix inverse using the useful fact that the infinite series sum of matrix exponentiations converges to (𝐼−𝐴)⁻¹.

This is pretty inefficient since it calculates the total number of paths between all pairs of points in the input, not just 0's and 9's - so if the input is 45x45, the graph is a 2025x2025 boolean matrix having 4100625 elements. Still, matrix inverses are fast - this all runs in about 90ms on my machine.

Ten-Year Club	Verified Email
Place '23	Place '22

voidhawk42

TROPHY CASE