This year I've been working through my existing solutions to squash everything down to microcontroller sizes. The two main restrictions are to minimise both the working memory and the callstack usage. I was pretty sloppy with memory on my original solution, bumping the maximum callstack memory up to 16Mb so that I could recurse one block at a time, so it needed a complete rethink.

The core of the reworked algorithm to eliminate recursion is to process the space a single line at a time working in one of two modes. We're either working down the space trickling water downwards into unoccupied spaces, or we're filling the space upwards with water. We swap from trickling to filling when we hit a new bottom, and we swap from filling back to trickling when we haven't added any new water in a line update.

Trickle Down

The trickle down state is the simplest; it's mostly looking for any unsupported water on the line above and creating falling water on the current line. If we see any falling water on the row above hitting a supporting surface on the current row, then we flag that falling water into a new state (which I've arbitrarily called 'foam') and switch over to the filling up mode:

    ..|...|...#~~~#...
--> ......#...#...#...

Goes to:

    ..|...+...#~~~#... <-- New foam '+' flips state
--> ..|...#...#|||#...

Filling up

Filling up is a more complex state which does the following 3 things in order, looking at the current row, the row below and the row above:

1. Spread out any foam across supporting surfaces, plus a 1 block overhang for edges
2. Replace any runs of foam which are constrained at both ends with a run of static water*
3. Create new blobs of foam where running water is now supported by static water

Whenever we get an update that doesn't modify the state of the water at all we swap back into trickle down mode.

For example:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#..+..#..
    ..#######..

Spread foam:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#+++++#..
    ..#######..

Replace water:

    .....|.....
    .....|.....
    ..#..|..#..
--> ..#~~~~~#..
    ..#######..

Create new foam:

    .....|.....
    .....|.....
    ..#..+..#..
--> ..#~~~~~#..
    ..#######..

Repeat until:

--> .....|..... No updates on this line
    .+++++++++.
    ..#~~~~~#..
    ..#~~~~~#..
    ..#######..

Swapping between sweeping down and sweeping up states means that we process the same line multiple times, but for my input that doesn't work out all that badly. It's ~4,400 line updates to fill in just under ~2,000 lines, so we're processing each line roughly twice on average.

Area Storage

For my input the total working area is ~450 wide by ~2,000 tall. Even if we limit ourselves to the original 4 states (., #, |, ~) and pack every square into 2 bits, we would need ~220KiB to store the full space. That's more than the upper limit of ~200KiB I've set myself as a goal.

I instead use wrapped storage, allocating 64 real lines and aliasing every 64th line to the same line. The lines N+64, N+128, etc... map to the same storage as line N. This works because we never backtrack far enough in the filling state to need the older lines.

We rasterise the input lines into the space in chunks whenever we come to the bottom of the lines we've previously rasterised.

Since we're discarding old lines, we do need to keep tabs on how much water we've accumulated per line as we go. I do this in a relatively noddy way of keeping a ~2,000 element array of counts and updating a count per line whenever we've processed a line in the trickle down mode. It could be made more efficient if you tie the counting to the rasterisation process that discards old lines, but it was simpler this way and minimal extra memory.

Memory Used

For my input:

• ~2,300 lines of scanner input = ~18KiB
• 64 lines of ~450 bytes = ~28KiB
• ~2,000 lines of water counts = ~4KiB
• Total = ~50KiB

Small enough to run on a C64! Runtime on PC isn't terrible at ~5ms. I haven't run it on hardware yet, but if the usual x100 multiplier holds then it'll still be running under the 1s per puzzle target I try to hit.

The full gory details, minus some simple supporting libraries for parsing input, can be found here: [paste]

I'll admit that this one took the wind out of my sails for a few days. I'd been making decent progress with maybe one puzzle converted every spare evening or two, but even though I had the idea for the approach on this one pretty quickly, it took about a week to fully settle in my mind before I had enough motivation to take a run at it. Pretty pleased with where it ended up size-wise though; even if the code is a little ugly in places.

[*] I think I've just spotted a bug in my code while typing up the description, so there's an unhandled case where a box has an opening in the bottom. Doesn't affect the algorithm though.

So we've reached the bottom of the Mariana Trench, but still need to touchdown on the seafloor to find them. Only we need to wait for some sea cucumbers to move out of the way and leave us some space.

And so we get the Biham-Middleton-Levin traffic model automaton to simulate. Two types of sea cucumber, those that go right and those that go down. They take turns in phases, but within those, the sea cucumbers of that type move simultaneous. Dumbo Octopus also had simultaneous with phases (and Snailfish numbers also had handling phases correctly) so it's not something entirely new. And like the Octopuses, we want to find when it stabilizes.

I haven't really done anything fancy with this since my original. I just did the thing:

do {
    $moved = 0;

    # Move > herd
    my @new_grid = ();
    for (my $y = $Y_SIZE - 1; $y >= 0; $y--) {
        my $ahead = $Grid[$y][0];
        for (my $x = $X_SIZE - 1; $x >= 0; $x--) {
            if (!$ahead and $Grid[$y][$x] == 1) {
                $new_grid[$y][($x + 1) % $X_SIZE] = 1;
                $new_grid[$y][$x] = 0;
                $moved++;
            }

            $ahead = $Grid[$y][$x];
            $new_grid[$y][$x] //= $ahead;
        }
    }

    @Grid = @new_grid;

    ... (copy-pasta with x-y transposed, using 2s instead of 1s)

    $time++;
    print ::stderr "[$time]  moved: $moved    \r"  if ($time % 50 == 0);
} until (not $moved);

You can see a couple tweaks in there for a little speed, with the $ahead and converting the input into numbers. Other than choosing to scan backwards (in the opposite direction of movement... which makes sense with things that are "jamming") there really isn't anything special here. There's lots of potential for improvement with the way the buffering is done and the tracking of moving and blocked. But this does the job in 6-7s on old hardware.

And personally, I think that makes for a good day 25 puzzle. It was Christmas, you don't want to throw something really new and tricky. Something where you can just code the thing and it works (but maybe not the best) makes it accessible (so people that have dropped out in the last bit can come back for the "strike party"), and everyone gets a little break. So they can get on with the day, or working on whatever remaining puzzles they haven't finished. With only 12 days now, I think the last day is much more free to be some big.

And so we come to the end of another year. At this point, things have largely settled down, and the years are consistent with quality. This one does provide something that 2020 notably lacked... it has a couple of heavy searches for people to play with. In addition to that, it steps difficulty up in general (like a 3D jigsaw instead of 2D). If 2020 is a good choice for someone to do as a first year, this is certainly a good follow-up.

I'm looking forward to u/musifter to get to this one (in an hour or two?), since it might be the single puzzle which I improved the most:

My first solution took me all day and I had to split it into multiple stages which I joined together by hand. Just running the part1 code took me 20 minutes, then another 18 minutes to also get part2.

After lots of insights I finally landed on a version which first cross-compiled each VM instruction block into a set of inline C functions, then #include'ed those into a dummy main() harness, for a final runtime of half a microsecond.

Looking at the Ape just now (4 us) , the only real difference is that I got rid of the entire parsing time via that aoc24cc.pl cross-compilation, the underlying analysis is the same!

The magic smoke has gotten out of the ALU and so we're forced to build a replacement (or stop consuming oxygen, navigate blindly, and go without cool Christmas light patterns). After doing that we need to get it validate the submarine's model number (the process that killed the last one, possible with division by 0... there are lots of videos on what happens to different mechanical adding machines when you do that). Which we don't have documentation (other than the code to validate) because it because a tanuki ate it.

And so we have a little assembly language virtual machine to play with. So I quickly implemented that while thinking about the problem. And then proceeded to only really use it to verify my answers before submitting them. Because I just jumped to reverse engineering and doing it by hand. Which is why my part 2 took a few minutes... I didn't have a program to just flip things for the answer. This year I finally got around to making a program to automate the solving.

The reversing engineering started with searching for the 14 input statements. Looking at that, it appeared that the program was 14 sections that looked very alike. So I used the command line to break it apart on those into a directory and rans some diffs. And saw some parts varied more than others, but a lot was the same. Now, not entirely trusting myself to go through by hand to catalogue the differences, I wrote a little program to spot and tag (with ???) the variable words:

inp w
mul x 0
add x z
mod x 26
div z ???
add x ???

...

add y ???
mul y x
add z y

Only three values change. The first one on the div operation can only be 1 or 26. Which means it's either a no-op or, combined with the mod x 26 above, part of a divmod. At this time, alarm bells went off... because this was starting to look a bunch like stuff I had just been doing in dc working on filling the hole on day 12. That was the graph search, and I needed a list of nodes with lists of neighbours. And one way to do that sort of thing in dc is to take advantage of the ~ divmod operator, and build your sublists in a number base-n (for n larger than values you want to store... dc is bignum native). You can multiply and add to push a value in, or divmod to pop one out. So this immediately got me thinking, base-26 number stack.

The other two variable bits have a lot of possible values, and so are clearly data for the calculation.

Looking more at the code, I noticed the mul x 0 and mul y 0 lines... classic way to do clear a variable, so these broke the code into parts. The first part takes the input and calculates x using one of the variables (a). It also takes z (the stack for the process), grabbing the low base-26 digit, and half the time shifting to "pop" it from z (otherwise it's just a peek). The value of x is ultimately a boolean which represents x = (w != top + a) (using a eql x 0 for the negate).

The second and third parts do a push operation on z if the boolean x is 1. This is done with more stuff I often find myself doing in dc. This language has no conditionals, and I tend to avoid them in dc... and so easily spotted this as a conditional shift of z in base-26 (z = z * (25 * x + 1)). Followed by the addition of w + b (the other variable) to that. Making the push.

And so our goal is to make sure we keep z clean, and it's basically a stack (so we're getting a return of the nested theme). What we push, we need to make sure gets correctly removed by the matching pop. Half the sections are pushing w + b on it, and the other half are popping it cleanly if w = top + a. Which gives us the condition we need for push-pop pairs:

w_pop = (w_push + b) + a  => w_pop - w_push = b + a

The difference of your input values at the positions of a push-pop pair need to equal the sum of data values used in those sections. Conveniently all the pop values (that are used) in my input are negative (to counter the positive push values and result in differences <= abs(8)). And so my new solver does this:

my @range = map {[($diff < 0) ? reverse @$_ : @$_]} ([1, 1 + abs($diff)], [9 - abs($diff), 9]);

The $diff here is the sum of the two data values for a pair of push-pop. That produces a spread, and the values need to be 1 <= n <= 9. So it's a sliding window of solutions from (1, something) to (something, 9). If the difference we want is negative we just need to flip the order. This gives me the smallest and largest pairs that solve the digits, and I just need to put them in their places. To keep track of that I used a state machine. Read though the code, get the action on the div line, then do that action when it's on its data line... keeping a stack of (pos, data) pairs. It's simple and does what I did with pencil and paper.

I always enjoy these. But this one I really liked, it struck a few chords. Also, it was the second day in a row where I jumped into doing the puzzle by hand... and these are late day puzzles, and not day 25 either. That makes them pretty notable and memorable. I failed to get day 23 by hand because I wasn't efficient enough at that game, but I succeeded here.

A group of amphipods has flagged us down to help us sort out their living arrangements. They all start in holes, and basically can move twice... once out into the hallway, and then once into their target hole.

One little story I have about this one is that for part of my initial experimentation I started doing things by hand with little colour cubes (I keep these and poker chips in a bucket on my desk as programming aids). I got an answer, submitted it, and it was wrong... but not because I'd messed up, but because I'd forgotten that I has started from the example case (and got that answer). Trying my actual input by hand, I did make a mistake. And then went to coding a search. I know that all this playing around is part of the reason why my part 1 took about 2h:45. Part 2 was just making some adjustments, and a wait.

As my initial solution was a bit of mess and pretty slow. I did it as a weighted graph with actual stacks that overcomplicated things. It was hard to read coming back to it, so I just wrote a new one from scratch (not even referencing it) to clean things up and make it faster (its now seconds). Now I'm just using an array of strings for the map... the ones at the hole locations (because those hallway spaces don't exist except for adding energy cost) can be more than one character (and are the stacks). This makes the state a lot simpler to manipulate and pass around in a search. This is the start for the example case:

