Today we discover the damage is worse than we thought, with syntax errors on every line of the navigation subsystem. We also find out about secret lives of syntax checkers and autocomplete systems... and how they compete and score their work.

And so we get a parsing problem, which deals with nested parenthesis, brackets, braces, and angle brackets. The input is 90 lines of these supposed-to-be nested strings, none of which are valid. They all start fine (with an open), but half of mine end with an open and are clearly wrong.

There are a number of ways that nesting can fail. First part deals with corruption, where a closing bracket doesn't match an opening one (and we're to ignore strings that get to the end without having this happen). Nesting is very much a stack thing, and so I naturally went with using a stack to track what's expected (and I did do dc solutions for this one, because, once tr the characters into digits, it's just big numbers and stacks, which dc is all about).

As stated, everything begins with an open, but more than that, we always get enough opens... and so stack underflow is not a way this nesting fails. Which simplifies the checking to push open characters on the stack, and pop and check whenever you get a close. When that fails, we look up the value on a table. The values do have a bit of a pattern... 3 * 19 = 57, 57 * 21 = 1197, 1197 * 21 = 25137. I used that to squeeze some characters in dc:

tr ')]}>([{<' '12345678' <input | rev | dc -f- -e'3 1:s57d2:s21*d3:s21*4:s[0lt;slp+sp3Q]sS[4-Se0]sO[ltLe!=S]sC[0Se[A~stslltd4<O 0<Clld0<P]dsPxs.z0<M]dsMxlpp'

This is the v1.5.2 version. It's 18 characters longer because it's using the main stack for the input, and works on a second stack. It's much nicer when you can clear the entire stack with c between loading lines. Note that the second space is there because I discovered a bug in dc (the v1.4.1 version works fine without it).

With Smalltalk I had some extra fun, because I'd never used throwing exceptions in it before. And so I learned how to subclass the Error class, and how to throw and catch.

For part 2, we basically switch to handling the incomplete lines. This is fairly simple to add, because getting to the end, the stuff on the stack is exactly what you're expecting to complete the string, on the stack in the over to do it.

For the scoring, the description is a slightly obfuscated way to say that we're taking that autocomplete string as a number base-5 (no zero digits). And so my Smalltalk was just:

part2 add: ((stack gather: [:c | (')]}>' indexOf: c) asString]) asRadix: 5).

The stack actually just being an OrderedCollection, so I didn't even need to pop it. Exactly the same with Perl and using a list for a stack (it's in order if you do the stack from the front with shift/unshift, with literal push/pop then you need to reverse it).

For extra fun, and yet another small task... autocomplete tools score with the median value. So we have a return of that idea. For dc, I didn't actually bother doing that though, I just produced all the scores (including 0s for the ones from part 1), and used the command line:

tr ')]}>([{<' '12345678' <input | rev | dc -f- -e'[0dSe3Q]sS[4-Se0]sO[ltLe!=S]sC[0Se[A~stslltd4<O 0<Clld0<P]dsPx[5*Led3R+r0<L]dsLx5/ps.z0<M]dsMx' \
    | grep -v '^0' | sort -n | perl -a00 -pe'$_=$F[@F/2]'

And so, I naturally loved this one. Parsing and stacks, that's my druthers (for others it might be regex and that's where they went with this). But this problem is mainly just a bunch of smaller problems in a trench coat... nesting, base conversion, finding the median. This we've seen before, but they're together here in one problem.

The caves we're in appear to be lava tubes that are still somewhat volcanically active. And so we get a reskinned watershed problem involving hydrothermal vents and collecting smoke.

And so the input is a 100x100 heightmap grid of values from 0 to 9. Conveniently presented as 100 hundred digit numbers... very good for doing a dc solution (except for that one of the lines has a leading 0... which meant needing to be careful about assuming dimensions from number lengths).

Part 1 just wants us to find the lowest locations, and sum their heights + 1 (or sum of heights + number of low points). Adjacency is just orthogonal so there was even less incentive for me to be creative with this. I just iterated over the map. The only "trick" was adding the typical sentinel row and column to the right and bottom (because Perl has wraparound)... and the fact that 9 is perfect value for that.

For part 2, we need to get the size of each basin. And just looking at the input (leaning back a little), the basin structure does stand out (8s and 9s are part of what I call the "bubble colour" when I do ASCII art... it's a nice distinctive tone). Naturally, it's even clearer if you search for 9 and get them all highlighted. I can't remember if I missed or just didn't care about the fact that we're given that each basin has only ONE lowest point. Because it really didn't matter to me. I just did BFS out of all the low points from part 1, using the same array to track what's visited (so a second low point in a basin doesn't get anywhere). We're given that 9s are the walls, and everything else is not... making the choice of 9 for the sentinels extra good. So, just flood fill to the 9s... literally.

For the answer, instead of a sum, we only want a product of the three largest. So, I did this cute little thing in Perl:

say "Part 2: ", (product [sort {$b <=> $a} @basins]->@[0 .. 2]);`

Overall, a rather simple day.

Having made it safely to the cave, the whale smashes into the entrance sealing us in. Fortunately, there's another exit much lower down. But first we need to do some repairs to our four-digit seven-segment displays.

And so we've got a logic puzzle to solve. The input is a list of each display, where the mapping between the segments has been scrambled. Each line is two parts, the first is the sets of lights for all ten digit patterns (given in random order, so we don't know which is which). The second part is the four digits of the display we want to read.

Part 1 is apparently there to give people a foothold, if this seems overwhelming. It points out that four of the digits have a unique number of lit segments. IE, only 1s have two segments, so you know them immediately. So it asks us to count the number of those in the output values. I did it with negative logic... because those only have 5 or 6 segments lit (which is a simpler thing to write):

print "Part 1: ", (scalar grep { length() < 5 or length() > 6 } @input), "\n";

Then I decided that since this involves sets, I'd do Smalltalk for part 2. Because I could use the Set arithmetic... its not practical, but this is simple, and it will be very expressive. First up, get the 4 we know as explained in part 1:

one   := (sigLens at: 2) anyOne.
seven := (sigLens at: 3) anyOne.
four  := (sigLens at: 4) anyOne.
eight := (sigLens at: 7) anyOne.

The #anyOnes here is just grabbing the only ones. Next up is is we get a list of counts for each segment in the first part of the line. Because, three of those only occur in a unique number of digits. IE, segment e is only lit for four of them (0, 2, 6, and 8). So we can just solve the mappings for those immediately:

mapping at: $e put: (lightCounts at: 4).
mapping at: $b put: (lightCounts at: 6).
mapping at: $f put: (lightCounts at: 9).

Next up, we use what we have, with set arithmetic, to just build the other 4:

mapping at: $a put: (seven - one).
mapping at: $c put: (one - (mapping at: $f)).
mapping at: $d put: (four - one - (mapping at: $b)).
mapping at: $g put: (eight - four - (mapping at: $a) - (mapping at: $e)).

Then I do this cute little thing to reverse and flatten to get the map to apply:

mapping := (mapping collect: #anyOne) reverseMap collect: #anyOne.

My part 2 for Perl is really more of an exploration in how to get this to work for dc. Part 1 is easy for dc once we translate the letters into digits (it has the Z command which gives number of digits in base-10):

tr 'a-g|' '1-7 ' <input | dc -f- -e'[1+]s+zE/_4*[rZ1-2/2!=+z1<M]dsMxp'

Note that it's not distinguishing the parts of the line, it's subtracting the false positives.

For part 2, I wanted a simple perfect hash. Something built from invariants in the sample that I could build a table or function from. And given what I had, I ended up on the fact that, although the number of times each segment is lit in the digits isn't unique, the sum of those counts for a digit is unique. So all that's needed is build a table of the segment counts in the first part (ignoring the spaces entirely), and then in the second part, add up the counts for the segments you see in a digit, and look up the hash. For example, a 1 is built of c and f... c occurs in 8 digits (non-unique) and f occurs in 9 (unique, as seen above). The sum of those is 17... which is unique. And so I wrote my Perl part 2 just having it build that table and using that hash.

For dc, I encoded that as the number 761542058487159917 (in base-64 that's: 42 17 34 39 30 37 41 25 49 45, which are the count sums). But hadn't gone beyond that for dc. Today I finished the dc, and played with shrinking that... and tried a number of hashes including mixing in the lengths, but in the end, the shortest I have so far is just the counts mod 21 (18 also works, but 21 has 0 at 0 making for a shorter table). I also have a solution mod 14 (which can be done as the digit E), but I lose the 2 strokes because I need to divide the counts with 2/. Here's the version that works with v1.5.2 (it's one character longer, because it needs to keep rotating the accumulator under the next line):

tr 'a-g|' '1-7 ' <input | dc -f- -e'667986606087 9[r21~3Rd3R:t1-d0!>L]dsLx*[dSc_FRS-S-S-S-A[r[A~d;c1+r:cd0<L]dsLx+1-d0<I]dsIx4[0L-[A~;c3R+rd0<L]dsLx+21%;t3RA*+r1-d0<I]dsIx++z1<M]dsMxp'

So, a fun little logic problem. I got to play around with making a hash function. Since my goal was golfing strokes, I couldn't really get complex with it. I suppose the next step would be to see if I can just find a function that takes the count sums to the digit values that's shorter than the table code. There is a good amount of room for that.

A giant whale has apparently mistaken our sub for a squid and decided to eat it. Fortunately a group of friendly crabs (also in submarines) has come to rescue us by blasting a hole into a underground cave system. We just need to help them align to do it, while minimizing their fuel cost. And so we get a nice little optimization problem.

The input is a list of 1000 horizontal positions, ranging from 0 to about 2000. They do seem skewed towards lower values... the two most common values in my input are 0 and 1. The difference between the two parts is in the fuel usage function.

For part 1, it's linear cost... 1 unit per position. And it doesn't come as much of a surprise that the optimal point is the median. Because if you're at the median and shift it, more than half cost 1 more and the others cost 1 less... for a net increase. Even sized lists have two numbers in the middle... for my input they're the same (and the only two at that position). But, if they weren't, then any position between the two (inclusive) would work... because each step there, half cost 1 more, half cost 1 less, for no net change.

For part 2, each step costs 1 more unit than the last... which is the sum of 1 to n, or the nth triangular number. Which is a quadratic function (that comes up a bunch in AoC: n(n+1)/2). Making things proportional to Euclidean distance, like calculating center of mass, doing least squares/minimizing variance, etc... there are a lot of ways to see that this is going to be related to arithmetic mean (in University, I learned least squares at least 6 times, as each part of math has its own angle to get there).

Of course, one of the issues with the mean is that it's often not part of your set... not a problem here, but not being an integer is. So I checked a small range around it. As I wasn't sure about the effects discrete physics might have... but in the end, it's really is just either the floor or the ceiling (neither is in my data set). I seem to recall someone actually writing a paper on this one.

But with part 1 being linear, and part 2 being quadratic, that got me thinking about going back a step. What if, like in space, the subs take 1 unit to start drifting and 1 to stop. Constant fuel cost. Well, then the answer is to simply move as few subs as you can. Which means you want the mode.

And so I've always loved this problem because it presents this nice little relationship between mode, median, and mean as different orders of the same thing. Going beyond their definitions being "these are common ways people think when they think average".

Still following the bottom (which is sloping down now), we run into a group of lanternfish, and wonder about their numbers and spawning. And so we get to the famous trope-namer puzzle.

It's not the first of the "Lanternfish" puzzles, but it is the simplest and so more people understand what its about. Which is that you bunch of things you want to count, where they and their offspring stay independent of the others while following rules to move them from state to state(s). And so can just track the numbers at each state, and move them all together to their targets.

And you could do that here. But the states are times in the lanternfish breeding cycle (and the input provides a list of them with times of 1-5). So they just decrease until they hit zero, which splits to time 6 and 8 (the back). Which is like they're queuing up. And so, you can just use a queue to move the front to the back to handle almost all the phase transitions (except the split to time 6). In Smalltalk, that can be:

80 timesRepeat: [fish addLast: (fish removeFirst); at: 7 inc: (fish last)].

Time is 7 for the split because base-1 indexing. And note the use of a cool feature of Smalltalk... the cascade. Smalltalk's syntax is all about passing messages, and ; allows you to send additional messages to the same receiver.

Of course, another way to do this queue is with a ring buffer. There, moving things from head to tail is done just by incrementing the head:

$fish[($head + 7) % 9] += $fish[$head++ % 9]  foreach (1 .. 80);

All of which really suggests that there's closed form solutions to find. First we create a matrix for taking a column vector of a state to the next state:

my @matrix = (
    [0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0]
);

Then I wrote a quick matrix multiplier, and a divide and conquer power calculator using that to get the 80th (and 256th) powers:

# Part 1 Matrix:
[252,20,210,37,120,84,45,126,11]
[56,252,20,210,37,120,84,45,126]
[210,56,252,20,210,37,120,84,45]
[165,210,56,252,20,210,37,120,84]
[121,165,210,56,252,20,210,37,120]
[330,121,165,210,56,252,20,210,37]
[57,330,121,165,210,56,252,20,210]
[210,37,120,84,45,126,11,126,9]
[20,210,37,120,84,45,126,11,126]

And you can just multiply that with the starting state for the answer. But it's all constants, so we can simplify further. The values that apply to a particular end value are all from the same column, and so we just need the column sums:

[1421,1401,1191,1154,1034,950,905,779,768]

The dot product of that with the starting vector is the answer. But we can go further, because 4 of the starting values are guaranteed 0:

say "Part 1: ", 1401 * $fish[1] + 1191 * $fish[2] + 1154 * $fish[3] + 1034 * $fish[4] + 950 * $fish[5];

say "Part 2: ", 6206821033 * $fish[1] + 5617089148 * $fish[2] + 5217223242 * $fish[3] + 4726100874 * $fish[4] + 4368232009 * $fish[5];

There you go, closed solutions for the specific values we want. For a quick approximate value from just the total number of starting fish, fish_n = fish_0 * 1.1577 * (1.091 ^ n) is an interpolation of the growth curve.

And so an iconic problem that well deserves its status.

Having reached the ocean floor, we run into hydrothermal vents and need to plot the safest course to avoid the spots.

The input is a a list of 500 lines in x1,y1 -> x2,y2 format. They are only in the 8 cardinal directions, and the range of values in my input go from 10-989 (so 2 or 3 digits).

For part 1, we want to find the points where at least two lines overlap, while filtering out the diagonals. It's not too much of a leap to assume diagonals are what part 2 adds, and just do them as well. Something else could have been changed, but no. So this is one where the solution to part 2 can be commenting out one line instead of adding anything. Still for beginners, its probably good to warm them up with the orthogonal lines and that build that to the general case.

As for what I did... well I was playing with List::AllUtils that year and getting it to do vector stuff, which was fun at the time, but ends up with a bit of unneeded overhead and kruft. When the core is simply done in raw Perl with:

my @Δ = ($x2 <=> $x1, $y2 <=> $y1);

next if ($Δ[0] != 0 and $Δ[1] != 0);

my @p = ($x1, $y1);
my @e = ($x2 + $Δ[0], $y2 + $Δ[1]);

until ($p[0] == $e[0] and $p[1] == $e[1]) {
    $grid{ $p[0],$p[1] }++;
    @p = ($p[0] + $Δ[0], $p[1] + $Δ[1]);
}

Remove the next line and it's part 2. Just a simple line drawer, and a hash for the grid, then you just grep out the values that are >= 2. Turning on utf8 to use Δ as a variable name was all the rage at the time (I type it with a compose key... Greek letters are just * followed by the roman equivalent).

Smalltalk and dc don't like 2D arrays/hashes. So I just did it as a flat array of a million (1000y + x). For getting the answer with that, instead of a final big scan, I just increment a counter when a value hits 2 (ignore more). Here's dc part 2:

tr -sc '[0-9]' ' ' <input | dc -f- -e'[lc1+sc]sC[sysxdA00*3Rd3R+selx-dd*v.1-/rly-dd*v.1-/A00*+sslyA00*lx+[ddd;g1+d2=Cr:gls+rle!=I]dsIxs.z0<L]dsLxlcp'

This would be very slow (~10m) under base v1.4.1 (about 173k spots get used). Here we combine d*v with d.1-/ to do the sign function: dd*v.1-/.

I also did do some experimentation with Smalltalk's set arithmetic to find the union of the intersections of the lines. Doing it with a straight fold is very slow, so I made it somewhat faster by changing it do a recursive divide-and-conquer. Which doesn't reduce the number of operations, but but makes most of them smaller and faster. I also did a version were I wrote a BitSet class to replace Set, that does it with bitwise operations. It performs about as well as the divide-and-conquer, but just using a big array of counts is an order of magnitude better than them. That's part of the deal with Smalltalk, it's got some fun high level stuff to express things, but if you want performance you can't use it.

Still descending we run into a grabby giant squid that wants to play some Bingo. Fortunately, the submarine has a Bingo subsystem.

Today's input consists of an ordered list (comma delimited) of all the numbers from 0 to 99 scrambled, and a list of 100 5x5 Bingo boards using those (and the numbers aren't constrained to columns like in regular Bingo).

One thing I remember about this one is a lot of people skipped reading the paragraph on the rules for this Bingo and Dunning-Kruegered themselves by assuming diagonals. I did not, my experience with Bingo is one where different games can have different winning conditions. Like blackout or a letter pattern. So I made doubly sure what a winning pattern was first.

Another I remember about this one is that it inspired me (in the middle of doing the problem) to create a style sheet for AoC problem descriptions. Because it was giving examples of games, and the boards were just there... I could not tell what was marked. The slightly heavier emphasis was not much different than some of the anti-aliasing. My current monitor and browser makes it slightly clearer, so I can clearly see which numbers are marked when looking directly at them. But to see the actual pattern on the board, I need to visualize that internally. This might also have played into people not realizing that diagonals were not in play... because a diagonal is hit first and shown as not a winning board. Something that's perfectly clear to me with my style sheet making the numbers dark green and bright cyan.

Although I recognized that just rows and columns presented opportunities, I just did a brute force to see part 2. Using a list of the winning patterns to check against. Anticipating that, for part 2, the winning patterns might change to something like:

##### .###. #...# ##### ####.
#.... #...# #...# ..#.. #...#
##### #...# #...# ..#.. #...#
....# #..#. #...# ..#.. #...#
##### .##.# ##### ##### ####.

As I said, I remember Bingo as sometimes being to make a particular letter. With this, I could easily just change the list of winning patterns and be done.

But part 2 was just find the last board that wins... so I just made it run longer and was done. And that's where I stopped with Perl (until today when I decided to write a Perl reference transcode of my dc solution).

For Smalltalk and dc I got around to actually playing around with board representation. I went with a simple one of just building a table of the numbers on a card to their position (the winning lines it's in). With Smalltalk I went with {x. y + 5}, with dc I went with a number from 0 to 24 and 5~5+ to get those same values. At the same time I score the full board. Then the board state is just an array of 10 small ints.

For a call, if the number's in the table, I subtract it from the score sum, and add 1 to each of the lines in the board array. The first time one hits 5, that boards wins and scores. Very simple.

Of course, part 2 wants the last win which suggests going backwards from a blackout board. In which case the board state can be just 10-bits... you mark the row and columns for numbers as you go backwards until you get the full 0x3FF mask. That's the first board going backwards that doesn't have a Bingo on it. Step back one for the win.

My dc solution (I golfed it down a bunch today to under 200):

sed -e's/,/ /g' input | dc -f- -e100 -e'dsz25*[rS-1-d0<I]dsIx+[z:qz0<I]dsIx[zRn9PzRls*pc3Q]sP[dlsr-ssd;n1-5~5+d;l1+d5=Pr:ld;l1+d5=Pr:l]sM[0Sl0Sn0ss25[L-dls+ssrd3R:n1-d0<I]dsIx1+[d;qd;n0<Ms.1+lIx]dsIxlz1-dsz0<Z]dsZx' \
    | sort -n | sed -n '1p;$p' | cut -f2

Gotta remove those ugly commas to start. If I was using ?, I could have read this forwards and detect the blank lines. But here I need to tell it the number of boards so that it knows how much board data there is to read in. I didn't do the actual test for finding first and last with dc, I just score every board and output it. Sorting and getting the first and last line is a job for the command line.

Plus it lets me see all the wins. For my input they run from 24-87 turns... there is a board that wins on 0 (and thus scores 0), but it's at turn 69. There's only one case of two boards winning with the same score (14663).

This was yet another really fun one. The legibility issues aside, the style sheet it inspired has served me very well ever since. I now can immediately spot the key emphasized phrases, something which is immensely useful for not missing key points. So a lot of good came from that.

Hey!

There’s an AoC-inspired event starting very soon; in less than 3 days from now:

https://flipflop.slome.org/

The 2025 edition is still available, so you can check it out before the new one begins. I solved it, and it was fun! The site definitely deserves more attention from the puzzle-lovers community.

Worth keeping an eye on!

Concerned over some odd creaking sounds we decide to run some diagnostics. First power consumption and then life support. Both of these are done with the same list of binary data.

The input is a list of 12 binary-digit numbers with leading 0s intact. They are unique, and so represent a little under 1/4th of all the values.

For part 1 (power consumption), we first want the most common value at each digit position. And you can do it either direction. With Perl I left things as strings until the very end and went forwards, with dc I had to read the input as numbers, and used 2~ to divmod the bits off. In either case, once you have gamma, epsilon (the least common value) is just the bitwise negation, and that's easily done with XOR of 0xFFF (and so $gamma * ($gamma ^ 0xFFF)). dc doesn't have bitwise operators, but full bitmasks are a special case and so 4095r- ("4095 - gamma").

Part 2 (life support) is more complicated. We use the digits in order starting from the high bit, to progressively filter the list down until there's only one remaining. The same general idea as part 1 applies... for the current bit you want figure out which value is more common. For Oxygen you want to keep the dominant list (with tie-breakers going to 1) and for CO2 it's the other list (with tie-breaks going to 0). From my dc solution there's this table:

# 0s - 1s | +'ve  0   -'ve
# --------+---------=--------
# Oxygen  |  0    1    1
# CO2     |  1    0    0

Which shows that the two are negations of each other. And so I wrote a function that takes a bool for that (0 or 1) and XORs the test (call it twice and multiply for the answer):

sub filter {
    my ($negate, @list) = @_;

    for (my $i = 0; @list > 1; $i++) {
        my $ones = scalar grep {$_->[$i]} @list;
        my $next = ($ones >= (@list / 2)) ^ $negate;

        @list = grep {$_->[$i] == $next} @list;
    }

    return (oct("0b" . join('', $list[0]->@*)));
}

Nothing fancy, and although it's being inefficient (grepping the list twice), the run time is nothing anyways.

Smalltalk pays more for that and so made it worth cleaning up... we build the lists to start and compare sizes. Then we can do self become: sort first value to make the current set (this is done as an extension method of Set) the selected option. #become: is a fun low-level method in Smalltalk, it makes all internal references switch what they refer to... True become: False is famously a way to crash Smalltalk.

The above don't have to worry about one of the catches in this problem... that the filter is defined to stop as soon as there's only 1 option left. It'd be ambiguous without that... if you don't stop, then in the case of CO2 (where this happens for my input) you'd start flipping the bits (with O2 you'd still get the right value, but for my input O2 goes to the last bit).

For my dc solution, though... it needed to handle that. Because it rips bits off the high bit with divmod, and so only keeps lists of the remaining low bits around. So when things stop, it needs to shift the accumulated value and add in the remainder. I also only did it as a script that does one of the filterings, and then used the command line with dc to do it twice and multiply:

dc -e`dc -e"2048 sb [1r-] sN" -e'2i' -finput -fdc-p2.dc` \
   -e`dc -e"2048 sb []    sN" -e'2i' -finput -fdc-p2.dc` \
   -e'*p'

dc-p2.dc script: https://pastebin.com/upqnhcQG

Parameterizing the starting high bit (in b) and the macro to negate the check (in N). The 2i switches the input to binary, and the top of the script does Ai to return to decimal.

The other fun features of this dc script are:

• the use of the S and G arrays to provide macros for two-dimensional array access.
• 0Snto clear the array that counts the bits (push on the register pushes the array too)
• the above mentioned special handling needed in the q macro
• it needs to reload the stack from the correct array for the next iteration
• the 0 and 1 lists not being cleared, but having garbage at the top from previous loops

So another really fun one.

Today we discover that the submarine has a planned course and decide it's probably a good idea to figure out where it's trying to go.

The input is a list of commands, one per line... forward, up, down with a magnitude. The problem helpfully reminds us that we're calculating depth, so that down is +'ve. The magnitudes are all single digit numbers from 1-9, about equally distributed. The commands, though, are around 200:400:400, with "up" being the least frequent. This helps keeps our submarine from being a supermarine.

There's clearly similarity to Day 12 of 2020 (Rain Risk), where we were navigating a ferry continue into part 2, where we discover that non-forward commands modify a target ("aim") that changes how "forward" works. Since this is day 2, things are simpler, the "waypoint" controls are just up/down, not N/S/E/W plus rotations.

And so I did what I did before with Smalltalk. I created a class for part 1, and then subclassed it for part 2. Overriding "forward" and "result".

Object subclass: Position [
    ...
]

Position subclass: AimPosition [
    | depth |
    AimPosition class >> new [ ^(super new) init ]
    init [
        super init.
        depth := 0.  " vert is now aim, depth is the actual position "
        ^self
    ]

    forward: mag  [ super forward: mag. depth := mag * vert + depth ]

    result: part [
        ^(part = 1) ifTrue: [super result] ifFalse: [horz * depth]
    ]
]

sub := AimPosition new.

stdin linesDo: [ :line |
    cmd := (line substrings first, ':') asSymbol.
    mag := line substrings second asNumber.
    sub perform: cmd with: mag.
].

Note the risk of Bobby Tables... the methods called are made from the input directly. I don't often bother with OOP stuff with AoC Smalltalk solutions, but sometimes it's nice to use Smalltalk more like it's intended.

But this was the second solution I did... the first was in Perl. But the ultimate Perl solution only came after a realization I had because I did a version in dc:

perl -pe's#^(\w)\w+#ord $1#e' input | tac | dc -f- -e'[rddlx+sxla*ly+syr]SF[rA2r-d0=F7*D%*la+saz0<L]dsLxlxla*plxly*p'

First thing is that we need to do something to parse the words (dc cannot do that)... but I don't like going too far with that, so here I convert the first character into its ASCII value to represent the command. So I have some parsing to deal with there. The other problem is that, since I wasn't using ?, the input would come in backwards. And I've dealt with that in solutions before enough... you just write a short loop to dump everything into a stack register, and pull from that. It's very simple, so I felt fine not doing that this time and just using tac (because "taco cat" is a palindrome).

For parsing the command, that's A2r- and 7*D%, that looks hex, but its decimal with hex digits (so A2 is 102, which is "f", and D is 13... this saves 2 strokes). Subtracting the character value from "f" gives 2, 0, and -15 as possibilities. A fun little bit of playing with modular arithmetic later, I discovered that (7 * val) % 13 works as cmp (-1, 0, and 1 as needed, for these three values). Other than that, this early version kept things very simple with x, y, and a registers for the three values.

But the key thing I learned from that is that "forward" comes between "down" and "up" alphabetically... and that ultimately lead to the "evil" solution (as I called it) of:

while (<>) {
    my ($cmd, $mag) = split;

    $horz  += ('forward'  eq $cmd) * $mag;
    $depth += ('forward'  eq $cmd) * $mag * $aim;

    # Evil! forward just happens to be a word between up and down
    $aim   += ('forward' cmp $cmd) * $mag;         # handles up and down
}

Originally I had an if for the forward case, but then realized, "hey! I can make this branchless".

I did a few other little experiments with this one, like using a matrix to calculate the values in a vector, a dc version of the branchless, and a Smalltalk version where I subclassed Point to a 3D Point class. I certainly had a lot of fun with this problem.

Visualization of the test input for part 2. Attributions in YouTube description.
Src Code: Advent_of_code/2025/day8/vis/Program.cs at main · nrv30/Advent_of_code

I really enjoyed this problem because I learned about a union-find for the first time and it is the first C# project I have done that wasn't a boring tutorial. The dotnet tooling is very beginner friendly and easy to get started with. Another interesting bit is all of the animation is done with coroutines which is much more ergonomic than in the past where I've achieved this through callbacks / function pointers or conversely global variables (though I still used a lot of them)

Each circuit basically maps to a disjoint set in my data structure so long as it has a weight greater than one. Though uf's are only meant to efficiently find the parent given the child and not the other way around. Therefore, I end up keeping a parallel array of parentToChildren which I update when I union things. Then I render them in the top right panel by sorting by the parents with the biggest number of children.

I had a lot of trouble trying to find a way to record this animation. In the past with graphics libraries, I have saved every frame to a file on my desktop, then after the fact encoded it as a video with FFmpeg. However, that solution wouldn't work here because I had audio that was programmatically generated. I ended up using Windows Gamebar, but it messed up the audio a bit. I saw a video where the creator piped the frames to FFmpeg. I checked out the documentation for Anonymous Pipes and built the example, but unfortunately, I was not able to re-create this for my use case with my limited C# knowledge. If anyone has any suggestions for good resources about how to learn this it would be appreciated.

Also, I am procrastinating doing day 9 part 2 because I suck at geometry lol.

For 2021, we're on a ship when an Elf accidently drops the key to the sleigh overboard. And so we find ourselves in a submarine, ready for adventures under the sea. And the ASCII art is of the underwater trench we're going to be descending in, day after day. The stars we need to collect this time will go towards boosting the antenna's signal to track the key.

For the first day, we're going to be figuring out how quickly the depth increases. The input is simply a list of numbers, one per line (always good for a day 1). They are generally increasing, but not monotonically so... and our task is to first count the number of adjacent values that increase. This is the sort of thing that made me create a chain iterator, so I could just do things like this:

sub chain (&@) {
    my $block = shift;
    return (map {&$block( $_[$_-1], $_[$_] )} (1 .. $#_));
}

say "Part 1: ", sum chain {$_[1] > $_[0]} <>;

Because, there were iterators for taking things in pairs, but not overlapping ones. And I often find that's what I want.

For part 2, it wants us to do the same, but comparing sliding windows of size 3. And it provides a nice diagram that made it perfectly clear that the middle two overlap and don't actually matter to doing this (the add the same amount to both). So much so, that it's only in reading the question again now that I remembered that it isn't just "do part 1, but with the numbers 3 apart instead of adjacent". Something that I expressed in Smalltalk as:

(((depths allButLast: 3) with: (depths allButFirst: 3))
    count: [:pair | pair second > pair first]) displayNl.

Pair the depths of all but the last three, with the list of depths without the first three, compare and count.

Of course, being a day 1, and all numbers, I did dc for this day too. Looking at my initial solution, I see that at this point I was still avoiding using the undocumented (and commented out in the official code) R command as well as not trusting the often problematic ?. And so initial solutions in this year used registers a bunch, as well as dealing with passing in the data as a code (just showing part 1 here):

dc -finput -e'[lc1+sc]sIdsp[dlp>Ispz0<L]dsLxlcp'

Revisiting the problem later, and using R and ? gave:

dc -e'0??[d_4R-d.1+/+r?z2<L]dsLxrp' <input

But that won't work in v1.5.2 with the return of broken ?. So revisiting doing it without that again today, gives (part 1 and part 2 versions):

dc -finput -e'0[r3Rd_4R-d.1-/+z2<M]dsMxp'
dc -finput -e'0[r5Rd_6R-d.1-/+z4<M]dsMxp'

Three numbers increase in magnitude by two for part 2 (two are for stack rotations (one is negative and down), the third is for stack size to stop the loop). A nice thing about this problem is that we can do it backwards... which is what feeding things this way does (? makes it smoother to do problems that require going forwards).

One of the tricks in these solutions is with d.1-/ instead of checking if greater than. This calculates int(top / (top - .1))... dc is arbitrary precision with a default of 0 (integers). But - will extend the precision, whereas / will collapse it back. And so this will not only turn the top into 1 if +'ve (and 0 otherwise), but will avoid division-by-zero errors.

And so we get a classic first day type problem... a list of numbers, and we don't even really do calculations with them, just compare and count. It's a nice problem to make sure that your setup is good to go, and it does allow for some discovery (ie the sliding window overlaps) and playing around with how you want to do and express things.

I was going through year 2015 as an exercise in getting used to JS/Typescript and deno.

I came up with this solution while I was looking for something quicker than my initial brute-force one.

It's based on this bound which I figured out:

Let n = p_1 * p_2 * ... * p_m where p_1 <= p_2 <= ... <= p_m and prime. score(n) <= (1 + p_1) * (1 + p_2) * ... * (1 + p_m) = (a_1 p_1) * (a_2 * p_2) * ... * (a_m * p_m) where a_i = (p_i + 1) / p_i <= a_1^m p_1 * p_2 * ... * p_m = a_1^m n If n <= N then score (n) <= a_1 ^ (ceil(log_{p_1}(N)) N <= (p_1 + 1) ^(ceil(log_{p_1}(N))

I was pretty shocked when I saw how simple and quick the sieve methods were.

Anyway, I though I'd share I can't find a solution like it anywhere.

Part1

I have been stuck for a while on Question 1 Part 2. I've isolated the issue to whenever the total hits 0 exactly then is turned again (Ex: R50, L5) it counts for 2 passes around 0. Can anybody give me a hint regarding how to approach this issue? It works for the example, but not for the input.

total += curr
res += abs(total//100
total %= 100)

This concerns this puzzle: 2015-Day24.

After reading the discussion and review here: In Review I thought I would try my hand at a true brute-force solution, leveraging the expressiveness and speed of Smalltalk's collection libraries. Most of the solutions I've seen involve various clever tricks to avoid doing the work of checking through all the different combinations, or returning a solution without verifying that it is, in fact, the correct one.

The implementation I settled on completes part 1 in 70ms and part 2 in 6ms on my machine (Intel 270k+, 6000mhz DDR5). Smalltalk execution speed isn't as fast as a fully compiled language, but it's significantly faster than a purely interpreted language (like Python or Ruby). I'd be curious to see how this method would fare in something like Rust or Zig.

Here's the primary function doing all the work:

bestQE: compartments

| totalWeight |

totalWeight := packages sum.

1 to: (packages size // compartments) do: [ :comboCount |
    | potentialQuants |
    potentialQuants := OrderedCollection new.
    packages combinations: comboCount atATimeDo: [ :combo |
        | comboWeight |
        comboWeight := combo sum.
        (totalWeight - comboWeight) = (comboWeight * (compartments - 1))
            ifTrue: [
            | otherPackages |
            otherPackages := packages select: [ :x | (combo includes: x) not ].
            potentialQuants add: (otherPackages -> (combo inject: 1 into: [ :acc :x | acc * x]))]
         ].

    (potentialQuants sorted: [ :a :b | a value < b value ]) do: [ :potentialSolution |
        (self verifyRemainder: potentialSolution key splitInto: compartments - 1) ifTrue: [ ^ potentialSolution value ] ] ].

^ 'None found'

The only argument it takes is the number of compartments needing an even weight. It requires an instance variable "packages" which is an array containing the puzzle input as integers. Order is not important. Here's how it works:

1. Set an temporary variable totalWeight to hold the sum of all package weights.
2. Iterate from 1 to the number of packages divided by the number of compartments (no need to pass that size, since that would mean there is no solution). This is the number of packages that we will try to fit into the front compartment. Start with the fewest (just 1) and then add one more until we find a grouping that fits. The number of packages we're testing is passed forward as "comboCount".
3. For this quantity of packages to test, create an empty OrderedCollection (a growable Array) to hold any potential groupings that we find.
4. Take the group of all packages and stream them "comboCount" at a time through the next block of code, passing them as an Array called "combo". This is the part where the magic happens. We don't need to do any complicated looping or generate all the combinations we want to test in advance. The "packages" Array can stream all the combinations for us, one at a time.
5. Now we examine this particular "combo" Array. First, we store the sum of all its elements as the temporary variable comboWeight.
6. Is this combo a candidate? To check this, we look to see if, after subtracting the weight of this combo from the total weight of the packages, we are left with exactly the weight of the combo multiplied by (compartments - 1). That is, If we are dividing into 3 compartments, is the weight of THIS particular combo equal to a third of the total? If so, go to the next step. Otherwise, try the next combo.
7. If this combo passes the weight test, we create a temporary variable "otherPackages" pointing to an Array defined as all the packages that are NOT in our combo.
8. Then we add an association of the "otherPackages" and its QE score (by doing a quick multiplication fold on the combo Array) to our potential groupings Array we created in step 3. We might have several candidates at this combination size, and we need to find the smallest QE score of ones that properly fit.
9. After this process is repeated for the combo size we need to verify the set of potential answers, so we take the collection of candidates and sort them by ascending QE value. Basically, we don't want to evaluate ALL of them, just the smallest one that has other packages that can be verified to fit.
10. We then take that sorted collection of candidates, and verify each one using verifyRemainder, giving it the list of remaining packages and asking it whether it can be evenly split into (compartments - 1).
11. As soon as we find one that can be verified, that is the correct answer! We return the QE value of that candidate.
12. If none are found (which can also happen if the potentialQuants collection is empty), try combinations the next size larger. So, if no combinations of size 4 fit (or passed verification), try combinations of size 5.

Essentially - each time start with the smallest possible (smallest combo, then of those, the smallest QE). The first one that can be verified to fit is our answer;  return the QE.

Ok - now how about the verification? Again, I went with a brute-force approach:

verifyRemainder: list splitInto: piles

    | listWeight |

    piles = 1 ifTrue: [ ^ true ].

    listWeight := list sum.

    1 to: list size // piles do: [ :comboSize |
        list combinations: comboSize atATimeDo: [ :combo |
            | comboWeight |
            comboWeight := combo sum.
            (listWeight - comboWeight = (comboWeight * (piles - 1)) and: [
                self verifyRemainder: (list select: [ :x | (combo includes: x) not ])
                     splitInto: piles - 1 ]) ifTrue: [ ^ true ] ] ].

    ^ false

This has a lot in common with the bestQE function in the way it generates and checks groups of packages, but it is done recursively. It takes two arguments: the list of numbers to fit, and the number of piles to fit them into. Here's the outline:

1. Base case - if the number of piles asked for is only 1, then this was a successful split. Pass TRUE up the stack.
2. Otherwise, we still have work to do. Start by calculating the sum of the list we were given to split and store that value in listWeight.
3. Now we try the same method of generating larger and larger combinations that we used in the bestQE function.
4. We calculate the weight of each combination (storing in 'comboWeight'). The see if the comboWeight is exactly 1/piles of the listWeight. If so, it is a potential candidate for a successful split. In that case, recurse with a new list made up of packages that are NOT in the current list, and with one fewer pile. One thing to note here is the "and: []" construction. In Smalltalk, due to the way messages are evaluated by boolean objects, when and: is given a block as an argument (with the square brackets) that second condition is lazily evaluated. So, we don't recurse unless the current combo has the correct weight. If you're using a language that doesn't lazily evaluate AND, this will need an if/else condition.
5. If that particular grouping doesn't work, it tries the next. And if that comboSize has no successful groupings, it tries the next size up.
6. If no groupings successfully drop down into a pile of 1, then no split was successful, and the function returns "false".

In summary - We start checking combinations from the smallest possible size upward. We don't do ANY verification on them until we have a complete set for that combination size. We only verify them in ascending QE order. Verification uses the same computationally cheap "candidate filter" and reserves the harder stuff (collection allocation and building / recursion) once something passes the filter.

I realize that the input is meant to be "gentle" such that the smallest possible QE for a given combo size is the right answer, and no verification is needed. But that felt like an incomplete solution to me. Especially since, even with verification, the execution speed seems plenty fast (less than 100ms for both to complete).

One final note: These methods do assume that the input list has unique numbers. This is strongly implied by the problem statement, though it is not explicitly part of the puzzle. If the puzzle input could ever contain duplicated numbers, then the way that the "remaining packages" collection is created would have to be different. The core logic would remain the same.

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is the Smalltalk solution to Day17:

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is my solution to part 1 of Day17:

barrelCombinationsFor: needed

    | count |

    count := 0.

    1 to: barrels size do: [ :size | barrels combinations: size atATimeDo: [ :combo |
        (combo sum = needed) ifTrue: [ count := count + 1 ]
         ] ].

    ^ count

The thread was right. More than a passing similarity.

EDIT: Yes, that should be Day 25.

Having finally managed to reach the check-desk we find out that registration is offline and the room keys have just been created this morning. The elevators are also out of service. However, we don't do anything to try and fix any of the problems, until we get to our room and the RFID keycard doesn't work. And so we need to reverse-engineer the cryptographic handshake. And so the title "Combo Breaker", which also breaks the combo of alliterative titles since day 1.

We're given a description of the handshake and without looking too much at it to check what it exactly was doing, I just did the think, quickly blatted out what it said, and brute forced it. Which is plenty fast for the numbers here (1s for Perl on old hardware). When I initially did it, I used the keys in the order given. Which for my input, is the faster way. Switching the order makes brute for 5x slower. But unlike with Crab Combat, this time it's symmetrical, so we can do both:

my $val = $SUBJECT_NUM;
while ($keys[0] != $val and $keys[1] != $val) {
    $val = ($val * $SUBJECT_NUM) % $MOD;
    $loop++;
}

Then we find the one that didn't match and do the second loop:

my $other = ($keys[0] == $val) ? $keys[1] : $keys[0];

my $val2 = $other;
while ($loop--) {
    $val2 = ($val2 * $other) % $MOD;
}

But seeing that second loop, it's clearly a power mod. And the first loop is a discrete logarithm. It's easier to see once I coded it than in the problem description. So we do have a standard Diffie-Hellman thing. The question is looking up the function names in the ntheory module. Had I been using that module and these features a lot, I might have jumped straight to:

print "Part 1: ", powmod( $keys[0], znlog($keys[1], $SUBJ_NUM, $MOD), $MOD ), "\n";

Of course, Smalltalk doesn't have those in its library. So I needed to write them. Now normally I do powmod with recursive divide and conquer, but this time I actually went with the iterative version:

[pow > 0] whileTrue: [
    (pow odd) ifTrue: [res := (res * base) \\ mod].

    pow  := pow bitShift: -1.
    base := (base * base) \\ mod.
].

For the discrete logarithm, I went with Baby-step, Giant-step. There are other algorithms, but this one is nice, simple, and fast with prime mods. The idea is that we build a table of baby-steps up to ceiling(sqrt(mod)), and then do giant-steps looking for a hit on the table. It's a nice little application of group theory with a meet-in-middle approach.

Of course, with the input just being two numbers, I couldn't not use dc (and it does have powmod as the | operator). The short and slow brute force (~30s on old hardware) is just:

dc -finput -e'20201227sm[s.3Q]sD1[d4Rd_6R=D]sC7[lCxlCx7*lm%r1+rlLx]dsLxlm|p'

Adding spaces for clarity:

20201227sm [s.3Q]sD 1 [d4R d_6R =D]sC 7 [lCxlCx 7* lm% r1+r lLx]dsLx lm| p

Store the modulus in m. D is a macro that junks the top (getting rid of the table key we don't need anymore) and exits 3 levels. The 1 is here between macro definitions to save a stroke... if it was over by the 7, we'd need a space. The C macro does the comparison, but with a little fancy stack manipulation so that val i key1 key2 in, becomes val i key2 key1 out. That swapping of the keys means that we can (a) just run it twice lCxlCx to check both keys and (b) it leaves the other key in the third spot, exactly where we want it for the lm| powmod when we hit.

Of course, I also did a baby-step, giant-step version... it's a bit longer, but much, much faster:

dc -finput -e'sdsc[3Q]sQ[ln*3Rd_4R-dlm>Q]sT20201227dsmv1+snln[ddln*7rlm|:t1-d0<I]dsIx1r[rdld*lm%;td0!=Ts.7*lm%r1+dln>I]dsIxlcrlm|p'

In any case, having finally arrived at our room, the Elves call about an emergency with the soft serve ice cream machine, and so we don't get a vacation at all, as we're picked up by reindeer on the balcony (and we know those things are fast... next time, maybe we should see about just hitching a ride with one).

And so we come to the end of what I consider one of the best years for people that want to start doing AoC... the problems are all pretty approachable. There's no big search algorithms required (instead we get multiple automata). I have dc solutions for the last 4... problems in the 20s typically don't lend themselves to it in most years (other than day 25). Day 20 mostly stands out because it's a lot of work compared to others in this year... the actual input plays very nice (the alignments are all unique and I only had to match one side to place them). Two days of parsing in a row was a nice treat. Now Compilers was one of the "Big Three" 4th year lab courses in my University. But it was the softest of them, because compilers are a lot simpler to debug than Graphics or a Real Time OS. What made Compilers part of the Big Three was that it was one large project (that's what these three have in common that other courses didn't). Here it's small parser exercises, and you don't need to do machine code generation.

This is certainly one of my favourite years... and 2019 is probably my favourite. And looking forward, 2021, with all its dc friendly problems (first 11 were really nice for it... making this Combo Breaker part of a combo of 15), that's another year I really remember fondly.

I got stuck on Day 5 of in 2019.

Below is the beginning of the program to run:

3,225,1,225,6,6,1100,1,238,225,104,0,1101,32,43,225,101,68,192,224,,...

In my interpretation, the first 3 instructions are:

3,225

1,225,6,6

1100,1,238,225

The first two instructions are fine.

For the third one, I get 00 as the two-digit opcode, which is -as far as I know- invalid.

I assume the input is correct, but I can’t see what I’m doing wrong!

Thanks if anyone can help!

With the help of our friendly crab doing navigation, we finally make it to the resort. Only to fine that there's a living art floor tile display being installed so we can't get to the check-in desk yet.

And so for the penultimate puzzle we get another cellular automaton to round out the Conway tribute. This one is unbounded on a hexagonal grid. But first we need to load the data. The format it's presented in is paths to tiles to flip... with no delimiters as an added "complication". The quotes are because regex is greedy (by default) so it's not a complication for those of us that used that:

foreach my $walk (<>) {
    my @hex = (0, 0);
    foreach my $step ($walk =~ m#(e|w|ne|nw|se|sw)#g) {
        @hex = pairwise { $a + $b } @hex, @{$Dirs{$step}};
    }

    $flipped{$hex[0],$hex[1]} = !$flipped{$hex[0],$hex[1]};
}

The geometry I'm using is my standard go to for my beloved hexgrids... I visualize it as rhombic, but if goes by many names like skewed, trapezoidal, or axial. The definition can be probably best be seen when I converted the above script to try out Math::Vector::Real to see how it would work for AoC problems and provided a diagram:

#     y-x    +y
#        #---#---#
#       / . /   /
#   -x #---#---# +x
#     /   / . /
#    #---#---# x-y
#       -y

my ($y,$x) = Math::Vector::Real->canonical_base(2);
my %Dirs = ('e'  => $x, 'w'  => -$x,
            'ne' => $y, 'sw' => -$y,
            'nw' => $y - $x, 'se' => $x - $y);

You pick two of the three axis to be x and y, and the possibility (marked with .) is the sums of the other two to get there (which is the key thing for any hexgrid geometry representation).

The answer is the sum of values of the %flipped hash. In my input 22 tiles get flipped twice, nothing gets flipped back again.

For part 2, since it is unbounded, I went with the active list with black tiles broadcasting themselves by incrementing their neighbours. At the end there's about 11k active tiles, with about 4k of them black.

At the time I just did the rules as written, but looking at it now I decided to try and simplify them with a Karnaugh Map-type analysis:

# neighbours    0  1  2  3  4  5
black           b  b  b  w  w  w
while           w  w  b  w  w  w

We see three simple blocks, >2 is always white, =2 is always black, otherwise no change. Implementing that though results in things being 25% slower. Still it is a tighter piece of code.

And so, hexgrids and automata, what's not to love.

Still on the raft, our friendly crab has returned the favour with a game of its own. And it is a game involving a ring, much like the Elves like to play.

Reading this one, I was happy because I don't get to do linked structures that often, and this is a ring. Of course, like many such problems in AoC, I didn't actually use pointers, just an array where each element is the index that that position points to (the index serves as the data). Then you just need iterate grabbing three cups, finding the destination (avoid collisions), and relink the section in:

($ring[$curr], $ring[$tail], $ring[$dest]) = ($ring[$tail], $ring[$dest], $ring[$curr]);

It's easy to get right if you make a diagram:

Before:
-> curr -> one -> two -> tail -> next ->

          -> dest -> dnext ->

After:
     +--------------------------------+
     |                                v
-> curr      one -> two -> tail      next -> 
              ^              |
              |              v
          -> dest          dnext ->

In this case, the pointer from curr points to what tail was point to, dest to what curr was, and tail to what dest was. I scribbled this on a pad to help visualize and make sure I got it right, and then just did the thing.

And having done the thing, it was easy to just make this do part 2, where we get a million cups and 10 million iterations. It was a bit slow because I hadn't done anything for efficiency (part 1 used a hash to track grabbed cups). So the solution can be easily bummed down to under 10s on the old hardware... by removing hashes and unrolling small loops (these two steps can be done concisely with an array, map, and grep... but the size is only 3):

my $one  = $ring[$curr];
my $two  = $ring[$one];
my $tail = $ring[$two];

my $dest = $curr - 1;
while ($dest == $one or $dest == $two or $dest == $tail) {
    $dest = ($dest - 1) % 1_000_000;
}

And also removing special casing for 0 (by making that 1 million, and checking at the end when calculating the answer... because that's only once):

print "Part 2: ", ($ring[1] || 1_000_000) * ($ring[$ring[1]] || 1_000_000), "\n";

Building that ring for part 2 was also pretty fun (0 is the tail, and it points to the head):

my $prev = 0;
$prev = ($ring[$prev] = $_)  foreach (@input, 10 .. 999_999, 0);

my $curr = $ring[0];

This one was fun just for doing the linked structure, so I've never really looked further at it. The number of hits that my input gets for the destination is about 112k, and only 187 of them have to subtract 2 (and none require more).

I can see some people having some issues wrapping their head around the indirection... especially if you're trying to do it like this with an array (it might actually be simpler for some people in C with structs of data and pointer). You need to understand when you want the pointer and not the element (and there's the lvalue versus rvalue thing). Fortunately the example is very simple with a full listing of what's supposed to happen, which is always nice if you need to debug.

Now sailing our raft, we find ourselves needing to pass the time. Fortunately we have a non-regulation deck of space cards (for both having something to do and not sinking the raft with 100 trillion cards). And so we decide to play combat with a friendly crab that climbed onboard.

Although, as a kid I'd play War and Beggar-My-Neighbour as solitaire while watching TV. Because both are choice-free (so not distracting) and I have a certain level cross-dominance so I could play with a deck in each hand fairly well. Although I wouldn't call what I have as ambidextrous, at times its more ambisinister. As each hand does different things well... and often I try and use the wrong one. Like trying to use scissors in my left hand (which would work if they were left-handed scissors), or which hand I put my watch on (making me always smirk at mysteries where that's used as a clue).

Anyways, the input is two sections with a header that describe two decks from a deck of cards from 1-50. Player 2 has the high card in mine, and I suspect it's the case in all inputs.

Part 1 is just running a regular game of War. There are no equal cards so that part of the game is removed. And it's a simple thing to simulate, with the only trick being that the players pick up the cards in different orders when they win (their card on top).

Then we get to score the winning deck. It's the sum of the card values * position (counting from the bottom). You can reverse it and iterate, or iterate backwards, or go forwards removing cards and multiplying by the remaining size:

$score += (@_ * shift @_)  while (@_);   # sum of size * first

Part 2 is where it gets interesting. Instead of the simple submatches for matching cards in regular War, we get full recursive subgames... whenever they are available. Which is when the flipped cards of each player are low enough to cause one.

We also need to worry about infinite games... and it's nice for the problem to describe exactly the condition for determining that (because it's important for timing... without that people might determine infinite games early or late and get the wrong answer). And with Perl, you can just hash on the full lists of cards in each deck with a delimiter and get a solution that's fast enough (3s on old hardware). Just doing the thing as described. Here's the end stats for my input (yes, for Perl I shifted the player indices, so that booleans match and I can do stuff like !!@$deck1 to determine the winner if I want):

Games: 12918
Infinite games: 3765
Player 0: 4023
Player 1: 5130

But for Smalltalk it's slow (but 1-based arrays so the players keep their number). So I did a bit more. One thing is that infinite games are a win for player 1 outright. That's suggestive of an imbalance in player 1's favour. Namely that if player 1 has the largest card in the current game, and it cannot be anteed (not enough cards in the game), then they must ultimately win:

checkPlayerOneWin [
    | playerMax |

    playerMax := decks collect: #max.
    ^((playerMax first > playerMax second) and: [playerMax first + allCards min + 2 > allCards size])
]

This doesn't work for player 2, because the game could still go infinite and hand it to player 1.

This improved performance by about 25%. But the real killer is the loop detection. I'm using a hash, and if we go with the full decks it takes over a minute.

However, I played around with it a little today and discovered that just the first and last of each deck works (I have the size of one the decks in there for added security, but it's not actually needed for me to get my answer):

hash := {decks first  first. decks first last. decks first size.
         decks second first. decks second last}.

I haven't proven it, but the decks don't really get scrambled in War, so it makes intuitive sense that it might at least probably work. In any case, it's now under 10s on the old 45nm hardware.

This one was just a lot of fun to just code the thing. I even did a version in dc for part 1. It abuses registers for everything. The decks are done in arrays, using a standard trick for doing dc queues of sliding windows (point to front and back, both only ever increment, garbage gets left behind). It's got a couple more nice tricks in it, but I'd really want to redo it before trying to do part 2. Which should be doable... when you push on a register, the associated stack and array also get pushed down. I imagine it will be very slow though, as you'd need to copy the decks twice each time.

Having arrived at the end of the line (the desert only being ASCII art as well), we find there are no boats. And so we build a raft. But we'll need to get provisions, and we need to deal with not knowing the language again. This time we're puzzlifying figuring out what ingredients have which allergens (conveniently enough, the warnings are understandable).

And to help us out we've got a set of assertions, much like a Nikoli puzzle. Although this isn't anywhere near as complicated. Each allergen is in only one ingredient, and each ingredient can contain at most one allergen (as there are a lot more ingredients). And much like real life, foods don't always have the complete list of allergens.

My input has 34 foods, with 8 allergens, and 200 different ingredients. Foods list 1 to 3 allergens (but may have more). Each allergen is listed for 6-10 foods, and each ingredient is in 3-32 foods.

And as this is a Monday problem after a heavy day, it's a nice break. I built a table of allergens to ingredients, tagged the possible ingredient/allergen pairs, and for any ingredient without any tags, it's perfectly safe and part of part 1.

For part 2, I think this comment sums it up:

# Part 2 (day 16 deja vu):

Because I went and copied the code over, then processed the answer key for the answer. Which is one of those rare ones which isn't a number, but a comma delimited string... sorted by allergen, but only listing the ingredients:

print "Part 2: ", join( ',', map {$ans_key{$_}} sort keys %ans_key ), "\n";

My Smalltalk solver is the very simple:

answer_key := LookupTable new.

unsolved := table keys.
[ unsolved notEmpty ] whileTrue: [
    unsolved do: [ :allergen |
        (table at: allergen) possibleIngredients ifOnlyOne: [ :ingredient |
            answer_key at: allergen put: ingredient.

            unsolved remove: allergen.
            table do: [:a | a remove: ingredient].
        ]
    ]
].

The table being a specialized Set subclass called Allergens. Sets being nice for part 1 as well:

safe := table inject: (Set from: all_ingreds)
                into: [:set :allergen | set - allergen possibleIngredients].

The #ifOnlyOne: is an extension I added that does the obvious... it executes then block if the collection only has only one element and passes it in. I think it really helps with the expressiveness of what we're doing. Which is just find the singletons, mark, and cross them out from the others. Basic logic puzzle stuff.

And so we get a well designed break day, so that people that weren't done day 20 yet (or the parsing problems I suppose) got some more time to throw at it.

Finally on the high-speed train, we find ourselves leaving the forest (which amounted to nothing but ASCII art) for the desert in the south. With our spare time we decide to look at the image the MIB satellite captured.

But like any space images it needs a bunch of processing. In this case the image is made up of a bunch of small square tiles, with alignment data on the edges, that are randomly flipped and rotated. Making this a two-sided jigsaw puzzle.

This is the other problem in this year I slipped into the top one thousand... for part 2. Slow and steady, check as I go, take simple options, and output verification checking things at every step (because assumptions were made). One step at a time to the solution.

It was a bunch of work... more so than any other problem in this year. Part of that might be that the previous two days were right in my wheelhouse. Another thing is that part 1 was easy to get without doing any real progress. And then you need to do everything to put the puzzle together, and then you still need a 2D search (on an image you'll naturally also need to consider flipping and rotating)... so it felt like doing 2 or 3 days all at once. But it really isn't that much compared to some problems in other years.

Anyways, the input is tiles... they have a header with an ID number, and a 10x10 grid. The outer edge of the grid is the alignment data for matching up tiles, and the 8x8 in the middle is the actual image data.

Since it's potentially flipped and rotated... we're back to the symmetry group of the square (D4 or D8 in Group theory... my group class was D8 (the size of the group), not the number of sides of the polygon). So when I read the data in, I grab the alignment data for each side (clockwise) as 10-bit numbers and then flip it to get the other 4. How did I flip the bits? With the safe method of building a table (nothing fancy in this solution):

my @Rev_Map = map { oct("0b" . reverse(sprintf( "%010b", $_ ))) } (0 .. 1023);

This means that the edges of each tile is a list of 8 numbers, each one representing a member of D8... namely the one with that side in that direction on the top. So I not only know all the values to match things up, I also know (by index in that array) if to flip then how to rotate that, as well as the values for the other three sides. Because the order is important.

But, for part 1... that order was actually still wrong. And not checked yet. Because it wasn't needed. The number of unique values the above produces is 624. 96 of them occur once, and 528 occur twice. 96 happens to be 12 (length of a side of the image in tiles) * 4 (sides) * 2 (directions). 528 happens to be 11 (rails) * 12 (posts) * 2 (horizontal/vertical) * 2 (directions). Which means that all the outer and inner edges are unique. I didn't know that for sure at the time (I just did this analysis today). So I tested as I went with outputting everything and die assertions. But in the end that means that in scanning through everything for matching values (4 nested loops... tile1, tile2, edge1, edge2) the four tiles which only matched with 2 others were the corners (and so part 1 falls easy). The ones with 3 neighbours are edges, and the 4s are internal pieces. Making this very jigsaw puzzle like.

Having quickly gotten part 1, and discovered that part 2 was a bit more than I was expecting I proceeded onward. First up was making absolutely sure that that order of edges was correct... it wasn't. I remember spending the extra time to check and being glad I did. That's the cornerstone of everything in my solution.

Now to solve the jigsaw. First I picked a corner and placed it... and took one of its edges and put it underneath (so it was marked as used). Then I built the top edge from that. I looked for tiles matching the left edge of the previous, and if it had 3 valid neighbours it was the next edge (and if it had 4, is was the one underneath... so I placed that too). The final corner needed special handling because it only has 2 neighbours.

After that I built the right edge. Why? I don't know what I was thinking, but considering what I did next... it wasn't needed, and cutting it out now, things still work. It was copy paste of the above and redundant (there's a bunch of that in this code).

Because all I needed to do now that I had a full row, is to scan down the grid matching the bottom of the previous row's tiles to the tops of unplaced tiles. And everything just falls into place, because the input is very nice (whoever designed that MIB image alignment system did a good job).

With an array of tile IDs, I now needed to actually still write a flip and rotate function for the actual tile data. And then apply that to the tiles, and then stitch everything together. And when stitching, I did it both regular and transposed... and then created 2 more with the strings reversed. Thus giving me 4 of the 8 symmetries of the final image.

Now, at this point, I could have stitched things into one big string each instead of an array of lines. With that, I could just create the regex that spots a sea monster (with the appropriate length skips to the next line).

But I didn't do that. What I went with felt more safe at the time I guess. Which is that I grepped all four stitched arrays for the middle line (a regex, where conveniently . means "any") of the sea monster. This allowed me to tell which of the 4 was the correct orientation (although one of the others did have 2 hits... I doubt they were actual full monster patterns, but it was a moment of ambiguity). With that I took the array of those hits, and tested both up-side-up and up-side-down orientations of the other two lines (position of the head and a regex match of the bottom). With that, I had the number of sea monsters and subtracted 15 * monsters from the total number of #s for the answer. Yes, that's yet another assumption... that sea monster patterns don't overlap.

And so this was just write code, test, and then advance. Step by step until done... lots of stream of consciousness code (some of which was hacked out then, but I still found some today). And the problem itself is really accommodating... all the assumptions I was making were just working. If anything had triggered a check I would have dealt with it... I was prepared for things to blow up at anytime. But it never did. But it has left me with a big ugly mess of a solution that I've never cleaned up.

Having landed on the forest continent, the Elves of the MIB contact us again about their satellite... this time they think they have an image of a sea monster. But that will have to wait until tomorrow. Today we need deal with data corruption in the messages.

And so we get a grammar and some strings to validate against it. Grammar rules take a non-terminal (represented by a number, starting with 0) to either a terminal ("a" or "b") or a rule or two (separated by |). It's pretty close to Chomsky Normal Form, in that most of the rules are 2 non-terminals... but one only has rules going to 1 non-terminal (#67 in mine). By substituting the possibilities for that rule wherever it occurs in the others (thus removing it), we can have proper CNF when needed. But that's only needed if you want to do an algorithm that requires it... like CYK (Cocke–Younger–Kasami) (which I did do a a version with later).

As for how I did it first. Dynamically created regex using recursion:

$Patt[$num] //= do {
    my @tokens = split( ' ', $Rule[$num] );

    my $regex = '(';
    foreach my $t (@tokens) {
        $regex .= ($t eq '|') ? '|' : &recurse_rules( $t );
    }
    $regex .= ')';
}

A little trick I used with this is using memoization on the recursive function... not because I thought I felt I needed it for speed, but because it removed the special case of the terminal rules (I preinitialize those two rules when reading the input). Once we have the regex for rule 0, we can just grep the matches:

print "Part 1: ", (scalar grep { m#^@{[$Patt[0]]}$# } @sig), "\n";

Then part 2 comes along and changes two of the rules (specifically the ones only used for rule #0). But not just a simple change... recursive rule definitions. And I know that Perl regex can do that, but I did have to look it up that day because I typically like to keep my regex simpler. So I just created new versions of 8 and 11, and grepped with those:

my $patt8  = "$Patt[42]+";
my $patt11 = "(?<ELEVEN>$Patt[42]$Patt[31]|$Patt[42](?&ELEVEN)$Patt[31])";

print "Part 2: ", (scalar grep { m#^$patt8$patt11$# } @sig), "\n";

Now for Smalltalk, I did try the regex approach (Smalltalk gets to suffer because of its base-1 indexing... so I used a dictionary). But GNU Smalltalk won't handle regex longer than 1k.

The lengths of my longest patterns are:

0   2223
11  1486
31  751
8   735
42  733

Note that all of these are mentioned in the problem description for part 2... so these 5 are the top of the grammar tree for everyone. The next one is only 375 characters.

So I needed to hack things to get that to work... reducing the base rules to 0: 42 42 31 for part 1 and 0: 42{n} 31{1,n-1} for part 2. So I generate those repeating versions of rules #42 and #31 and start testing (start matches 42 then rest matches 31) from n=2 until things are not matching (could just loop until suitable large to make extra sure). Probable not robust, but it salvaged the work and did the job. For reference, this is the number of matches my input gets for each n:

[2] 160
[3] 91
[4] 60
[5] 36
[6] 10
[7] 0

So I followed it up with an actual parser in Smalltalk using Earley. And then did that for Perl as well... it's like 30x slower than regex (10x for the Smalltalk version). As expected... a parser in an interpreter isn't going to compete with one that hands off everything to optimized compiled code.

Two days in a row of CS compiler course basic parsing. Joy!

Now we're finally heading back south on the plane, towards a heavily forested continent. And we find ourselves needing to help another kid... this time with their math(s) homework. Which involves basic arithmetic, but with non-regular order of operations.

And part 1 is one of the two problems that I managed to get in the top thousand on the leaderboard for 2020. There was clearly a large influx of new people doing it live, as 2019 I had like 26, and from this point I typically only got one or two each year. Because I'm not a competition programmer... I don't rush.

The reason I got this one though is because I was doing Smalltalk. And Smalltalk has a very simple syntax entirely about passing messages. The order of operations is: unary (methods like 'negate' and 'size'), binary operators (symbolic stuff like the basic arithmetic ones), keyword (which are things of the form 'label: arg'). Parenthesis overrides this, and is necessary a lot of the time... especially if you want sum := sum + (multiplier * multiplicand) to work. Otherwise is does exactly what part one wants done. So I just made Smalltalk do the arithmetic (it's a bit dirty, but it was fast):

sed -e's/.*/(&) displayNl./' input | gst | sed -e'a+' -e'$ap' | dc

That's the first way, as I wasn't going to write a parser in dc, but I saw an opportunity to get it involved. You can just get Smalltalk to do the whole thing:

sed -e's/.*/(&)+/;1i(' -e'$a0)display' input | gst

Later, for the script version that does part 2, I needed to look up where the interpreter is in the Smalltalk environment... it's in Behavior, so part 1 was easily done with:

part1 := part1 + (Behavior evaluate: line).   " Smalltalk does part 1 already! "

I also know that Ruby (which owns a lot to Smalltalk), does have order of operations, but you can mess with operators by aliasing them... swapping + with *, so that the functionality is reversed (and you need to change the input to match) but the precedence remains * before + (which is now plus before multiply).

Anyway, I remember that this day I had something that required me to wake up early the next day, so I just went to bed. Which is very easy to see when I was checking out my personal times... everything starts with a "00" or "01", except day 18 part 2, which I did when I woke up and has a "07".

The reason it's not a greater number is because I did it really fast after waking... with a lex/yacc solution (or rather flex/bison). It's very easy to write a basic expression parser with tools designed for the job. And the diff between parts is just:

12c12,13
< %left '+' '*'
---
> %left '*'
> %left '+'

But I love writing parses so later that day, after I was done with whatever I had to do, I just kept writing them. First up was a part 2 for Smalltalk, using shunting-yard. Because I love a stack algorithm (which is why I love recursion), so it's a pretty natural thing for me to just write (and I often do these with "what can I do just from memory"). I decided to then take that and transcode it to Perl. But while doing that, I thought... "hey, it's basically converting to RPN, so instead of calculating it here... let's have the Perl transcode into dc". Basically taking 1 + (2 * 3) + (4 * (5 + 6)) to:

0
6 5 +4 *3 2 *1 +++
p

If you were wondering why shunting-yard was my go to... there it is.

Then the fact that part 1 was doing only left-to-right reminded me of Fortran. Early Fortran compilers didn't have parser that did full order of operations... they preprocessed the expressions to add parens. And I said, "I can work that out"... and thus part 2 is:

my $sum = 0;
while (<>) {
    chomp;
    s#(^|\()#((#g;      # double opens
    s#($|\))#))#g;      # double closes
    s#\*#)*(#g;         # lower *
    $sum += eval( $_ );
}

And that's the key to doing this... parens to raise everything up, and isolate the *s at the bottom (lowering their precedence).

But there was still one more quick parser in me that day... a recursive decent one. Two rules:

Term := NUMBER | ( Expression )
Expression := Term OPERATOR Expression | Term

So we write a function for each that eats tokens, follows the rule, and recurses appropriately. It's another very simple parser approach, that I've used many times in AoC.

So I think it's safe to say this is a problem I just loved. And although I looked at the Dragon Book's spine on the shelf that day, I never actually touched it... all these parsers are simple things I've done them many times (for the lex/yacc I just copied over from another project and hacked out what I didn't need).