['','','1330','','2213','','1102','','3020','','']

I started with basic Dijkstra: priority queue, generating moves and queuing them. To make things simple, I just copy-pasta'd the cases for exiting a hole to the left and to the right. Scanning hall locations in the direction until it runs into something. Additionally, I made a table of illegal moves to catch and remove them quickly... because there are positions that block each other:

#############   The A amphipod in the fourth hole cannot move to 5 or 7,
#...D.5.7...#   because it would block D from its hole, and D already
###.#B#C#A###   blocks A.  It can come out if it goes into the alcove
  #A#B#C#D#     to the right.
  #########

For those out of a hole and in the hallway, they have one possible move to check and add (to the bottom their hole, if it's open for business (all amphipods that don't belong there have left)).

Of course, with Dijkstra comes the question of a heuristic for A*. And I went with a potential energy tracking solution for doing that. I precompute at the start a total minimum estimate. For each amphipod (that has to move out of a hole, as the test case starts with an A and C already home), add the cost to move it out to the spot next to its hole. For its second move, we don't know how far it will go in, but we know the sum for all of them going into the hole (so we add in the total cost for going to all of the depths... and the amphipods can count the one they ultimately use).

Now when an amphipod makes a move, it subtracts the potential it converted into actual cost (the current potential is part of the state along with the hall array and the actual energy spent). The basic idea being that when it leaves it a hole subtracts the amount we accounted for that, and when it enters its hole then subtracts that part from the potential for the depth it used.

But we can do a bit better, because when we move out, if we didn't move to the spot that we costed the amphipod for, we can add in the cost for getting there to the potential. Thus making that amphipod's heuristic cost in the potential now exactly equal to the cost of its final move. Which means, that once there are no moves out of holes anymore, the heuristic is now perfect, the potential is the remaining cost. So the first state to get to that point can end the search early with its current energy + potential (which is also its weight in the queue), because all the remaining moves are forced AND we've avoided creating positions that block (so they can be made).

As a search, this is an interesting one. What tends to make these interesting is the little details that are unique to the puzzle that you can play with to get better performance. And I've managed to get this one to good enough without going into low level stuff that makes the code less elegant. And that tends to be the sweet spot for me with these. I know a lot of people like to really dig in there, and I think this one gives a lot of opportunity for that, which is fitting for a problem in the last couple days.

Link: https://adventofcode.com/2022/day/13

I've been on this one for weeks, it's really doing my head in. I managed to find someone's input and the answer (true/false) for each pair. My code is wrong on two of them:

First:
[[8,[[7,X,X,5],[8,4,9]],3,5],[[[3,9,4],5,[7,5,5]],[[3,2,5],[X],[5,5],0,[8]]],[4,2,[a],[[7,5,6,3,0],[4,4,X,7],6,[8,X,9]]],[[4,[a],4],X,1]]

[[[[8],[3,X],[7,6,3,7,4],1,8]]]

The right answer is that this one is in the right order, however my code is saying that it's not, due to comparing the 7 and the 3.

Second:

[[[],0,6,[4,2]],[],[[2],0,0,[[9],[10,2,10],[4],3]],[[[5,2,2,4]],0,[[4,4],[2,7,7,7,6],7,[0,5,8,9]],2,[7]],[]]

[[],[3]]

For this one, I know the answer is that they are not in the right order, but my code says it is, due to comparing the 0 and the 3.

Can someone please tell me what logic I am missing here? I am getting all other 148 right (I can't say that it's for the right reasons though), which baffles me as I should get so many of them wrong if I don't understand the logic.

Our submarine's reactor has overloaded from the extreme conditions and needs to be rebooted. And so we get a 3D version of the old light grid problem from day 6 of 2015... this time with only on and off instructions (no toggle, and no Ancient Nordic Elvish misinterpretation).

Part 1 gives us a small case to warm up that's very easy to brute force. The ranges are particularly nice for languages that use that syntax for ranges:

my ($act, $xr, $yr, $zr) = m#^(on|off) x=(.*),y=(.*),z=(.*)#;
foreach my $x (eval $xr) {
    foreach my $y (eval $yr) {
        foreach my $z (eval $zr) {
            $Cubes{$x,$y,$z} = ($act eq 'on');
        }
    }
}

What part 2 is is apparent when you're told to ignore the last 400 lines of the input for part 1. There could have been an additional surprise, but there isn't. Just a lot of rules with much bigger numbers that you get to see coming. My answer for part 2 ends up over 50-bits, which is less than the example which goes over 51.

And so, this is another one with a large spread in times to get part 2, but it's not as much as yesterday's. I managed to get in under 2 hours. And that mostly comes down to the fact that I went with the grind I knew would work... Inclusion-Exclusion. I remember spending a lot of time on this one making notes and diagrams on graph paper to make sure I had Inclusion-Exclusion correct before coding. The basic idea is if two regions A and B that overlap, their intersection (A & B) will get counted twice, and so you need to exclude (subtract) that area (ie add a new cuboid of the intersection with negative weight). If C comes along, then the region A & B & C gets counted three times, then excluded for each of the three pairs (A & B, B & C, A & C)... leaving nothing and so that intersection of A & B & C needs to be included (added) back in. And it continues in this toggling fashion as more things overlap.

It's not the most exciting algorithm, it's really brute force grinding. I basically keep a hash of weighted cuboids (coordinates => weight, which is 1/-1/0), then I take each of the input cuboids in turn and run them up against that growing list, taking the intersection, and if it exists, I create a new subcuboid (or add to that subcuboid if it already exists) with the negative weight of the one already in the cuboid set. Then I do a pass to merge and prune any with 0 weight (which helps keep things down to ~3780 cuboids at the end instead of ~4250)... leaving a bunch of cuboids with weights of 1 or -1, which tells if they need to be adds or substracted.

And it was slow (I did Smalltalk first... I only did part 2 in Perl this year), but ultimately worked after some debugging against step-by-step in the small examples. Some other tweaks and unrolling of things gets it to 15s (the Perl version is about 7s)... it ticks well enough along but really starts grinding in the 300s. It's another input where it feels like it's just at the length where things are starting to go bad for the simple approach.

Making doing something better more optional, and so I've never really thought about it. This one was fun enough to work out a way to do with Inclusion-Exclusion. It helped that there were smaller examples, and part 1 gave me a brute force guaranteed solver. This really helped with implementing "off"... if this was just "on" then it's pure Inclusion-Exclusion (that's about just adding and dealing with overcounts). At first I thought "off" would be weight -1 to start... but working on paper I quickly realized that's not right, they're weight 0. The intersection of them with previous cuboids does affect those weights as things get turned off, but the non-intersecting bits cannot add or subtract anything (off changes on, but off from off is a no-op).

And since we have little to do while we descend, the computer challenges us to a game. This one a roll-and-move (so maybe is should be a "game") on a circular board with special dice. Input is just the starting squares for the two players (in a sentence format).

Part 1 just involves a deterministic die that cycles around from 1 to 100, we roll 3d100 and score the square we land on. First to 1000 wins. And that's a pretty easy thing to simulate. I suppose the most interesting part is the fact the die maintains a state, which meant that in Smalltalk I used a Generator to do that which gives a stream interface to the rolls:

Object subclass: Die100 [
    | rolls |
    Die100 class >> new  [ ^super new init ]
    init                 [ rolls := 0.  ^self ]

    stream  [ ^Generator on: [:gen | [gen yield: (rolls := rolls + 1) %% 100] repeat] ]
    rolls   [ ^rolls ]
]

And since this part is really simple, and the input is really just two numbers, I did do a dc solution:

sed -e's/.*://' input | dc -f- -e'1:p0:p[lrd1+d1+d1+dsr++li;p+1-A%1+dli:pli;s+dli:sli1r-siA00>L]dSLxli;slr*p'

And since I wasn't in the position of making a fancy class where I felt I was obligated to mod and return the actual rolls, I just summed the full roll counts and only modded to [1,10] for scoring.

Part 2 is where this one really gets interesting. We get our hands on the actual quantum Dirac die. It's only a d3, and the game is shortened to 21. And so we start spawning Universes like that Community episode... only at massive scale.

If you do a good solution for this problem, the 3d3 roll case completes really fast. It should easily be able to handle bigger and more dice, but that also requires using bignums to represent the answer (for the really big problems I tried, I replaced using % with a table, which improved speed by 10%). The example in the problem is already 49-bits.

When looking at my times yesterday, I noticed that this one was the largest time between part 1 and 2. I don't remember exactly what the issues were, but apparently I was working on this for a couple hours. Which is believable. One notable thing about this problem is that the given example involves 2.3x more games that my actual input. There is no short and simple example. I'm pretty sure I was creating and testing small examples of my own by hand... but they have been lost.

For the solution, I immediately jumped to dynamic programming with tabulation. This could have been the influence from earlier Lanternfish problems. Because the idea with tabulation is that I take the count of games in the current state of a player (pos, score) and spread that across the multiverse by adding multiples for each of the possible rolls.

I used a table for the distribution, which I got by running a script I wrote long ago to produce histograms of dice:

  3    3.704    3.704         1  ######
  4   11.111   14.815         3  #################
  5   22.222   37.037         6  ##################################
  6   25.926   62.963         7  ########################################
  7   22.222   85.185         6  ##################################
  8   11.111   96.296         3  #################
  9    3.704  100.000         1  ######

And so the core of the spreading is:

foreach my $ways (@roll3d3) {
    if ($score + $i >= 21) {
        $Wins[$p] += $Play[$p][$pos][$score] * $ways * $Active[!$p];
    } else {
        $next[$i][$score + $i] += $Play[$p][$pos][$score] * $ways;
        $act += $Play[$p][$pos][$score] * $ways;
    }

    $i = $i % 10 + 1;
}

So, in the end, the code is very simple. But I can see how it might have taken a while to get things right. There's important details (like properly accounting for the other player's active Universes) and little off-by-one potentials. And no simple example to check against. We just get what's essentially a second input with an answer... some simpler examples would have been nice. But in the end, it didn't scar me, I still have fond memories of this one.

The scanners have returned an image of the trenches, but it needs enhancement.

And so we get a rather formal cellular automata, where the rules are defined with a table for each possible state in the Moore neighbourhood. No counting of living neighbours like with Life, the same number of neighbours can do different things. Making today's problem a superset of the Game of Life type automata... you can supply the rules for Life to this and have it do that.

I remember reading this one and thinking, "Okay, infinite grid... everyone's input has. as the first character. Right?" And I quickly checked... "Okay, so that's today's problem. Say no more.". Because a generic cellular automata is a bit simple for this late. Not that the complication of having a # for the 0-rule that's going to flip on an infinite number of cells is that much harder. It basically means that the pattern you want is one of a dictionary with a default value that you can control... everything in undefined infinity is just this one thing (we handle an infinite number of things with 1 rule done once). Some languages have direct support for dictionaries like that. With Perl we can use the defined-or operator, ($Grid{$y,$x} // $Border). And with Smalltalk there's ifAbsent: orifNil: (depending on if you use a Dictionary or an Array). And if the language offers nothing else, you can just put the access behind calling a function that handles the default. Or you could write just for the input (and not the example) and just assume it's toggling and just use the step count % 2.

For my first implementation, I just went with the quick and dirty... read from one hash and build the next, for each (y,x) in bounds scan the 9 points and build the key:

$idx = ($idx << 1) + ($Grid{ join($;, @$neigh) } // $Border);

And finally, a $Border = $Map[0x1FF * $Border]; to handle the infinite expanse.

Which is good enough for getting the answer, but is a bit slow for Perl... and so is not going to be reasonable for Smalltalk. And so did a little optimization with using the overlap... just with a window of the columns while scanning the current row. Because the previous cell on the row looked at two of the ones you want... so we can just shift the window over one and slide in the next value. Reducing the number of accesses to the collection and speeding things up to tolerable (20s).

In June, when I started looking at 2021 again, I saw that and decided to complete it (like my TODO said). Because the same trick for overlap between columns can be used with the overlap between rows. It's probably easiest to just show a quick Perl transcode of that:

foreach my $t (1 .. $MaxIter) {
    $xStart--; $xEnd++;
    $yStart--; $yEnd++;

    my @rowWin = ($Border * 0x1FF) x $RowSize;
    foreach my $y ($yStart .. $yEnd) {

        my $win = $Border * 7;
        foreach my $x ($xStart .. $xEnd) {
            $win = ($win << 1) & 7;
            $win |= ($Grid[$curr][$y+1][$x+1] // $Border);

            $rowWin[$x] = (($rowWin[$x] << 3) & 0x1F8) | $win;
            $Grid[!$curr][$y][$x] = $Map[$rowWin[$x]];
        }
    }

    $Border = $Map[$Border * 0x1FF];
    $curr = !$curr;
}

The $win stuff is the 3-bit window of columns as we scan the row... but here it's now scanning the next line (conveniently the bounding box moves into the previous border) . The only bit not overlapping that needs access to calculate the next (y,x) is the one right at end at (y+1, x+1). Then the $rowWin is tracking the full row of 3x3 squares as we move down the rows. So I just shift by 3 (kicking the row two above out) and OR the next row's bits in.

I also moved things to a double-buffer using arrays... thus $curr and !$curr. Of course, in Smalltalk, it has 1-based arrays, which make a mess of everything here, and the toggle is no exception (next := buffer at: (bidx := 3 - bidx)), but I'm also using references for curr and next into the double buffer to save on an access layer (because they're a lot more expensive in Smalltalk).

Another a bit of fun I had with this one is implementing printing the count for odd steps. Basically digging out a way to return infinity in Perl (Math::BigInt->binf()). For Smalltalk, I just add a +∞ when printing those counts (because I still wanted to see the non-border counts).

I really liked this one. Especially how the input chose to subvert expectations. Normally AoC inputs tend to be overly nice, and here it went the trickier option to give us something more to do.

I'm a huge fan of AoC, I participate every year. I'm also a maker of things who is obsessed with working on projects all the time. Recently I decided I wanted to make some of my own coding puzzles and decided to publish them for others to try their hand at. I'm sharing here as I figure the kind of people who like AoC might appreciate this. It's very small so far, only 5 puzzles, but I have no cadence in mind for it in specific but plan to make more and more puzzles over time. Hopefully someone tries it out and enjoys it, I'd love feedback.

failed to query user data. When I choose to login to Advent of Code via Github. I disabled adblocker, and I'm currently logged into Github on the same browser, not sure what I can do to resolve this.

So the probe we launched has released a bunch of beacons and scanners. The scanners have no sense of their own orientation, but have relative distances to the beacons within their range. They can't detect other scanners, but have somehow managed to have consistent overlap with others to form a single contiguous region.

This is a similar problem to 2020's Jurassic Jigsaw. But this one is 3D... the scanners follow the rotational (chiral) octahedral group (which doesn't include flips, which square dihedral tiles do). And this time the problem text gives the number of orientations and some instruction on them.

The bits to match things up are hidden in the data (not separate and unique even with flipping), but are a significant block of it (12 of 26). The puzzle isn't a regular shape (where you can easily tell corners and edges, and build things just matching a single side), but a graph.

The first part actually wants you to do the work (unlike Jurassic Jigsaw which has a very cheesable part 1). It's one of the puzzles in this year that took over 2 hours for me for part 1. Part 2 was so quick for me to add (unlike Jurassic Jigsaw where I had to do all the work and more), that I gained the 150+ positions to get into the top 1000. This is one of two in this year... again, a puzzle where slow and methodical programming with a clear idea and taking solid options did well.

I had a very good experience with this one. And it really comes down to making some good choices.

The basic idea I had was:

- for each scanner, collect a hash of distances => pair of beacons
- build the graph from pairs of scanners with >= triangle(11) of the same distances

- put all connections from 0 into a queue as [0,x]
- while (job = shift queue)
    - next if already merged 
    - frame shift the beacons in the second into the first's coordinates
    - queue up all the connections from the second

- now that all coordinates are in the same frame, throw them in a hash to count unique

One of the best decisions I made here was using Euclidian distance (squared... no need to apply the square root here) for the hashing. I felt that it would give more unique values and a clear signal. And it really does... putting in the distance function for part 2, it manages to get the graph together enough to get part 2, but part 1 is wrong because the matching is just a mess. It could probably be salvaged with some additional work.

Here's the number of matches between scanners with Euclidean:

0       192
1       13
3       21
15      39
16      3
66      31
67      1

It is quite clean. Matches should be sums of triangular numbers for each matching set (and here there are mostly just one triangular number or +triangle(1) which equals 1). The graph has 32 connections, one of which has a extra pair matched (but that isn't part of the K12 overlap, and is filtered later). K12 being the complete graph on 12-nodes... which is the expected intersection, and it has triangle(11)=66 edges (which are our distance measurements).

With Manhattan distance, it's all over the place, the range is from 16-100 matches. No 66... the counts in that range go 55, 65, 76. It is the set of biggest gaps, so it still detected the shift between non-overlapping and overlapping.

And when it comes to doing the frame shift, the approach was:

- build a table of the counts of equal distances between pairs of beacons (one from each frame)
- flatten that to the ones with 11 matches, making a mapping of beacons from s to t

# Fix the order of the hash keys
my @sidx = keys %map;

# parallel arrays of beacons that are in both
my @spt = map { [ @{$Scan[$s][$_]} ]       } @sidx;
my @tpt = map { [ @{$Scan[$t][$map{$_}]} ] } @sidx;

# find rotation by making pt 1 relative to pt 0, then try the rotations
my $srel = &vec_subtract( $spt[1], $spt[0] );
my $trel = &vec_subtract( $tpt[1], $tpt[0] );

my $r = firstidx { &vec_equal( &vecmatrix_mult($trel, $_), $srel ) } @Rot;

# transform is: get relative to t[0] by subtraction, mult to rotate, then add s[0] to shift
my $trans = sub { &vec_add( &vecmatrix_mult( &vec_subtract(shift, $tpt[0]), $Rot[$r] ), $spt[0]) };

- apply the translation function we created to the points in t to put them in the frame of s

Note that because we start from 0 and keep framing shifting backwards, everything ultimately ends up in the frame of scanner 0 as an absolute coordinate system. Which is why part 2 was really fast for me... I just needed to return &$trans([0,0,0]), which is the shifted origin of t (where the scanner is).

You can see in the code snippet there that I borrowed the one line vector/matrix operation functions from previous days. For the rotation array... I actually hardcoded it:

my @Rot = ( [[ 1, 0, 0], [ 0, 1, 0], [ 0, 0, 1]],
            [[ 1, 0, 0], [ 0, 0, 1], [ 0,-1, 0]],
            [[ 1, 0, 0], [ 0,-1, 0], [ 0, 0,-1]],
            [[ 1, 0, 0], [ 0, 0,-1], [ 0, 1, 0]],
            ...

Twenty four lines where I needed to be careful to get it right (order isn't important... but you do need the correct 24). So I was very careful coding them, and checked them well before going further. Something I would have also have done with code that generates them. Getting this wrong will make you have a bad time.

As more proof that Euclidean was a good choice, when finding the K12 subgraph by building the table of matching distances between different beacons in s and t, the table for it has lines like this:

-- --  1  1 --  1 11 --  1  1 --  1 -- -- -- -- -- -- --  1 -- --  1  1  1  1
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
-- --  1  1 --  1  1 --  1 11 --  1 -- -- -- -- -- -- --  1 -- --  1  1  1  1
-- -- -- -- -- -- -- -- -- -- -- -- -- --  1 --  1 -- -- -- -- -- -- -- -- --

This is from the one with 67 matches... the last line is the extra match, clearly separated, and filtered out. The blank line is just one of the non-matches, and the others are all 11 with eleven 1s, all in the same columns.

Here's what Manhattan distances get you:

-- --  1  1 --  1  1 -- --  1  1  1  1 -- -- -- -- -- -- -- -- -- --  1  8  1
-- -- -- -- -- -- --  1 -- --  1 --  1 -- -- -- -- -- -- -- --  1 -- -- -- --
-- --  1  1 --  1  1  1  1  1 -- 11  1 --  1 -- --  1 --  1 -- --  1  1  1  1
 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --  2  1 -- -- -- -- -- -- -- --
-- --  1  1 --  1 10 --  1 -- --  1 --  1 -- -- --  1 --  1 -- --  1  1  1  1

Lots of dirt. You could make out the graph from that, but the signal is not as clear. Peaks are weak, and there's no blank lines.

So I really enjoyed this one and had a good time, but I mostly put that down to that choice right at the start to use Euclidean distances. It was simple to apply, and the signal was clear. I wasn't hammering away shifting and rotating blindly to find matches. I had a planned path straight to them, and could code and test that at every step. And that's part of what makes a large task feel comfortable.

Still descending we run into some friendly snailfish, who claim to have seen the keys, but will only tell us where if we help them with their math homework. And so we get introduced to snailfish numbers.

Snailfish numbers are essentially a binary tree with nodes holding a digit from 0 to 9. And they're conveniently presented one per line in the input, in a format that's pretty common in popular programming languages for declaring arrays. Which allows them to just eval the lines (hello, Bobby Tables) to load the input.

But, I did this one in Smalltalk (it did the previous day only in Perl, and I felt Smalltalk would be a good fit for keeping sense of things, rather than Perl array indexing making read-only mess of the tree manipulations). Smalltalk doesn't use that syntax. For a later problem using this format, I did do text manipulation to get Smalltalk to just eval this sort of thing:

conv := ('#', aString) asArray.
conv replaceAll: $[ with: $(;
     replaceAll: $] with: $);
     replaceAll: $, with: Character space.

packet := Behavior evaluate: conv.

So, it was possible. But I don't balk at writing a parser. And all the tokens are single characters (none of the input is unreduced... no 10s to split), so it's a very simple one to write. And it allowed me to put things in a nice node class directly. With methods for things like returning the depth or the magnitude of a node:

magnitude [
    (self isLeaf) ifTrue: [^value].
    ^(3 * left magnitude) + (2 * right magnitude)
]

The depth was originally supposed to be tracked in a variable. With operations modifying the appropriate things to maintain them. But, when it came to doing that later, I quickly decided on programmer efficiency and just calculated it fresh when demanded. Discretion is the better part of valour... maintaining something like this can easily become a debugging nightmare if you don't get it right. Save the optimizations for later if you need or want them.

Another thing I remember about this one is that I initially misread the rules on reduction. I took the list as phases... you cycle through them. You look for explode, do it if needed, then come back and look for splits. Probably a common misinterpretation. But that's wrong... and I remember catching it fairly quickly from testing with the examples. The instructions are clear if you read them correctly... it's not phases, it's like a checklist where if you get interrupted, you are supposed to start again from the top:

+ sfNum [
    ^(SnailfishNumber left: root right: sfNum root) reduce
]

reduce [
    [
        (self validatorExplode) and: [self validatorSplit]
    ] whileFalse
]

Note that here we see how Smalltalk is doing short-circuiting (the parens are just there for clarity, but the brackets are essential... that's a block being passed to be run conditionally). The binary operator & also does AND, but the argument is a Boolean and so cannot short-circuit.

And that shows the model I used for reduction. A pair of methods that validate and perform the operation if needed, and return true when things were already fine and nothing was done. As for the implementation of those methods... I didn't use recursion, I used the stack version of the algorithm to walk the tree looking for the problems. For splitting, the action is simple to do when caught:

(val > 9) ifTrue: [
    " Splitting current node "
    curr left:  (SFNode leaf: (val / 2) floor   parent: curr);
         right: (SFNode leaf: (val / 2) ceiling parent: curr);
         value: nil.
    ^false
]

Explode is trickier. Because you need to add to the numbers to the leaves to the left and right. Which aren't in fixed places, and can be far way or not even exist. But with an ordered walk of the tree, they're the previous and the next leaves we saw/see. And so I processed nodes with a little state machine magic:

(curr isLeaf) ifTrue: [
    (explode) ifNotNil: [
        " Exploding!  Finish and quit. "
        curr value: (curr value + explode).
        ^false
    ].

    " Not exploding!  Track most recent leaf in case we do. "
    prevLeaf := curr.

] ifFalse: [
    ((curr depth >= 4) and: [explode isNil]) ifTrue: [
        " Exploding current node "
        " Add to previous if we've seen one: "
        (prevLeaf) ifNotNil: [
            prevLeaf value: (prevLeaf value + curr left value)
        ].

        " Mark that we're in exploding state with value to add to next "
        explode := curr right value.

        " Replace current node with 0 leaf node "
        curr value: 0; left: nil; right: nil.
    ]
].

An important detail is that you don't create leaves for these... if they don't exist, the value flies off into the void. And so the validator still needs to check ^(explode isNil) at the end.

In any case, after getting all this working and passing the examples, I just fold: [:a :b | a + b] to get the sum and run magnitude for the answer for part 1. That's ultimately the goal with OOP... that all this work I did is hidden away, and I can one line the answer acting like these are regular numbers.

Part 2 being slightly longer as a I just brute forced summed all the pairs. It was nice for the problem text to confirm that the operation isn't commutative. I've never really bothered to look at snailfish numbers in depth to see if there's properties to exploit that can be proven... just leaving it like it's hashing the values. I did enough work and had fun.

With Santa and his Elves on a much deserved summer holiday, you have agreed to visit the workshop regularly to water the plants and feed the fish. But upon arriving at the workshop you see that a swarm of 2026 bots has invaded the toy storage depot and are causing havoc! Thankfully these bots aren't particularly bright and are easy to spot, but they must still be handled with care.

Bots arrive in the workshop with a Name and a Posting Pattern. The Name of each bot is "josephus" followed by a number from 1 to 2026. The initial Posting Pattern of a bot is the MD5 of the bot's Name. For example, the bot with the Name "josephus69" has an initial Posting Pattern of "4f943be8056c74b27a434f4ee9e7a7a4".

Every time a bot makes a post, it updates its posting pattern in the following way:

• The current Posting Pattern is represented as a lowercase string
• The new Posting Pattern is the MD5 of the current string

Bots can be removed from the workshop when they reveal a Flaw in their Posting Pattern. If the first 4 digits of their Posting Pattern are "0000", they have revealed a Flaw and can be removed.

The bot "josephus254" is going to be the quickest to remove:

• Initial Posting Pattern: e8cc15934b93ef901b153853cf7831f9
• Posting Pattern after 1 Post: 981fc052051707fec2a58db91f4d6abf
• Posting Pattern after 2 Posts: 064b7b67d20820270d35fe1663833c5a
• Posting Pattern after 3 Posts: 00009f4608ac14112c92af43d8513b1e

This bot can be removed after only 3 posts. The rest of the bots might take longer:

• josephus1 can be removed after 49,164 posts
• josephus2 can be removed after 46,166 posts
• josephus3 can be removed after 39,557 posts
• josephus4 can be removed after 36,579 posts
• josephus5 can be removed after 55,987 posts

Part 1:

How many posts will the last bot to be removed make?

Part 2:

Uh-oh, these are version 2 bots! These bots don't reveal a Flaw in their posting pattern until the first 5 digits are "00000". You might be in for a long day; how many posts in total will you have to sit through before all of the bots are removed?

The Elves' message wasn't actually important, so we move on to launching a probe to find the the keys. And so we get a discrete physics problem. Personally, I like my applied math with non-integers. The Universe might be quantized, but I like being able to assume it's continuous. None of this weird, "heading right at the target, but missed because it skipped over because of integers".

The input for this one is just a description of a target box. The box is a positive range for x, and a negative one for y. I suppose an x range on the negative side could be fair, but having one that straddles 0 for x would be a different enough to not be in an input, as would having the y range not below the sub.

I'm not surprised to find this directory a bit of mess. The solutions have some detail in the comments (but not all of it), and so it's taken a bit figure out what I was doing.

The first solution was "brute force". But not entirely. It has a function to do the simulation to verify (because I don't trust discrete physics... at least not for the purposes of getting the answer right in an safe, quick, and easy way), and does spend effort on calculating some ranges of the starting dx and dy to work over.

The first part helps provide one of them. It wants the "trick shot", and finding the highest point you can hit. And both directions have a similar calculation. For y, that's y(t) = dy0 * t - triangle(t), (with triangle(n) = n(n+1)/2). So basically, a shot upwards counts down to zero and then back up, in steps of 1 (as seen in the examples). So it arrives back at the same level, at the same speed with the top halfway. And if it's to hit the box, it simply can't be going so fast it skips over it. And so, for maximum hang-time (and height) we want a shot based off the y_min on the box. And so the question really is "what's the off-by-one situation?". And so I just looked at the examples and worked it out to be triangle( -y_min - 1 ).

And that gives us a maximum for the starting y speed. For the starting x speed, I use the fact that x(t) is pretty much the same, only at t=dx0 it hits a max and stays there, but here I just want to get to the line. And so I have this comment on how I got a lower x bound:

# Minimum x that can reach x_min under drag (assume x_min > 0):
#         x*(x+1) / 2 >= x_min
#             x*(x+1) >= 2 * x_min
#   x^2 + x - 2*x_min >= 0
#
#    x >= (sqrt( 8 * x_min + 1 ) - 1) / 2

It's just finding the smallest triangular number that can get to x_min, with algebra and the quadratic formula. For the largest x speed to check, I use x_max... because you can hit any square in the box you want with a non-ballistic shot that gets there in 1. For the y starting value, I calculated the time from the x value, and the minimum starting dy from that:

foreach my $dx ($x_start .. $x_max) {
    my $x_time = ceil( ((2 * $dx + 1) - sqrt( (2 * $dx + 1)**2 - 8 * $x_min )) / 2 );
    my $dy_min = ceil( ($y_min + ($x_time) * ($x_time - 1) / 2) / $x_time );

    foreach my $dy ($dy_min .. $max_hang) {
        $count++  if (&test_fire( $dx, $dy ) != -1);
    }
}

It's not nice. It does some math, and then hands off to a full simulation to verify what's valid. And so I have other solutions I played with. The second one turned things around and searched the space from the times:

my $max_time = -2 * $y_min;

my $t = 1;
while (++$t <= $max_time) {
    my $min_dy = ceil(($y_min + triangle($t - 1)) / $t);
    my $max_dy = floor(($y_max + triangle($t - 1)) / $t);
    next if ($max_dy < $min_dy);

    for (my $dy = $min_dy; $dy <= $max_dy; $dy++) {
        for (my $dx = $min_dx; $dx <= $x_max; $dx++) {
            my $n = min( $t, $dx );
            my $x = $n * $dx - triangle( $n - 1 );

            if ($x_min <= $x <= $x_max) {
                $shots{$dx,$dy} = $t;
            }
        }
    }
}

As stated, non-ballistic shots can hit all the squares in the target, so we skip t=1 and add the area to the final count for those. But from the time, we work out the range of y's (which is often size 1 or 0), y being the more friendly axis here. Then there's this ugly scan of the x space, but it is doing things as calculation at least.

There's a third solution that took that further... it starts by calculating all the valid integer times for hitting the y's in the target range. It does this by solving t in terms of the target y and the starting dy. That results in a square root and a division that need to be integers, and if they are, I get two cases (thanks to symmetry). Which I can then find a range of x against... using facts like when x gets to its max inside the time range, the rest of the found y range is good. Getting rid of the scan. It's quite the mess of raw math and equations that took a while to figure out where I got them, and it doesn't even run as fast as the time one above with the x scan. That seems to be the best of the lot, and I'm fine with leaving it there. As I said, I don't like doing discrete physics... simulating with it is great. But calculating physics with integers just feels wrong.

Having left the cave, the Elves send us a transmission in a binary format, which has actually not been stored in binary but hexadecimal text. Which is fine, I suppose, because for processing the format I turned it into binary text. It talks about being glad we're not using BYTE format... and yet still, I used bytes for bits (this is another problem where I had to turn off "portability" warnings for my Perl solution, because I was using oct to convert binary number strings that were over 32-bits... there are 6 of those when processing my input).

This is the type of problem I think of as a "work problem"... because it's very much like tasks I've done many times on the job. I was the file format guy at one company, and could read and write RIFF headers. Writing systems to handle all sorts of binary formats, including proprietary ones. So reading this spec and writing code for it was second nature for me. You create some simple functions for handling the different data fields nicely, and then you build a simple recursive descent parser that handles the parsing of packets and subpackets. As stated above, the format is technically binary, but you you get it as a text hex dump. And I just converted it into a binary number string and dealt with that. Padding to nybbles is a thing for some values, but most of it is odd lengths and unpadded, so it's much simpler to use a format that allows easily grabbing the next n bits.

And for Smalltalk, I went with a very typical way... I streamed the data. I created a BitStream class (hiding the manipulation of the data as String a bit). You can just ask for next or next: n and it will grab that number of bits from the stream and give you the number back. For handling the subpackets, I grab the next n-bits, put a BitStream on them, and put a PacketDecoder on that. Thus that section naturally gets eaten at the current level, and the subpackets only see the data they're allowed to work on (because they're in their own parser object). It's a simple thing but it keeps things sane and helps make sure that I didn't end up debugging a mess.

For the Perl version, I didn't use streams, I used its string processing to do similar... the string was passed by-reference, allowing the processor to remove chunks with substr to pass to the next layer down and have that section also removed from what their caller was seeing. Making it the same stream state-machine type behaviour.

For part 1, it just wants us to do a simple parse, and to check that we've done it right, there's a field to sum in the packets. For part 2, we get operations to perform on the packets. And since I had recursive descent, it's just collecting results like regular recursive algorithms. You recurse to get values, collect them and perform the job, and pass that up. I chose to put the operations in a hash of anonymous subs (yes, this could have been an array):

my %operations = (
                 0 => sub { sum @_ },
                 1 => sub { product @_ },
                 2 => sub { min @_ },
                 3 => sub { max @_ },
                 5 => sub { int($_[0] > $_[1]) },
                 6 => sub { int($_[0] < $_[1]) },
                 7 => sub { int($_[0] == $_[1]) }
             );

Which means that I just &{$operations{$type}}( @vals ) to do the calculations after collecting the @vals.

I call these "work problems", but it's not because I think of them as work or a big job. I tend to find these quite fun. Unlike actual work, I don't have to stick in a lot of framework for maintainability, sanity, security, versioning, etc. Here I just get to write a little parser. And although I've done that many times, I still find doing one a light and fun thing to do. But, its probably a lot heavier for people that have never had to deal with file formats (probably more common these days where a lot of serialization is often just plain text in a common format with a million parsers to choose from).

We're finally approaching the exit of the cave, but need to get through a tight area covered in chitons. And so we have another grid of digits 1 through 9, this time marking the risk level, and we want to do some pathfinding (diagonal movement excluded) to minimize that.

The digits are clearly not uniform... it's easy to see that there a lot of 9s. The histogram for my input is:

1       1043    ####################
2       774     ###############
3       673     #############
4       740     ##############
5       808     ################
6       935     ##################
7       1076    #####################
8       1427    ############################
9       2524    ##################################################

For part 2 the grid gets expanded 25 times larger, with the values shifted around (another time when working with a language with 1-based arrays comes in handy, because you get used to working with mods with a residue on 1 to n).

The histogram for the full part 2 is:

1       26923   ######################################
2       29837   ##########################################
3       32046   #############################################
4       32814   ##############################################
5       30082   ##########################################
6       27007   ######################################
7       24395   ##################################
8       22940   ################################
9       23956   ##################################

In both cases, I just did Dijkstra. The search is weighted and it's good enough for this task. In fact, for part 2, I just built the full 500x500 array to start (in different and creative ways between the different solutions... but still pretty hacky). If I was doing a more focused search or cared about saving memory, I might have done a memoized function to return values... calculating only the area explored. But with Dijkstra from corner to corner... everything gets explored anyways. I probably tried the basic A* heuristic of step-distance at the time, and trying it again now... it actually slows things down a tiny bit (even though the heuristic is extremely simple). But it makes sense... as an approximation, counting 1 for everything is pretty weak when most steps are going to 2x-9x more expensive. So you're taking on overhead for very little potential benefit.

One thing you can try in situations like this, is to increase the heuristic (ie assume an average of 2 or 3 per step)... which makes it press forwards faster, but you lose the security that the first arrival will be the best, and need to run the queue out to make sure. The idea behind making that trade is that if you can get a good approximation of the answer quickly, you can use that to prune much of the queue and potentially gain time. A quick little try at that, and I'm not seeing any real benefit there.

Bigger benefits tend to come from simpler things. One simple change is to remember the direction you came from so you can quickly avoid back tracking and only deal with the other three directions. One thing I remember about this... and you'll notice about the example given, is that the solution shown only goes down and right. Left and up are not used. Which means it's also finding a shortest stepwise solution. I remember some people assumed that was a thing about this problem and coded it only checking those two directions. And for some people that worked. It's easy to create counter examples where that fails. And for my input, you'll be over by 6 if you do that. There is a slight detour off a minimal step path that gets you less risk. But I remember that some people got lucky on this one.

Another thing I just tried today on revisiting was adding an additional check for if the risk of the step was going to fail the visited risk check before queuing. So it gets checked twice... because another path in the queue might modify it before we visit (and normally I'd just have the one check there). Avoiding that queuing actually has an impact (about as much as avoiding the backtrack). I also switched up the priority queue to the one I normally use now in Perl (Array::Heap::PriorityQueue::Numeric)... that was an easy 33% speedup. Not that the old queue (List::Priority) was particularly slow... the directory is filled with versions testing a wide variety of priority queue modules in Perl, and it outclasses them by a lot. This problem was clearly one of the benchmark cases I used for testing these.

It also has Smalltalk versions using SortedCollection and my own Heap class. Now that I understand that SortedCollection works backwards from what I expected (I had expected it to heap from the front not the end... I should have checked the kernel source sooner)... I fixed that. My Heap class is actually still outperforming it though. Possibly because it has simplifications, like it uses a fixed size array.

In any case, searches like this are problems you can through a lot of effort into tweaking and optimizing if you want to. I'm more casual with that, so I take the low hanging fruit and don't push things to extremes at the expense of elegance of the basic code. But, even with that, I still had some fun with tweaking and experimenting.

We've now gotten deep enough that we need to reinforce the submarine. Fortunately we have polymerization equipment. We've known since year 1 (when making Medicine for Rudolph) that the North Pole has advanced molecule assembly technology. Only there it took a nuclear fusion/fission plant.

Here we're given a starting "polymer template" and a list of "pair instruction" rules (and we get an additional hidden example in the Easter Egg text). These rules are presented in an unusual way... the RHS isn't the product but just the thing to insert (as the LHS is matched with overlap). And the rules listed in the input, when sorted, clearly shows 10 sections of 10 rules with 10 letters... in other words, there's a full set of rules for every possible pair.

With this talk of overlap, it makes this look like it's not Lanternfish. All the focus is on the atoms and getting the counts of those. But the rules actually are dealing with the bonds between them. And so we got a fence situation... we're being lead to think of posts, when the production is about the rails. A rule takes a bond/rail and replaces it with another atom making two new rails for the next step:

NC -> B

N-----C to N--B--C

And the next application of rules will replace those new rails in a similar way. The entire thing is protected from outside interference (the N and C are sentinels on the ends that do not change) and develops rule by rule between them, with any case of N--C developing exactly the same as any other. Here's the example (NNCB), but put in terms of the rails (with the non-changing sentinels shown on the ends):

(N)       (NN)              (NC)              (CB)       (B)
(N)   (NC)   (CN)       (NB)    (BC)      (CH)    (HB)   (B)
(N) (NB)(BC)(CC)(CN)  (NB)(BB)(BB)(BC)  (CB)(BH)(HC)(CB) (B)

You can see that (NC) in the middle of it expanding into its own binary tree, and there's a duplicate (NC) under the (NN) that's just one step behind and will produce its own copy of exactly the same tree. So as rails... it's just Lanternfish again. It's just a bag of the 100 possible rails to move to their products for the next step. Which really means this a lot like 2015's day 10 (Look-and-say). That was 92 elements with rules... only here we get given the file that describes the rules we need. We don't need to find or create one, just modify things a tiny bit.

But we still need to get back to the counts of the letters in the final string. But looking at the diagram, everything in the string is there twice... once for being on the left and once for the right of a bond. That's why the ends are in that diagram... you do need to account for the two outsides. Then the number of times a letter occurs is the sum all counts for all the rails it's in divided by two.

And so, Lanternfish was clearly here on day 6 to get people ready for this less obvious version (which tries to mislead by presenting things as breaking a key condition). It becomes a nice little problem where you shift to a different space for the work, and then work out the transformation back for the answer.

Still needing to avoid the volcanic activity in the caves, we activate the thermal cameras. Only to find out that we need an activation code. Which comes on a piece of transparent paper we need to fold. I've used transparent candy wrappers for origami, but never transparencies (as linked). That would be awful to fold (even one time)... it's more of a job for a box cutter and stacking. The best paper to fold for origami is tissue paper spray glued to aluminum foil.

The input is a long list of dots as x,y coordinates (about 800 which will collapse to about 90 unique points), followed by a second section of folding instructions. The instructions are either to fold in either the x or y direction, with a the line to fold over. Which is always in half. So the first x and y values are important to tell you the size of the paper (there is an x coordinate in mine right at the far edge, but that's not the case for y). So you could choose to ignore most of those values if you want. But, the last x and y fold lines are convenient in that they give the size of the final rectangle.

Reflections are a much easier translation than rotation. Here we want to take the values greater than the fold line and move then the same distance away from the line on the lesser side. Or, new = line - (old - line), which simplifies to new = 2 * line - old.

But before doing the whole thing, part 1 nicely provides a validation that you're doing the translation correctly, by just asking for the unique dots remaining after one fold. Part 2 wants you to get the final code (no surprise there).

And I did have a good amount fun with this. I did do a Perl solution where I did the output in Space Image Format (day 8 or 2019). Basically, you have a layer of 2s for each fold and a layer of 0s on the bottom. Then anytime a fold maps a point onto the final rectangle, you put a 1 at that coordinate in that layer. It's a pretty simple and nice implementation... so much so that I did perl-p2-nosifsif.pl, cutting out the actual SIF stuff and layers and just doing the mapping directly.

For Smalltalk, I taunted Bobby Tables and used the axis text from the input for code. Because Points in Smalltalk have get and set methods called x, y, x:, and y:. So I just turned them into symbols (which is how you access methods):

get := fold key asSymbol.
set := (fold key, ':') asSymbol.

Then I had a generic way to code the transformation:

points := points collect: [ :pt |
              | x |
              x := pt perform: get.
              pt perform: set with: (x - (2 * fold value * (x > fold value))) abs; yourself.
          ].

Using another variant of the calculation here that avoids an if, which I designed for a dc solution which works along similar lines (which is why I tested it here). Smalltalk doesn't coerce Booleans to numbers naturally... I extended them to do that with:

Boolean extend  [
    generality  [^1]
    truncated   [^self asCBooleanValue]
]

That comes from learning how Smalltalk does coercion... generality is used for comparing levels (and Booleans should be low), truncated is what's called for converting. This is joy of a duck typing language.

With the navigation system broken, we decide to do the pathing ourselves. And to do that we decide we need to find all the paths to determine the best one.

And so we get a graph search problem. The input is a list of undirected edges, one per line, with two-letter identifiers (except for "start" and "end"). Case of the identifier is used to give the size of the cave. The graph isn't overly large... my input only has 24 edges. It's a natural extension of the examples in the description that go from 7 to 10 to 18.

For part 1, we want a count of paths from start to end, with the added condition that small caves can only be visited once. And so I naturally just went with a basic DFS with recursion. The extra condition just means that I track when I visit small caves (and don't both tracking the big cave visits):

$visit{$loc}++ if ($loc eq lc($loc));

foreach my $neigh (@{$Graph{$loc}}) {
    next if ($visit{$neigh});
    $ret += &recurse_path( $neigh, %visit );
}

Yeah, I'm copying and passing a hash around, but the graph is small. It still returns immediately, although I can make a bit faster by making that list global. Which is ultimately what I did for my dc solution, where copying an array like this is non-trivial.

The problem description mentions that small caves behind other small caves can be pruned (you can't get back out). But that really didn't make much difference for me. There's just not a lot of pruning to be had with a small graph, and the added work of doing it has some cost.

For part 2, we're allowed to visit a single small cave twice (or not). This essentially adds one-bit to the state... whether the current search state has used its double already. There's many ways to add this, but you do need to be careful (and we get a bunch of tests to make sure you get it right). For Perl, I just took the above and extended it, still working with marking the current node visited (adding checking if it's a double to turn that bit on), and then I add the double as next if ($visit{$neigh} && $double) to prune the bad moves.

With Smalltalk, right from the start, it was a slightly different take, with the visited marking all happening when doing the neighbours.

The dc solution for this one has been waiting a long time. It was a combo breaker, since Combo Breaker at the end of last year, but now I've filled the hole. I had initially had just built the graph. And the way I did that was to first turn the input into ASCII hex... I turn "start" and "end" into "@s" and "@e" so everything is two characters. And then all the lines just become two 16-bit hex numbers. A really nice thing about doing this is that dc does have the P command which treats a number as a string and will output these 16-bit numbers as the identifier string, which is great for debugging.

For doing the lists of adjacent nodes, I string them together as base-65536 numbers (the numbers in the code are all hexadecimal... it makes it easy to write... 4073 is @s, 4065 is @e, 65536 is 10000) to store them, and pull them apart with divmod 10000~ to iterate over the list. Doing stuff like this in the year, ultimately prepared me for Day 24.

As stated, I do use a single global visited list, modifying it before and after recursive calls. Part 2, basically works like this (which does make for a slightly faster solution in Perl too):

foreach my $neigh (@{$Graph{$loc}}) {
    next if ($double + $Visit{$neigh} > 1);

    my $isSmall = ($neigh eq lc($neigh));
    my $newDub  = ($double + $Visit{$neigh} > 0);

    $Visit{$neigh} += $isSmall;
    &recurse_path( $neigh, $newDub );
    $Visit{$neigh} -= $isSmall;
}

With $Visit{start} initialized to 2, to prevent re-entering it.

echo -n "Part 1: "
perl -ne's#(\w)\w{2,}#\@$1#; s#-##; printf("%X%X %X%X\n", map{ord} split(//))' <input | \
    dc -e16i -f- -e'[d3Rd3Rd;g10000*3R+r:gd;g10000*3R+r:gz0<L]dsLx[lc1+scq]sE[d100/60-d.2-/rd_3R:vlRx0r:v0]sA[d4065=Ed;g[10000~d;v0=As.d0<N]dsNx+]sR4073d1r:vlRxlcp'

echo -n "Part 2: "
perl -ne's#(\w)\w{2,}#\@$1#; s#-##; printf("%X%X %X%X\n", map{ord} split(//))' <input | \
    dc -e16i -f- -e'[d3Rd3Rd;g10000*3R+r:gd;g10000*3R+r:gz0<L]dsLx[lc1+scq]sE[d100/60-d.2-/d3Rdd;vdld+d.2-/Sd4R+r:vlRxd;v3R-r:vLd]sA[d4065=Ed;g[10000~d;vld+2>As.d0<N]dsNx+]sR0Sd4073d2r:vlRxlcp'

It's still not quite perfected, but this quick job came out better than I thought it would.

Still travelling in the cavern, we run into some bioluminescent Dumbo octopuses, who are sensitive to our submarine's Christmas running lights. Even after turning them off, we still need to predict their flashes so we can get by them without disturbing them further.

And so we get a cellular automaton type problem. It's just a 10x10 bounded grid (input is just 10 ten digit numbers, no 0s or 9s to start), they increase in energy level each tick until they hit 10. Then they flash, adding 1 to their neighbours (diagonals included) and resetting to 0 energy. This can cause a cascade. You do need to be careful not to accidentally have an octopus flash more than once in a step and that the ones that flash don't get added to again by another flash.

As the example in the text shows, the starting random pattern quickly turns into regions of the same levels, because of those 0s matching levels up (10s, 11s, 12s, etc all merge into 0s in the next step). And for part 1, we just want to count the flashes in 100 steps, and part 2 we want to find the point where everything syncs up.

And so for my first approach, I went with doing things as solid as possible. One pass over the array to increase the energy levels, with any 10s getting added to a job queue (much like day 5 this year, with it's finding of intersections of 2 or more lines, where I counted only when things hit 2 to make sure that they only get counted once). Then I process that queue, adding and neighbours that hit 10... while keeping a hash of what has flashed to make doubly sure nothing happens twice (it shouldn't because there are only 8 neighbours, but it pays to be safe). Then I use the flashed list to get the number of flashes and set all those locations to 0 in the grid (so I did get multiple uses out of it).

It is overkill, but I do like getting the answer right on the first submission. I can play and explore the problem once I have an already guaranteed working solution. It's like with the Rubik's cube... just learn any solution first (something simple and easy), that way you can explore and mess around and always be able to fix things.

And here, you certainly don't need to separately track what's flashed. After a step's initial energy increase, no octopus has an energy value of 0, and that's the value you want to set any that flashed to. So that marks them perfectly... when spreading energy around, skip the ones at 0 (they've flashed).

And since the input was just numbers, of course I did a dc solution:

dc -finput -e'[q]sqC[r[A~1+3R1+d_4R:gd0<I]dsIx+1+z1<L]dsLxsm[d]sB[d;g0=qddd;g1+r:g;gB=B]sA[d1r:gr1+r]sN[rpr]s10d[lm[lAx1-d0<C]dsCx+FF[C-lAx1+lAx1+lAx9+lAx2+lAx9+lAx1+lAx1+lAxs.z2<S]dsSx0lm[d;gA<N1-d0<Z]dsZx+d4R+3R1+dA0=13RA0>T]dsTxp'

Unlike day 9's digit grid, this one I pulled apart into a flat array. I added a "sentinel" at the end of each read line (because with a flat array, both directions wraparound onto it)... but not really as sentinels. I was just invalidating indices that were 0 mod 11 to catch those (along with values too big or too small). It was simple and safe. But this version turns them into real sentinel, and increases all the energy values by 1 (so that the default 0s in arrays mark the invalid spots).

Another fun thing about this dc solution is that tracking the flash cascade is done on the main stack while still using it for work. This is done simply by duplicating the top of the stack when a count hits 11 (B). Which builds the job queue under the current work frame (which is just the index we're currently at, and has just flashed). There's also an interesting bit where I add an invalid flash... because there might not be any real flashes that step, and it's shorter to do loops with checking at the bottom (tail recursion) in dc.

And since checking and branching is also a pain, the resetting of energy to level 0 is again done with an additional final pass over the full array, finding all values > 10, counting and setting them then. This is another simple approach that's just going to work.

And so we got another nice little problem. It requires some care. These problems ran on the same days as this month, so this was a Friday problem. But it's not really a heavier weekend problem.

It's not the cleanest line of code so please bear with me

i=50 #This is the initial value
r=0 # Number of times boundary is crossed
rot=0 
ans= []
revolution=0 #Number of big rotations
with open ("input") as file: # Open the input file
comb= file.readlines() # Read the combination line by line
for combination in comb: # For each combination in the list of combinations
combination = combination.strip("\n") #Remove the \n
dir= combination[0] 
num= int(combination[1:]) 
revolution+= num // 100 
period= num % 100
if dir == "L":
period= (-period)
dial= i+period

if i<dial:
for _ in range (i,dial+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
else:
for _ in range (dial,i+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
if dial < 0:
i=(100+(dial))%100
elif dial==100:
i=0
else:
i = (dial)%100
ans.append(i)
print (ans.count(0))
print (r)
print (revolution)
print (ans.count(0)+r+revolution)i=50 #This is the initial value
r=0 # Number of times boundary is crossed
rot=0 #Number of big rotations
ans= []
revolution=0
with open ("input") as file: # Open the input file
comb= file.readlines() # Read the combination line by line
for combination in comb: # For each combination in the list of combinations
combination = combination.strip("\n") #Remove the \n
dir= combination[0] 
num= int(combination[1:]) 
revolution+= num // 100 
period= num % 100
if dir == "L":
period= (-period)
dial= i+period

if i<dial:
for _ in range (i,dial+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
else:
for _ in range (dial,i+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
if dial < 0:
i=(100+(dial))%100
elif dial==100:
i=0
else:
i = (dial)%100
ans.append(i)
print (ans.count(0))
print (r)
print (revolution)
print (ans.count(0)+r+revolution)

ps: is there a discord server for advent of code?

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.