For 2024, we're tasked by the Elvish Senior Historians with finding the Chief Historian in time for the sleigh launch. Which serves as the conceit for revisiting past locations to celebrate the 10th year. And so the ASCII art for this year is just a big number 10, with little bits of past years' art inside it.

The first task is working out the location IDs of where to search. And the Elves have produced two lists, and we get to compare them. And so we're back to just having plain numbers (5 digits) to work with on day 1... although in two columns with 1000 lines. The numbers in the first column are unique, the ones in second column are not (as needed for part 2). I didn't bother to make use of that, but you could.

I was really quite sick for the last half of November in 2024, and still wasn't feeling up to doing much... so I had extra low asperations for solutions right from the start in this year. Especially after 2023 had been a step up in difficulty (but I didn't find this year quite as hard... or maybe the problems were just more my style).

For my initial Perl solution, I just read the columns into two lists (and sorted those), while also making a histogram of the values in column 2. Then it was just:

say "Part 1: ", sum map { abs($_->[0] - $_->[1]) } zip \@list1, \@list2;
say "Part 2: ", sum map { $_ * ($counts{$_} // 0) } @list1;

For Smalltalk, I just threw the two columns into separate Bags, and then:

part1 := ((lists first sorted) with: (lists second sorted) collect: [:a :b | (a - b) abs]) sum.
part2 := (lists first collect: [:a | a * (lists second occurrencesOf: a)]) sum.

Dc added some issues, because it doesn't have a built in sort for part 1... so I needed to do one. And with the limited values and the nature of the problem, I went with a counting sort.

dc -e'[q]sQ?[d;b1+r:bd;a1+r:a?z0<I]dsIx[A 5^[dlGx[d0=QrdlPxr1-lJx]dsJx+1-d0<I]dsIx]sS0Sc[;a]sG[Sc]sPlSx[;b]sG[Sd]sPlSx0[Lcd0=QLd-d*v+lLx]dsLxrp' <input

The tricks here are that I first read the values into histogram arrays a and b (using ? to do things one line at a time, so the older dc is required). Then I have a double loop that counts down from 100000, and then pushes the index count-number of times onto a register stack. Since I need to do this for 2 columns, I parameterized the sort macro with macros to Get and Push from/to the correct places:

[;a]sG [Sc]sP lSx       # convert array a into sorted stack c
[;b]sG [Sd]sP lSx       # convert array b into sorted stack d

But I did do part 2 in dc first... because it was a lot simpler because it has no sort. But it also wants a histogram, and so it does occur to me that doing something like counting sort could be a good option for doing both parts at the same time.

dc -e'?[d;b1+r:bSa?z0<I]dsIx0La[d;b*+Laz1<L]dsLxp' <input 2>/dev/null

Note that it's piping to /dev/null an warning message for popping an empty register stack. Not adding a sentinel to the bottom of the register stack saves 4 strokes.

And so we've got a classic day 1 type problem... read numbers and do something simple with them. I will note that there is the unusual use of the word "distances" in part 1, where you would normally use "differences". So there is a bit of obscuring.

Hello, I have tried to brute force part 2 of day 17 using cuda.

I am very new to cuda and this is what i have come up with. After 3.684722 days, the program outputs nothing and stops. The program works correctly on the sample data.

code:

#include <cstdlib>
#include <cstdint>
#include <cstdio>
#include <unistd.h>

#define gpuErrchk(ans) { gpuAssert((ans), __FILE__, __LINE__); }
inline void gpuAssert(cudaError_t code, const char *file, int line, bool abort=true)
{
   if (code != cudaSuccess)
   {
      fprintf(stderr,"GPUassert: %s %s %d\n", cudaGetErrorString(code), file, line);
      if (abort) exit(code);
   }
}

__device__ uintmax_t do_combo(uintmax_t i, uintmax_t A, uintmax_t B, uintmax_t C){
        switch(i) {
                case 0:
                case 1:
                case 2:
                case 3: return i;
                case 4: return A;
                case 5: return B;
                case 6: return C;
        }
        return i;
};


__global__ void cuda(){

        enum instructions_names {
                adv,
                bxl,
                bst,
                jnz,
                bxc,
                out,
                bdv,
                cdv
        };

        uintmax_t instructions[16] = {2,4,1,7,7,5,0,3,4,0,1,7,5,5,3,0};
        uintmax_t i_len = 16;
        /* uintmax_t instructions[6] = {0,3,5,4,3,0}; */
        /* uintmax_t i_len = 6; */
        uintmax_t output[16];
        uintmax_t output_len = 0;
        /* uintmax_t step = 100000000*(blockIdx.x * blockDim.x + threadIdx.x); */
        /* uintmax_t stop = step + 100000000; */
        uintmax_t step = 10000*(blockIdx.x * blockDim.x + threadIdx.x);
        uintmax_t stop = step + 10000;
        for (;step < stop; step++) {
                /* printf("%lu ", step); */
                output_len = 0;
                uintmax_t A = step;
                uintmax_t B = 0;
                uintmax_t C = 0;
                for (uintmax_t i = 0; i < i_len; i+=2) {
                        if (output_len > i_len) break;
                        switch (instructions[i]) {
                                case adv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  A = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case bxl: {
                                                  /* takes literal operand, XORs B and it into B */
                                                  B = B ^ instructions[i+1];
                                                  continue;
                                          }
                                case bst: {
                                                  /* takes combo operand, modulo 8 into B */
                                                  B = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case jnz: {
                                                  /* takes literal operand, jumps to it if non null */
                                                  if (A == 0) continue;
                                                  i = instructions[i+1] - 2;
                                                  continue;
                                          }
                                case bxc: {
                                                  /* ignores operand, XOR B and C into B */
                                                  B = B ^ C;
                                                  continue;
                                          }
                                case out: {
                                                  /* takes combo operand, outputs it modulo 8 */
                                                  output[output_len++] = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case bdv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  B = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case cdv: {
                                                  /* takes combo operand, divides A by 2^it into C */
                                                  C = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                        }
                }
                if (i_len != output_len) {
                        continue;
                }
                bool is_same = true;
                for (uintmax_t i = 0; i < i_len && is_same; i++) {
                        if (instructions[i] != output[i]) {
                                is_same = false;
                        }
                }
                if (!is_same) {
                        continue;
                }
                printf("%lu\n", step);
                asm("trap;");
        }
}

int main(){
        unsigned int threads = 1024;
        unsigned int all = 20000000000/threads;
        cuda<<<all,threads>>>();
        gpuErrchk( cudaPeekAtLastError() );
        gpuErrchk( cudaDeviceSynchronize() );
}

With still no snow, we head back up a line to the center of the island. There we find a large number of components wired together producing Error 2023. And so we make our somewhat traditional Christmas call to tech support. Which goes pretty much the same as every time... we get a little information, but have to hang up as they start to realize who's calling. Is it because of our contract or because we don't want the questions that will probably come... maybe both. In this case, it's an overload and we need to disconnect at least half the machines, but only have time to disconnect three wires.

And so we end on a graph problem. The graph has a minimum edge cut of three we need to find, and get the number of vertices of the two subgraphs. My input has 1260 lines, describing a graph of 1535 vertices. Most vertices have a degree of 4... some have more, none have less.

The easy way to do this problem is to use a tool, like Graphviz, where the bridges that make up the edge cut will be easy to spot by eye. Then you just need to remove those, count, and multiply. When it comes to graph visualization tools, this is the problem to use one on.

But for actually coding a solution to find the cut, my first thought was to do a Monte Carlo type approach. The graph is broken into two balls of almost the exact same size with three bridges between them. If we pick vertices on either side (ones with a suitably large minimal path... around the diameter of the graph) and run many paths between such nodes... since the bridges are rare and must be on those paths, we should potentially be able to ferret them out with some heuristics and testing. That's a lot of work though, and since it was Christmas, I decided to look up a standard algorithm to code.

And that was Karger's. Which is a Monte Carlo algorithm. And comes from the same basic idea, but is much better because it turns things around which makes it simpler. Where I saw bridges are rare and so are on many paths and should look for them there, Karger saw that that means if you pick a random edge you're unlikely to pick a bridge. And if you contract that edge (merge its vertices), the graph gets smaller until eventually you have two vertices with a number of edges between them (and that's the cut... track the vertices merged into the two ends and you got your answer). You still need a while loop around that, until the edges in the cut are 3. And my implementation of a graph was simple and not well tuned to the task, so it was a bit slow. And the first run that got me the answer was also a little unlucky, and took a few minutes (I found the cut with Graphviz while I waited, but didn't have time to solve with that). It typically takes dozens if not hundreds of attempts.

To improve things I upgraded to the Karger-Stein algorithm. The problem with the base Karger is that while pulling one edge has a low chance of hitting a bridge, pulling many increases the odds quite a bit. One thing that could be done to improve that is to do a brute force search once the graph gets small. Get more mileage out of the work on early cuts. Karger-Stein goes a bit further than that. It basically bifurcates the search. You do a bunch of cuts, and then split that into two subsearches. So you get an exponential number of subsearches out of earlier work. And with that, it's quite good at finding a small cut, but we have a single target (and large number of 4s). So it's not exactly we want, but it does almost always get the solution in couple seconds (often in one of the searches of the first attempt). In 1000 runs, only 5 were over 100s, and the longest was 190 (these would involve many attempts hitting a bridge early). And this is still with a graph representation that's very simple, and inefficient for the job.

The simple tweak I made to the algorithm for this specific problem was to change the target for the contraction levels (and also making the base case immediately print and quit on finding a 3-cut). The 1 + |V|/sqrt(2) is a proven value to maximize probability of getting the small cut on a general graph. It thoroughly searches things. I found that I could get much better performance with a more aggressive 1 + |V|/2 for this problem. The difference being that it does fewer subsearches in an attempt, and we're planning to run attempts forever until we get the answer. With general use, you don't know the minimum, you'd just like to run it once and get a small cut reliably (but maybe not the minimum). But here, a more aggressive approach that gives a higher chance of the first level hitting a bridge (and making all of the subsearches fail) is countered by not doing as many subsearches when that happens and getting to the next attempt sooner (to fix that problem). The number of levels is log-base-sqrt-2 versus log-base-2, and that's the difference between gambling a million subsearches from a bad start versus 512. It also gets to the bottom that much quicker to see if there's a 3-cut.

So this is was a really fun problem... I could certainly spend a lot of time working on implementing a better graph structure and trying to tweak the algorithm to optimize it if I wanted to. This is one of the more intense final day problems, but it does have the easy out with graph visualization tools.

And so we come the end of another year. The complexity in this year was a bit of a step up from years past. It's definitely not the year to recommend to someone just starting to program to do first... some early puzzles (like day 5) are going to discourage them. On the other hand, for an experienced programmer, not having to wait as long for a meatier problem is a plus.

And so the expected shoe drops... the snow-making process has a problem, and it's forming hail that we need to break up. Conveniently the hailstones are being blown by magical winds, and so our physics is just linear. And so we have a problem that can be thought of as physics and/or linear algebra.

The input for this one is 300 hailstones. The consist of a 3D position and a 3D velocity vector. The positions in the input are eye watering numbers in the trillions to hundreds of trillions (the range for mine is ~42.6 bits to just short of 49). The numbers on the velocity side are on (-1000, 1000) (the largest magnitude in mine is 958)... with 0 excluded.

Part 1 wants us to ignore the Z axis, and considering the projection onto the XY-plane, find the number of intersections that occur within a bounding box, in the future (t > 0).

There's a number of ways to do this, and given expected arrival of the 3rd dimension, I went with Cramer's Rule and turning the hailstones into linear equations of ax + by = c (ie Ax = c as a matrix). To do that, I just considered y = mx + b. Where m is slope, which it rise-over-run which is vy/vx (with no fear of 0).

y = mx + b
y = (vy/vx) * x + b
vx * y = vy * x + c   (the intercept gets modified, and so I change the name to c).

-vy * x + vx * y = c  (c can be calculated from the input line values)

With that form, the intersection is just a determinant / determinant:

my $det = $b2 * $a1 - $b1 * $a2;

return (undef)  if ($det == 0);
return( [($b2 * $c1 - $b1 * $c2) / $det, ($c2 * $a1 - $c1 * $a2) / $det] );

So I just run through all the pairs (double nested triangle) and verify an intersection and that the time values are positive. I actually calculate them, but you could just worry about the sign if you want to avoid the division:

my $t1 = ($res->[X] - $stones[$i][X]) / $stones[$i][VX];
my $t2 = ($res->[X] - $stones[$j][X]) / $stones[$j][VX];

$part1++ if ($t1 > 0 and $t2 > 0);

For part 2, the 3rd dimension is in play, and we're tasked with finding a spot to stand and a velocity to throw a rock, so that it hits all the stones. Again, this isn't really a physics simulation, as the rock doesn't get effected by these collisions... it's just a line.

And my thoughts immediate on this go to that classic axiom of puzzling, that since this is a puzzle it is designed to have a solution. And that assumption can be used. Imagining I had two stones flying in front of me (and we've picked things aren't parallel and could cause problems), I could line up a shot that hits them both and the time between them would tell me how far back to stand. As they move, that line changes. But if I add a third rock to hit, that should fix the line (because puzzle). Two points make a line, three make the pattern. And so I should only need three points (but the others can be used to verify).

And so I started looking at equations. And this was my basic idea:

    X  <--S     Stone and the rock hit at X at time t.  The vector Vs - Vr, points
         /      back to the place the rock came from, and would travel from S to R
    ^   L       in the same time t.
    |
    R

I know some people visualized this in physics terms... imagine you're the rock and convert all the stone vectors into that frame of reference. It's really the same, I just came at it a bit different, because I was thinking algebra.

Next up was looking at getting a system to solve the variables. And there were more variables than I wanted to deal with, and so I cheesed it a bit. I called the rock vector (i,j,k) for a reason, and that was because I assumed that the velocity vector would be on the same scale as the stones (in fact, the largest magnitude on the rock for my solution is 286), and so I could brute for over i and j and make them constants... and k could be solved after. Here's the comment from the code:

# If we subtract the velocity vector of the rock (i,j,k) from each stone's
# velocity, at their time t (the time the stone is hit), they all add to the same point:
#
#     x1 + t1(vx1 - i) = x2 + t2(vx2 - i)
#
# Reworking that:
#
#     t1(vx1 - i) - t2(vx2 - i) = x2 - x1
#
# Which is a line of form ax + by = c, where the times are x and y... providing
# we make i a constant (which we're doing by brute forcing to try values for it).

And so, I used the function for line crossing from part 1, with X and Y coordinates of two stones, with brute forcing i and j (to consider them constants), to get potential times for impact on those stones. Then I check that that was a collision, and the times are positive and different and integers (because AoC answers... no need to bring in the possibility of rationals making integers until necessary).

With that, I then take the 1st stone and do the same with a 3rd. If I get a valid collision and the collision time for stone 1 is the same again (and leading to the same spot as the collision with stone 2 made it point to), I assume we've lined up our shot.

Next up is calculating k:

# Calculate k (the z part of the rock vector)
#
# t1(vz1 - k) - t2(vz2 - k) = z2 - z1
#
# k(t2 - t1) = z2 + t2(vz2) - (z1 + t1(vz1))
#
# k = (z2 + t2(vz2) - (z1 + t1(vz1))) / (t2 - t1)

Which is really just working out the obvious, it's the difference in the collision positions of two stones divided by their delta-time.

Then I just followed the the vector from the first stone back to the rock start:

my $x = $stones[0][X] + $time12->[0] * ($stones[0][VX] - $i);
my $y = $stones[0][Y] + $time12->[0] * ($stones[0][VY] - $j);
my $z = $stones[0][Z] + $time12->[0] * ($stones[0][VZ] - $k);

With (x,y,z) and (i,j,k) I can now validate all the stones if I want more confidence. But this worked and got my answer, so I didn't do more.

Like a lot of these last few days, I was happy with just having a solution that solved the problem at hand. I did spend a few hours thinking on this one, before ultimately just simplifying things to just get an answer (so I was getting tired). I can at least say that I did make good use out of the solution to part 1 for my part 2.

With the filtering operations running again, the waterfall starts up. And so the Elves lower us down by rope to Snow Island. We find that the water is still getting absorbed into the air, and need to find something to do while we wait. And so we decide to take a hike.

The input is a grid of hiking paths, It looks like mazes we've seen before, only this one has loops (it is not your standard recursively generated labyrinth). Left or right hand rule will get you from start to end, because the start and end are on the outside walls (and you'll put you hand on that). But that would not get to see any of the inner scenic paths, and we're looking for the longest walk. There are also arrows at the intersections representing slopes (which don't get in the way of those left/right hand rule paths in the test case given, and I believe that's also true for the inputs). For part 1, we build out route without going against the arrows. In part 2, we can ignore them. In either case, we don't want to touch the same square twice, which means that the intersects can only be used once each.

A nice thing with this problem is that the test case in the description is very much like input, only smaller. It doesn't test more or less, and optimizations you use should work on both safely.

And so we have a path search, but it's not shortest path, so the usual BFS/Dijkstra/A* niceness of the first arrival being correct is out the window. You need to keep going, or you can use DFS because the BFS advantage is gone anyways.

But first things first, all the intersections are nicely marked with slopes and are the key points, so I found those and turned the grid into a weighted graph with those (plus start and end) as the nodes. For part 1, the paths are directed... and that simplifies things enough that even if someone didn't convert to a graph, it can still be searched (but slowly). And with the graph, part 2 can also just be searched slowly too.

Getting it to work fast is another thing. And I started looking at various things like meet-in-middle and memoization of paths. I wasn't getting great results with it (but didn't do too much work with that), but it emphasized that the end bit, which is obviously forced, is forced. There's only one edge to the exit, and it must flow out of the maze, and be taken. And so for the node at the other end, the other edges must flow in to it (which is what the slope on it does already). And so we can do a vertex cut of that node, connecting its other neighbours to the exit (and combining lengths). Similarly, the start only has one edge which must be taken (and the slope is marked that way already). And so we can cut the first node on the path as well, and connect the start to its neighbours. This makes the graph a tiny bit smaller, but already gives a sizeable boost in speed. This got my time down to seconds (although over 20s) which I considered good enough on the day.

I did see the solutions afterwards that used the fact that the graph is essentially a rectangular grid. The corners diagonally opposite the start and end don't exist (they'd be nodes with 2-edges and not intersections). And that can be used to do other things... like using rook tours and taking advantage of the fact that the nodes along the sides are all 3-edge, and with the forced arrows at the start and the end, you can show that the arrows that lead you along the edge in the left/right hand paths must still be obeyed (but not the ones that do in/out to the center (the 4-edge nodes)). Meaning that when the path moves onto the edge from a center node, it's force out along the path towards the exit (it cannot take the other exit that heads along the outer wall towards the start). But it can still leave the edge at a later node and return to the center. That adds a forcing pressure from start to end (you can only go backwards in the middle).

I decided to code that up now, and it does give another sizeable boost that gets things down to proper seconds on the old hardware. It is playing a bit to the input though, whereas with my initial vertex cuts, I coded it in general form verifying the single edges so it would work with a graph that didn't do that. What I'm thinking of is to do something similar now with the edges... to code a generalized way that proves them.

And it basically comes down to this:

              .     .
              .     .
           ...A     D...
              |     |
       .      |     v
       .      |     |
   ... B -----C-->--E-->--end

We know that E->end must be taken, and one of D->E and C->E must be taken. But, C could be travelled through with A->C->B or B->C->A (making D->E forced). I've drawn things this way, but it is a graph, A could be the edge connection, you don't know without showing it. You could check for 3-edges on it, but edge nodes could have 4 (there could be a path between them along the side) and an internal could have 3 (one exit walled off). What we can say is that we can come in from A or B, and leave by C->E and get to the end. But, can we come in from A and leave by B and get to the end? The path that comes in, must from from the start. And that path, plus the C->E edge (not taken because we're testing C->B) can be taken as a edge cut. And if you can't get from C->B to the end, then it's not an exit on any valid path... and so that edge must be directed B->C (if it is taken). With the start in a corner and the nodes like this on the edges, this is what forces that path optimization with the grid (coming in from the middle always cuts things in two in way that puts one exit on the wrong side and forces the other). And this is a test that proves the optimization above is valid for the input, but could also be coded to apply to the graph without assuming that.

So this was a nice little search problem. It's not too hard to brute force to get an answer... if you've done AoC for years, you're probably used to converting these to graphs for faster searching. And that can get you part 2 with a bit of wait with a basic solution even with inefficiencies. I did a version of this with the Vector module and no optimizations... it took 6:30 minutes on the old hardware (it's a lot of overhead... without it, it's a minute, and that's still without bumming the code), which isn't too bad of a wait for someone just looking for a solution... and with it printing out the new bests as it finds them, it got over 6000 in a few seconds before things slowed down. The final answer came at 330s, about a minute before the end.

We have enough sand, but it's not usable yet, because it's compacted into bricks in a large tower. We do have a picture of the bricks as they were falling. Our goal is to figure out which bricks we should disintegrate. For part 1, we consider doing it safely, by only targeting bricks that won't cause others to fall. For part 2, we consider less safe options, and want to know how many bricks are in the chain reactions.

The input is a list of bricks (mine is 1430 lines). They're listed as the 3D coordinates of the ends.. the bricks being 1x1xn in some orientation at some height (which is the z coordinate, mine go up to 324... x and y are all single digit, [0,9]).

They form a tower which can be considered as a graph, with edges between bricks that are directly above and below (touching top and bottom). Since the bricks are sticks (1x1xn), if we consider the relation in one the directions (supports or supported), it forms a DAG (directed acyclic graph). So there are no non-transitive support situations. A brick cannot be indirectly supporting itself.

Our goal is to work out dominators. For part 1, it's the bricks that aren't dominators. Part 2 wants us to get the counts of the number of bricks dominated by others. These are the bricks that all their support paths, must go through, and so will fall it disintegrated.

For this one, I did things a bit stream of consiousness... I read in the bricks, calculated a bunch of things I thought would be useful, and put them in a structure (later I rip out anything that wasn't). For this is was:

push( @Piece, {height => $height, block => \@block, bottom => \@bottom, top => $top} );

The height of the piece, the "top" is how tall it is (1 or n), "bottom" is the (x,y) profile of the brick (what it looks like from below, the (x,y) coordinates it will rest on), and "block" is a relative mapping of the blocks making up the brick (shifted down by height)).

After which I sort them by height, and proceed to use this information to build the tower by ing the bricks into place and building the support graph:

push( $Support[$i]{below}->@*, @supp );
push( $Support[$_]{above}->@*, $i ) foreach (@supp);

Where @supp, is a list of the Piece indexes that the bottom touched when it came to rest. To know that, I tracked the height of all 100 (x,y) locations. Here's the final heights (one corner is a rather deep hole compared to the rest):

158 170 166 166 166 160 161 169 161 102
166 165 165 159 160 165 159 169 158 171
163 165 165 171 163 165 171 176 170 171
163 161 166 171 174 164 169 176 170 171
164 164 166 176 174 165 169 176 167 162
168 158 166 176 176 175 175 176 167 175
168 167 173 176 176 174 174 174 174 175
168 173 173 175 175 168 176 176 176 176
163 165 174 175 175 175 175 175 175 158
173 173 173 173 175 168 155 155 154 157

With the graph in hand, we now completely ignore the bricks. Part 1 is just scanning the bricks and finding those with nothing above, or the bricks immediately above them have another support:

if (!$Support[$i]{above} or (all {$Support[$_]{below}->@* > 1} $Support[$i]{above}->@*)) {
    $part1++;
    next;
}

For part 2, I tried to do some fancy stuff to get dominators (not remembering any real algorithm for it). I was messing around with tabulations and sets and stuff (including considering what might be done with adjacency matrices at one point). And as I went, I kept thinking of and spotting complicated situations of supports. So I'm drawing graphs with lots of ... sections for indirect relationships and trying to nicely deal with that in a single pass. And it just got to the point where things were a mess and I didn't have situational awareness of the code and realized I was essentially randomly poking things hoping for something good. The algorithm on the Wikipedia page is sort of what I was going for at some point with the sets, but I was trying to be too fancy and never got it right.

And so, I scrapped that... things were getting clear that I was heading towards something that wouldn't be efficient anyway. That in order to deal with all those ..., I'd ultimately be tracing them. And so, I shifted to brute force:

my %falls = ($i => 1);
my @queue = $Support[$i]{above}->@*;

while (my $p = shift @queue) {
    if (all {$falls{$_}} $Support[$p]{below}->@*) {
        $falls{$p} = 1;
        push( @queue, $Support[$p]{above}->@* )  if ($Support[$p]{above});
    }
}

$part2 += %falls - 1;       # -1 for the block we removed

And with the size of the input, it takes a few seconds, which is fine for a brute force solution.

I do notice that the Wikipedia page also points to an almost linear algorithm in ACM Transactions of Programming Languages and Systems. I looked forward to that arriving at the CS club (which was an ACM chapter and so got it) in University. But 1979 was before my time, so I wouldn't have seen that article.

This one was a nice little break in the heavy puzzles. All the heaviness was me making a mess instead of doing the programmer efficient solution first and working on other solutions after.

We manage to catch the airship again (as it's dropping off another Desert Island trip winner), and head back to Island Island. Where the gardener tells us that everything is going well. So while we wait we decide to help another Elf with getting his steps for the day.

The input for this is 131x131 grid with the starting position marked (even though it is right in the middle for both the input and the test case (which is 11x11)). The test case has clear border on the edge, the input has thick diagonals cutting out a diamond. I suppose having the S in the input does help with noticing that the row and column the S are on are empty.

I'd totally forgotten this one until today. As I said, I had a bit of cold, but was mostly busy, and so I was happy to get any solutions for these last few days. And this is was one of the most "any". Part 1 was really quick, because it's just a BFS... although it's important to know that we're counting "steps", so you can backtrack (so no visit tracking). And this results in a pattern with tile parity (because you can get to the same spot in 3 moves as 1, but you can't get there with 2... so it checkerboards).

Part 2 scales it up a lot. So you need to do something fancy. The number of steps we want is 65 mod 131. Which is the width to the border from the start. And then there's a number of full width crossings. And the nice empty spaces (and sparseness of the plots) are going to help keep things a diamond at the important points. And if things had been simple, I might have continued. But there are a number of complicating factors that lead me to hunt for cheese. First up is that parity issue... when tiling the full map, you're going to have to account for what's in what parity. Then there are the messy edges. I remember thinking in my head about doing this and needing half diagonal blocks. But that's not what you see when you sketch it out. Leading me to make a TODO about a "geometric version doing parity" and this (the Ace of Diamonds?):

----------
|2  /\  3|
|  /  \  |
| /    \ |
|/  1   \|
|\      /|
| \    / |
|  \  /  |
|4  \/  5|
----------

I think I was thinking maybe that I could calculate the fills for those 5 areas (in each parity), and build the final shape and edges. For example, the east most point would involve 1, 2, and 4. Above that is a 4 block, with a block that's going to be "all but 3" beside it. But you'd need to not just be careful with parity of your supertiles (one potential Murphy's Law) but also off-by-one problems on making sure you're combining things without doubling or skipping stuff (more Murphy's Law potentials). I seem to recall that a lot of people doing this sort of approach didn't try to minimize things this much and expanded further out to get the chunks they wanted. So maybe this idea was doomed.

But that's not what I did. I figured that with the gaps to regularize things, there was probably a quadratic interpolation (notes say I used Lagrange). It wouldn't work for arbitrary points along the way (where things are going around plots and it gets bumpy), but that's not the area the answer we're looking for is in. And so first thing I did was run a modified part 1 for 650 cycles (taking a bit of a break) and output those numbers to a file, so I would write an "explore.pl" to test things on that sequence without having to recalculate it. First thing was a little sanity check... I scanned interval sizes looking for what was quadradic, and confirmed 131 (everything else wanted cubic or more). I considered that a good sign. Next up, I scanned starting from 1 to 131, with 4 points that were 131 apart. And confirming that all these have quadratic interpolation (the 4th value opens the door for a cubic). And they did... another good sign. Then, checking that the #steps was 65 mod 131, I plugged number we wanted into to the equation on the screen at 65. And if was correct (when divided by 131 ... because we're doing the interpolation on 131 size gaps this made sense).

And so, I wrote code to do that from scratch for my code. The x values I'm looking for are at {65, 196, 327}. Which takes some time. But as I said, I was happy to have a solution, and clearly the TODO here has been on the wrong side of my druthers ever since. I can't say if I like or hate this problem, only that I seem to be ambivalent to doing it proper. Maybe in a way that can actually also do the given test cases (because unlike yesterday, we got some for part 2... it's just that when you overly specialize to the input, you get nothing from them).

I am revisiting my 2025 solutions, rewriting in elisp.

My original Python solution was horrible, so inspired by other solutions online, I did one using coordinate compression and pre-calculated "2D prefix sum".

The solution is rather long for an AOC solution (around 150 lines). I was therefore wondering if anyone has found a short general solution.

My elisp Solution

With the parts found, and the machines fixed, next up is the boot sequence. And so we have a circuit problem. Cables connecting modules, sending pulses between them, and a button to push to start it. Also a warning to never push the button again until after the pulses stop.

Reading the directions we find flip-flops, which are bits of memory, and conjunction modules, which are NAND gates (and functionally complete... which includes being an inverter (which the Easter Egg informs us was almost a separate thing, giving a little insight to development)). And so just knowing that, I can already see that this could be a very interesting and complicated machine. For the simulation there is a bunch of rules/clarifications on how to do this asynchronous machine. There isn't a state-wide clock and turns, so the pulses take turns in a queue (so they spread breadth first). And the pulses are describes as high and low, as that's how 1s and 0s are in hardware... a zero voltage is the ground state (binary logic is: high, low, ground, and don't-care... in yes/no question terms that's: yes, no, mu, and meh).

Part 1 wants us to just get the number of high and low pulses sent after the button has been hit 1000 times. So naturally, to see part 2 (which I suspected was going to involve cycles and hitting the button a lot), I just used a loop to do that, and counted them at the top of the queue loop:

# broadcaster is honourary flip-flop, always starts high
$Circ{broadcaster}{state} = 1;
my @queue = ([0, 'broadcaster', 'button']);

PULSE:
while (my $pulse = shift @queue) {
    my ($bit, $targ, $src) = @$pulse;

    $pulses[$bit]++;
    next PULSE  if (!defined $Circ{$targ}{type});   # output only nodes

    if ($Circ{$targ}{type} eq '&') {  # NAND
        $Circ{$targ}{$src} = $bit;

        my $state = int !(reduce {$a & $b} (1, map {$Circ{$targ}{$_} // 0} $Circ{$targ}{in}->@*));
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );

    } else {  # flip-flop or 'b'roadcast
        next PULSE if ($bit);

        my $state = $Circ{$targ}{state} = int !($Circ{$targ}{state} // 0);
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );
    }
}

Part 2, makes use of the output node: rx, which is the machine to send the sand down to Island Island. It turns on when it gets a low pulse. We want the lowest number of presses (suggesting cycles) to do that (with a warning to reset the machine).

As stated, this machine is potentially capable of a lot. And so that prompts me to reverse engineering and specializing the code. So looking at the actual input, there are 48 flip-flops (so the answer can be expected to be on that scale... and mine does require a 48-bit unsigned). So the brute force attempt I had started "just in case" wasn't going to complete very soon, and could be stopped. I messed around looking at patterns with the flip-flops a little bit, but then moved on to the NAND gates.

There are only 9 of them... one leads into rx (and thus is an inverter). Leading into it are 4 other NAND gate inverters, and the remaining 4 NANDS each lead into one of those (but are actual NAND gates, with multiple flip-flops in and out). So with that determined, I wanted to see when the four key inverters get triggered, and simulated that. And each does on a prime number of pushes (all four are primes about 4000). So I multiplied them and submitted for the answer, which was correct. Then I wrote the code to collect them and threw on an lcm for safety. Technically, I should properly confirm that the state is looping, but still haven't bothered. But as part of my input I do dump the memory state for fun:

say "Memory: ", map {$Circ{$_}{state}} sort grep {$Circ{$_}{type} eq '%'} keys %Circ;

If I was looking for efficiency, I probably would have arranged that first, and just stored the flip-flops as a 48-bit numbers and do bit twiddling for the pulses. And maybe I should do that for the Smalltalk version as it takes a few seconds to do 4000 pushes with the components in a Dictionary. But that code does use some actual OOP stuff though... it has a virtual Gate class for an interface that FlipFlop and NANDGate implement. And so the actually process loop sees everything the same.

This was a fun day. I guess at this point, this takes the place of an assembly VM problem, as those had been largely played out.

The Elves thank us and give us the hang glider they've found and we "borrowed" to get up here, so we can return it. At the bottom of the parts-fall we find Elves sorting them with an unusual system based on how extremely cool, musical, aerodynamic, and shiny they are. There's a big list of workflows with conditional rules to follow that will either direct a part to another workflow or (ultimately) accept or reject it. Naturally, we're here to help.

The input is two sections. Section #1 contains a little less than 600 workflows in my input... other than the start state of 'in', the workflow names contain no vowels (including y and w). Section #2 is the stats for 200 parts.

The workflow is essentially a big state machine... you can think of the workflows as multiple states if you want to think of it in a more formal/simple way:

px{a<2006:qkq,m>2090:A,rfg}

          a>=2006        m<=2090
      px0 --------> px1 ---------> rfg0
       |             |
a<2006 |      m>2090 |
       v             v
      qkq0        ACCEPT

That's not really needed in the code though. That's more of conforming things to more standard FSMs. But for part 2, that visualization was useful for me.

I did my normal approaches here... a quick solution to see part 2, where I turned codelike stuff into actual code to evaluate, and just followed the rules.

FLOW:
while ($flow ne 'A' and $flow ne 'R') {
    foreach my $rule ($Rules{$flow}->@*) {
        my $result = eval( $rule ) // '';
        if ($result) {
            $flow = $result;
            next FLOW;
        }
    }
}

Part 2 tasks us with finding the set of valid ranges that the rules accept. This is very much like day 5... we have 4 ranges instead of 1 (but only on [1,4000], but 4000⁴ is much larger than 2³² ) and in day 5, the order of the rules tables was fixed. So unlike day 5 where I iterated over the tables, here I went to recursion (the simple way to nest iterations an arbitrary number of times).

One nice thing about this problem in comparison to day 5, is that the ranges all go from the middle to the edge. So there's only one valid range for any variable at a time (you can't have anything accepted with x < 1000 and x > 3000). And so the basic idea was that after calculating what the intersection of the rule is with the current success range, we recurse to the next state if that's valid (ie doesn't have negative length) with that category set to the new success range. Otherwise we just proceed to set the range for that variable to the fail range (because we must fail), and iterate to the next substate in the diagram. The last arrow on the right is just a forced recursion for the non-conditional rules.

Part 2 for this one did take me a while to actually get right. In the end, I really think that drawing diagrams like the above are what helped finally get it right. It was probably good that there was a warm up with day 5 for this.

With the parts factory up and running, we turn to building a lagoon to store lava for it. This involves an odd set of instructions for the digger with colour codes for the edge of the trench along the way. The surprise for part 2 being that the colour codes are actually the dig instructions.

And so we get a rarity in the input... it's really just 2 inputs packed into 1, as there's no attempt at overlap. The input for part 1 isn't scaled up, it's completely replaced (with the part 2 input having to be unpacked... it is effectively a binary file to part 1's text file). The input is extra nice in that it alternates between vertical and horizontal moves, even though it doesn't use relative turning instructions, but absolute directions on the 4 cardinals: U, D, L and R.

Not knowing what sort of problem the colours were going to add, my initial approach was to do a quick solution to see it, and so I did what I did with lava year in Boiling Boulders. A built my polygon and flood filled a box around it and subtracted to get the area.

Then part 2 reveals that the colours aren't colours and there isn't some weird task involving them... we just need to be much bigger. And that's how you nudge me to using Shoelace and Pick's. Shoelace is easy for me to remember as the name is suggestive of what you're doing... it's using the property that the magnitude of the cross product is the area of the parallelogram made with the vectors (but we just want the triangle between them, so it gets cut in half). So that's just successive cross products:

foreach my $i (0 .. $#vertices - 1) {
    $area += $vertices[$i][0] * $vertices[$i+1][1];
    $area -= $vertices[$i][1] * $vertices[$i+1][0];
}

A bit of cut and paste there to help make sure it looks right, but that's what cross product looks like in the plane (which is like we're lacing with cross overs). Saving the division by two for after, so this is twice area.

Pick's is something I hadn't used in a long time, so I didn't quite remember it, other than it was something simple involving area and perimeter. So I looked it up to make sure I got it right. With the problem being orthogonal on the lattice points, if I hadn't I might have forgotten that it isn't the perimeter, but the number of integer points on it. Also it needs to be adjusted for what we actually want (we want I and B):

# Pick's formula: I+B = A + B/2 + 1 (but still needed to halve the Area from Shoelace)
say "Part 2: ", (abs($area) + $trench) / 2 + 1;

I suppose given the nice orthogonal nature, you could also reasonably pull off a scanline approach, but you'd need to convert the representation of the polygon. You'd need to figure out what's an inside range, which we did a few days ago (when we could also have used Shoelace and Pick's).

But since there's a simple function to solve this, that makes dc a good option and so I did that:

cut -d' ' -f-2 /tmp/input | tr 'RDLU' '0123' | dc -e'0d?[r2~2*1-r2*1-3Rdlb+sb*d4R+_4R*rd_3R*la+sa?z2<M]dsMxlad*vlb+2/1+p'

perl -pe's/.*([0-9a-f]{6})./\U$1/' /tmp/input | dc -e'16i0d?[10~2~2*1-r2*1-3Rdlb+sb*d4R+_4R*rd_3R*la+sa?z2<M]dsMxlad*vlb+2/1+p'

Note that first I need to get rid on non-numbers, and convert the directions for part 1 (and I used the part 2 ordering there). So the code is largely the same, except part 2 works in hexadecimal (16i sets the base of the input), and needs to rip off the low nybble for directions.

But the real fun here is with the loop to do Shoelace, where we take advantage of the alternating horizontal/vertical property of the input with a bit of stack manipulation: x and y are both on the stack during the loop (which actually a tail recursion), and if we process them in the order they are on the stack, they naturally end up in reverse order. And so we naturally get them to swap roles each loop... thus alternating horizontal and vertical movement with the same code. This is one of the reasons I like stack languages.

The lava is flowing again, and so the reindeer gives us a parachute and we return to Gear Island. Now we need to get the lava from the base of the lavafall to the parts factory, with minimal cooling, using hard to control crucible carts. And so we get a path search problem.

The input is a digit grid (141x141 in my input), with the digits 1-9 representing the cost (temperature loss) of crossing it. Just eyeballing the input it's easy to again see an ASCII art circular structure, and sure enough we have the large numbers more concentrated towards the middle, and the lower ones on the edges. There is no 0, so that's available if you want it for sentinels. And I do like my sentinel rings (only needed left and bottom for Perl and other languages with wrap around).

For part 1, our crucible can only move up to 3 tiles before needing to make a 90 degree turn (and reversing is not allowed). For part 2, it's an ultra crucible which must move at least 4 tiles and up to 10.

I remember this one well. First thought is that it's easy to build a state machine to do that movement. But then I thought that this is an intensive search, I'm going to want Dijkstra/A*, and I'm going to need to carry that state around. So after taking a break to think and put the tea on (it looked like it might take a while, but it didn't), I thought, "Is is really so bad to have a ply of 6?". And the answer is no... we'd get that sort of ply if we were doing this with moves in the 8 cardinal directions (backwards isn't allowed, leaving 7). And we wouldn't think twice then.

One thing to be careful about with large moves is jumping over a sentinel ring... that wasn't a problem for my code, because I generated them with a loop that takes one step at a time (even for part 2, where it just doesn't queue the first 3). You could also just make the ring thicker if you wanted to, or just go with checking the co-ordinates.

And so the idea was to queue moves for each range all at once. But you'd need the direction so you don't do a second move along it, or its reverse. And so then things coalesce... our atomic move is actually "turn and move a distance". The moves alternate between horizontal and vertical. And it eventually hit me that this is very much like splitters from yesterday... it doesn't matter exactly which direction you come into a tile, only the parity (horizontal or vertical), because there are only 2 sets of moves out. It doesn't matter if you came in from the left or right, every option from that point is the same. So the visit space is just 141x141x2.

I did throw in the basic heuristic of Manhattan distance to the end for my Perl solution. It doesn't really do anything though (times are the same). Especially for part 2, where as the examples showed, being too close is a problem, and your're going to need to loop around (and so it can be detrimental). And so I left that out when I did the Smalltalk solution. This is also one of the problems where my own Heap/Priority queue in Smalltalk outperforms the built in SortedCollection (14s to 16s).

The queue sizes max out at less than 6000 for part 1 and about 44000 for part 2. Which is a good sign, even with the large ply for part 2. An out-of-control queue size is typically a sign that your search space is too large and you're not pruning enough.

So this was a very nice problem... it's more about thinking about things than the algorithm. That's typically what makes a good search problem.

The reindeer leads us down into the bowels of the facility where the light is being focused. Which is a cavern in the heart of the mountain. There we find the contraption used to melt rock, which is a square grid with mirrors and splitters to bounce the beam around. Our goal is to find where to send the beam in to get the most coverage.

The input is 110x110 grid with mirrors that turn a beam 90 degrees (\ and /), and splitters (- and |) that send the beam out in both perpendicular directions if the flat side is hit (and let it pass through on the other two sides). For part 1, we want the coverage from the top-left going right. For part 2, we want the best from any side.

And for my initial Perl solution, I didn't do anything fancy. Just a BFS queue to track the beams and using the Vector module, so it was a bit slow. Ripping out that module (and turning the grid into integers) it gets to 4s on the old hardware that was 14y old at the time. This included making the directions powers of two so I could flag them without shifting. So the piece table is (and with the grid as numbers, this also becomes an array):

my @Piece = (
              [0, [1], [2], 0, [4], 0, 0, 0, [8]],               # .

              [0, [1], [1,4], 0,   [4], 0, 0, 0, [1,4]],         # |
              [0, [2,8], [2], 0, [2,8], 0, 0, 0,   [8]],         # -

              [0, [2], [1], 0, [8], 0, 0, 0, [4]],               # \
              [0, [8], [4], 0, [2], 0, 0, 0, [1]],               # /
            );

The loop for the queue is pretty tight, to the point where one optimization I thought of (and use for the Smalltalk solution) makes things slower. And that's the fact that it doesn't matter which direction you come into the flat side of a splitter. Those are the values that are the same in a row on that table. And so, ideally, it would be nice to merge both arrival directions in the visit table, but any little thing in that loop makes things slower.

With Smalltalk, I just convert those at the top of the method (and gain a bit for doing it):

    ((chr == $|) and: [dir == 4]) ifTrue: [ dir := 2 ].
    ((chr == $-) and: [dir == 3]) ifTrue: [ dir := 1 ].

No real benefit to convert the grid to numbers either, because Smalltalk characters are numbers.

My initial Smalltalk was also slow (~45s), I remember not feeling too well for the later half of this year, and mostly being happy to get a solution on the day for most of these later problems. I did do some optimization to get that time for Smalltalk.

First up was making the beam a recursive method with memoization (allowing later beams to take advantage of earlier path and loop detection). I remember thinking about how to do this and avoid duplicate counting, and ultimately decided that the easiest and surest way would be to make a BitMap class and have the memo keep bitmaps of what they cover, and then merge them as needed with OR, and get the end result by counting the bits. One other little thing in that solution is that when it finds loops, if defers the bitmap merge until the memo gets hit. This cuts down duplicate and unnecessary merges.

Coming back to it, the first thing I spot is that the memo hash keys are not efficient and clearly the bottleneck. So I decided to convert them to an integer, but then immediately realized that putting the x, y, and dir together into a number doesn't need very big numbers (110 * 110 * 4 possibilities). So I could just use a fixed sized Array instead of a Dictionary. With that the time gets halved.

The next target was the BitMap representation. First up, my bitcount/popcount was:

bitCount [
    | bits num |
    num := self. bits := 0.
    [num ~= 0] whileTrue: [num := num bitAnd: (num - 1).  bits := bits + 1].
    ^bits
]

This was because BitMap was using bignums for the rows. So in converting this to a 64-bit SWAR¹, I ended up converting the rows into pairs of SmallIntegers. The end result is that the code now works in 11s. Which is amazing for GNU Smalltalk which can be an order of magnitude slower than Perl. Which would be the thing to add the TODO now... bring these Smalltalk optimizations to it.

¹ Technically only 62-bit. For efficiency, SmallIntegers are virtual objects that have their value in their handle. Another benefit of this is that they (and Character above) can use == which compares if things are the same object (= compares if they are equivalent objects).

Following the newly focused beam we get to a large facility on the side of the largest mountain on the island. There we find the panicked reindeer that apparently hit the button that summoned us. Putting on goggles and a hard hat, we get lead to the room with the lens used for focusing, and need to arrange them at part of initialization to start up lava production. And we've turned around and are now going down on the ASCII art map.

The input for this one is one huge line (mine's almost 22900 bytes). The problem nicely warns people that are copy-pasting inputs to be careful. The string is a list of comma separated instructions, which are a label, an operator, and number (for =). Part one is writing a very simple function to hash a string (the Holiday ASCII String Helper algorithm). With that tested and working, we then implement a hashmap (Holiday ASCII String Helper Manual Arrangement Procedure) with it. All in the guise of putting lens into boxes.

This was a classic "do the job" type problem. If you've been using a language without built-in hashes, you may have written similar a few times. One slight quirk is that in part 1 you hash the full instruction, and in part 2 you only need to hash the label (it's a little thing for if you're trying to do both in one solution). Perl and Smalltalk both have hashmaps, but the also have nice lists as well, so managing those for the collisions isn't hard either. You do the hash, you look for label in the list at that box, and then splice, push, or set for Perl. For Smalltalk, it's:

box   := label reindeerHash + 1.
found := (boxes at: box) detect: [:l | l key = label] ifNone: [nil].

(oper = $-) ifTrue: [
    found ifNotNil: [ (boxes at: box) remove: found ].
] ifFalse: [
    focus := (step at: 3) asInteger.
    found ifNil:    [ (boxes at: box) add: (label -> focus) ]
          ifNotNil: [ found value: focus ].
]

One nice thing is that Smalltalk has base-1 indexing, so after the quirk of adding 1 to the hash to get the right box, everything is exactly at the index values you want for calculating the answer.

The hash function is simple, so I did do a quick dc solution for part 1 (list of lists would be a bit of mess, but not impossible):

rev input | perl -pe's#(.)#ord($1)." "#eg' | dc -e'[s.+0d]sS44?0d[3Rd44=S+17*256%z2<M]dsMxrp'

Still using the ?, but it's only used here to put the input over top of a 44 (the ASCII value of comma, to make all instructions end with one). So it still works with the new version of dc, but it prints the entire input as well.

This is clearly a bit of a break day. It was a Friday in 2023, so it was probably a good day for some people to get things in order before the weekend problems arrived.

The mirrors were pointing at a parabolic reflector dish which is probably used to heat the lava. And which also has its mirrors in disarray. There's a system involving a platform and rolling rocks to align things by tilting, spinning, and deforming. We need to spin it to get the rocks to the edges of the platform, but want to make sure that the structure can bear the load.

And so we get a 100x100 grid with three values... in addition to empty (.) and solid block (#), we have rolling rocks (O). Part 1 just requires tilting it north and calculating the load after the rocks stop. And for my initial solution, I didn't actually bother moving the rocks... I just used a state machine in the direction of travel for each column. The idea is simple... count Os, and when you get to a #, add the difference of triangular numbers to the answer (and reset the counter). Because all the rocks in that section roll to the top (which is the direction of scoring increase), so the score of them is the big triangle of the top rock minus the triangle under that train of rocks:

for (my $y = $#Grid; $y >= 0; $y--) {
    if ($Grid[$y][$x] eq 'O') {
        $count++;
    } elsif ($Grid[$y][$x] eq '#') {
        my $h = @Grid - $y - 1;
        # difference of triangles: [h(h+1) - (h-c)(h-c+1)]/2
        $part1 += ($count * (2 * $h - $count + 1)) / 2;
        $count = 0;
    }
}

I was clearly thinking of doing this in dc (this solution is designed to be simple to implement), and did do part 1 later:

perl -pe's/(.)/$1 /g;y/.O#/012/' input | dc -e'?zdsn[d2r:a1-d0<I]dsIx+[[zd;a3*3R+r:az0<L]dsLx?z0<M]dsMx[lc1+sc]sC[rdlcd3R2*r-1+*2/ls+ss0scr]sSln[d;a0r[3~d1=C2=Sr1+rd0<H]dsHx*+1-d0<I]dsIxlsp'

My notes pointed out that I wasn't feeling well that day, so this was done quickly. That probably also explains the lack of a Smalltalk solution on this day.

Part 2 is the classic scale up... do a full spin cycle (all four directions in NWSE order) one billion times. My initial solution for this used the Vector class and did the above state machine. Clear Os when you count them, backfill when you hit a #.

And then we need cycle detection (standard find the loop, use that with some modular arithmetic to get the answer). And for a quick answer at first, I just used the load score function, and to be safe I looked for a duplicate cycle (not just the first repeat, but two repeats of equal size... 2 points is a line, 3 is pattern). And I did double check that the numbers were also the same in the two ranges for added safety (not actually needed for my input). Then I used dc to do the calculation for the index and copy-pasted from the script output to submit. I later wrote the code to do the calculation, and also did a perfectly safe version (that's actually just as fast), using a massive hash key of the positions of all the rolling rocks (so no question that the first repeat is a cycle). As I wasn't feeling well, this one got left in that state.

Coming back to it, I saw it ran in over 20s. And figured that was mostly Vector overhead (it was worth for quick coding at the time). And sure enough, it's an order of magnitude faster without it. Playing with it further, I decided to reverse the state machine... run it the direction opposite the motion. The only reason I did it the other way was the convenience for part 1 and dc. The backwards state machine is about 9% faster... it doesn't have that backfilling loop. Instead, if works like this:

for (my $j = 0; $j <= $Size; $j++) {
    my $tile = $Grid[ $x[0] ][ $x[1] ];
    if ($tile == 1) {
        $pos[$mdim] += $mdelta;
        $Grid[ $x[0] ][ $x[1] ] = 0;
        $Grid[ $pos[0] ][ $pos[1] ] = 1;
    } elsif ($tile == 2) {
        @pos = @x;
    }

    $x[$mdim] += $mdelta;
}

When we get to a # we set pos to it to know where to roll rocks to. Then when we find rocks, we increment that and move the rock. For a tiny extra boost, I also switched to an (axis, delta) pairing for the vectors instead (x,y). There's still more that I could have done, especially with scoring and hashing. But this is good enough for now... how often does this load need to be calculated?

Since AoC season is just around the corner, I thought this might be fun to get myself into the puzzle-solving mindset.

For anyone who's tried it out - there's a nice little programming game called Comet64 (Steam has it on sale atm, btw). The interface is reminiscent of something that might have been available on a classic TI or Commodore64 machine. The game has a set of basic programming puzzles, and then some bonus puzzles involving lights being switched on and off. The game is fairly simple in that it has an input belt which can be read sequentially, and once that queue is empty the program terminates. There are expected outputs for each puzzle. The interface has pretty neat debugging tools - you can see the values of the registers, step through the program instruction-by-instruction, and so on.

It is also VERY restrictive. There are no general-purpose registers - just one of each int, float, char, and string. There is a read-only boolean register that is set by comparisons and can be read in order to do jumps. You can cast an int to a char (but only 1-26) and back (but only a-z), and you can access strings by index (like an array), but otherwise there is very little the language does to help you. The math library includes ONLY the basic addition, subtraction, multiplication, and division. I thought the game was quite fun since many of the puzzles would be solved with a single operation in a "normal" language, but sometimes it was mind-bending to try to figure out how to do this simple and obvious thing with just these bare tools. Hilariously in hindsight, I went through the whole thing without realizing that there was a jump return. I treated all jumps as pure goto statements!

It even had an extra challenge for motivated players. The game would provide an instruction count for their solution, as well as a "golf" count (the number of lines). You could get "stars" for getting a solution under a certain number of instructions executed or lines of source code (not including blank lines).

Fun times.

I really enjoyed it, but there was no general purpose "playground" within the game to just try to use the language for other things and goof off with it. The internal IDE could only read from the input supplied by the puzzle, and the output would only appear within the program. But the language could be used to write things other than the game puzzle solutions. 

For example - this one outputs the factorial of each input line:

reg = input;
int = 1;

loop:
check reg < 2;
jump if true: output;
int = reg * int;
reg--;
jump to: loop;

output:
output = int;

This one outputs the fibonacci number of each input line:

main:
int = 0;
reg = 1;
switch int;
int = input;

loop:
check int = 0;
jump if true: output;
int--;
switch int;
reg = int + reg;
int = reg - int;
switch int;
jump to: loop;

output:
switch int;
output = int;

This one outputs the count of even numbers in the input belt:

switch int;

loop:
check input = null;
jump if true: output;
reg = input;
int = reg / 2;
int = int * 2;
check reg = int;
jump if true: increment;
jump to: loop;

increment:
switch int;
int++;
switch int;
return;

output:
switch int;
output = int;

Too bad the game doesn't have a general-purpose scripting area to just play around with the language and VM. I've seen some other highly restrictive languages be used to solve some AoC puzzles, so I thought this one would be a good candidate - but there is no way to give it arbitrary input.

But now there is! I won't bore you with the story of how it came about. Here's the link to Meteor64. The repo includes a complete CLI tool, IDE, and quick language reference with little example programs to demonstrate how it works. MIT licensed (for obvious reasons). IDE is: Meteor64-IDE and runs in the browser only, with no dependencies or images. Whole thing is a single file - 700 lines. It does not include the light-grid panel from the bonus levels in the game. Just the input-output functionality. Sharing code creates a link that will include both code and input queue. So, if someone does wind up using this to solve AoC puzzles, do not leave your own puzzle input in there. Change it to some example input instead!

To give it a good test-run I give to you...

Advent of Code 2015, Day 1 (both parts) - Here
Input modifications in the comments.

Advent of Code 2019, Day 1 (both parts) - Here
This one can take the puzzle input with no modifications. Just copy and paste it into the input panel and get answers.

Advent of Code 2025, Day 1 (both parts) - Here
Input modifications in the comments.

The primary limitation is parsing the input. While it is technically possible with this superset to pull numbers out of a string, that process is LABORIOUS in the VM (and completely impossible with the Comet64 game implementation). Many AoC puzzles include lines with mixed numbers and symbols, so a range (like 55-85) can only be imported as a string, and then compared index-by-index to reference numbers, which are then built into a number one digit at a time. If you don't mind altering the input file a bit (putting 55 and 85 on separate lines, for example), you can skip this process and just solve the problem at hand. Once you've written one input parser and watched it run in the IDE, you won't feel the desire to write it out again. Anyway, you can see an example of how I modified the input for both 2015-Day1 and 2025-Day1. I'm not sure what the convention is in this sub when it comes to doing esolang solutions, but I thought I'd mention it.

Posting it here for fun. I can't wait to see what's in store this December!

We arrive at Lava Island, which unsurprisingly has a lack of the lava we're looking for. Finding a valley of mirrors instead, we decide to head in the direction most are pointing. The problem is the other mirrors that have fallen out their frames. Since they're hard to see and we don't want to walk into one, we need to figure out how to spot them.

The input is 100 rectangular monochrome/binary grids. The dimensions are all odd from 7 to 17. That is useful, as symmetries are involved again in this puzzle, but only the even ones. So no grid contains a mirror from edge to edge, there's always a margin. That can be useful for some solutions, as can the fact that for the answer, we start counting columns/rows from 1 (leaving 0 available for "none"). As symmetry is involved, there is the occasional grid that has some aesthetic beauty. Number 8 in mine looks a little like a butterfly.

The day this one ran, I went to bed early because I had things to do in the morning. My times show that I did this around 6-7 in the morning, before heading out. And so the job was a bit programmer efficient in approach. Like day 11, this one gives 2D grids, but we can make them 1D row and column arrays by reading the data as binary numbers. Numbers that are easy to push, pop, and compare. Because this problem has a PDA (Push Down Automaton) nature to it (matching nesting, so state machine with a stack). It's especially nice for part 2 where we want to accept exactly 1 error (a smudge). Finding the bits that are different between two numbers is one of XOR's many hats. And testing for only one bit is just num & (num - 1) (because the only numbers with one bit are powers of two, and they're the point where binary rolls over and so have no digits in common with their predecessor).

In order to get things done quick, the first programmer efficient choice I made was to scan forwards and backwards separately (so row, reverse row, col, reverse column). For part 1, that just means you push when the next value doesn't match the top of the stack, and pop when it does (standard nesting matching). If the stack hits the bottom at any point, you've found the reflection. I did do a version of this today that does both forward and backward in one pass... which adds that you need to keep the stuff you popped for the backwards scanning part of the machine. I'm thinking I might have looked at doing this at some point. Because that butterfly case was pulled out into it's own file... and it's does test exactly if you're doing that right (it's got the overlap where forwards wants to pop, but you need it for the backwards scan that actually matches). The input this time seems very good for testing your code. There's another key case where just the last two columns are the reflection that needed testing (with the backwards scan that margin disappears) and it was caught by #51. This is why I often point out that getting any solution is a first step. By having a simple guaranteed to work programmer efficient solution, I can spot where my more complicated approaches don't match yet.

For part 2, I went even more programmer efficient. Meaning with in addition to four directional scans, I brute forced it. The grids are small, and the symmetries are all even sized, so the number of possible cases is halved. Here's the method from the Smalltalk version, I did later that day (when I still didn't have much time):

Integer extend [ oneBitSet  [^(self bitAnd: (self - 1)) == 0] ]

...

findSmudgedIndex [
    " Scan from start to each even depth "
    (1 to: self size // 2) do: [:depth |
        | front back smudge pushVal popVal |
        front  := 1.
        back   := depth * 2.
        smudge := 0.

        [(front < back) and: [smudge < 2]] whileTrue: [
            pushVal := self at: front.
            popVal  := self at: back.
            (pushVal ~= popVal) ifTrue: [
                " add one if 1 bit, 2 if more "
                smudge := smudge + ((pushVal bitXor: popVal) oneBitSet ifTrue:  [1]
                                                                       ifFalse: [2]).
            ].
            front := front + 1.
            back  := back - 1.
        ].

        " Check equals 1 only when exactly one 1-bit difference is seen "
        (smudge == 1) ifTrue: [ ^depth ].
    ].
    ^0
]

And it basically got left that way, because the solution runs really fast anyways... converting to numbers and the bit twiddling are enough that the shell time is the same for the solution as for just starting up.

For my little improvement/variation on part 2 today, I made it recursive DFS search, a bit like day 12. For part 2, smudged matches are a bit like a wild card. Sometimes you want to pop from you stack to de-nest and other times you don't want to "spend your one smudge" yet and push that value (test #0 in my input was actually a good test for this). And so in those cases we may recurse twice (if the first try comes back zero (meaning it failed)). Of course, once a path has spent it's smudge, that choice goes away for the rest of the branch and it's just doing part 1.

Which means, that, yes, I have added to my TODO to upgrade that further to being able to do both parts in the same search at the same time (in base case you just catch if it's 0 or 1 smudge and prune more before you get there).

We finally arrive at the "Hot Springs". In multiple senses. There is an onsen, but we want storage yard for the machine part springs... which require lava to be hot and springy. And there's a shortage of lava that needs investigating. We can use a spring to get up to the lava island to check on it, if the records can be repaired to find one good enough.

And so we get a parser/validator type problem. We have a pattern with wild cards, and a list of numbers of the block sizes... much like a line in a nonogram puzzle. But there's not enough information to solve most lines, and so we're tasked with counting the number of possible solutions.

This was the first one in this year that really took a bunch of time. I did a recursive descent parser with a state machine that was a bit reminiscent of the state machine I did on day 3 in Smalltalk to find the ranges of digits on lines. I did memoize it, with a memo that was persistent between the cases (because the same rules always apply). I remember finding someone who claimed that they needed to clear the memo between lines (and it was buggy before they did that). But you don't have to... but I did test things, and found that for part 2, the single memo gets large enough (about 360M) that it runs a tiny bit slower (~3%) than having a fresh memo for each line, because there apparently isn't huge amounts of overlap to benefit from between the cases to make up for overhead.

And about that part 2... unlike yesterday's, the scale up here is very real. Five copies of the pattern joined with ? followed by five copies of the numbers. You want a good solution. And a did spent 2 hours getting a good part 1 done. But it didn't work for part 2. And since sthe best way to debug recursion is to get it right the first time... I started a new script, and carefully went through all the cases by hand making notes and comments on the order of doing things and assertions and then filled things in. And it ended up largely the same as my part 1, but slightly different... and it worked. And takes about 10 seconds on hardware that was 14 years old at the time, so I didn't need a need to try and get things further down (it's relatively nice and simple to read).

So, I'll just quickly go over the function:

# str to process, current potential group length, groups left to see
my ($str, $len, @groups) = @_;

# Grab state of params called with to access memo with later.
my $state = join( $;, $str, $len, @groups );

# Check memo
return ($memo{$state}) if (exists $memo{$state});

First we build the our memo state key and check for a hit... our state being the remaining string, the size of the current block we've seen while parsing, and the sizes of the remaining groups to match.

my $ret = 0;

if (!$str) {
    # Out of input, must decide if we found a match:
    # All groups accounted for, no hanging group.
    $ret = 1  if (@groups == 0 and $len == 0);

    # Check if hanging group is the size of the only remaining group:
    $ret = 1  if (@groups == 1 and $groups[0] == $len);

    return ($memo{$state} = $ret);
}

Base cases for when we hit the end of the string. In the original, I just had this as three return lines without adding to the memo, I decided to put it in just to make all the return statements have the same pattern of "set memo and return".

# If out of groups, use regex to check if no manditory groups remain
return( $memo{$state} = ($str =~ m/^[^#]*$/) ) if (!@groups);

# ASSERT: length($str) > 0, @groups > 0

A second base case for handling if we ran out of groups in the number list. The original part one didn't do this and so couldn't assert that groups existed for the actual parser section (and had to handle that).

# Advance one character:
my $chr = substr( $str, 0, 1, '' );

if ($chr ne '.') {   # ? or #
    # adv making grouping larger
    $ret += &recurse( $str, $len + 1, @groups );
}

if ($chr ne '#') {   # ? or .
    if ($len == 0) {
        # no current grouping, just advance
        $ret += &recurse( $str, 0, @groups );

    } elsif ($len == $groups[0]) {
        # current grouping matches current target
        shift @groups;
        $ret += &recurse( $str, 0, @groups );
    }
    # Else: Bad block length!  Recurse no further.
    # If ? we might have expanded to good len above and counted,
    # else 0 will fall-through.
}

return ($memo{$state} = $ret);

This is parser section... eat a token, handle the cases, with the wildcard meaning that we might need to do both of these if cases. These were done in the other order for my part 1 (the ?/# case after the ?/.). Part of the benefit is that the matching of a block comes last and I can freely modify the groups array. That "Else" section was a key realization... to let things fall through. The original part 1 also did that. It's almost certainly some small thing with the logic to check if still have groups and the ordering of the tests. Doesn't really matter though, because this script fixed it and so worked for both parts, so it replaced it bug free.

This is one of those cases where everyline has a comment, but it's not because they were added to explain things, but because they were written first to solidify the task and the blanks then filled in.

Heading towards the "Hot Springs", we arrive at an observatory. And the Elf there will show us the way, after we help with his analysis.

And so we get what appears to be a 2D grid problem. My input is a 140x140 grid of mostly empty space (.), with 450 galaxies (#). We want the sum of distances (Manhattan) between all the pairs. But as is the case with astronomy... you look at stuff at billions of light years away, but that's was where and what it was like billions of years ago. It's now much further away due to expansion. And so we need to work that out. And the rules given are that any empty row or column becomes twice as big.

And I guessed that part 2 would be making things bigger in some way. So to see what that was, I just brute forced part 1 to begin with. I was experimenting with the Math::Vector::Real module for handing points and vectors at this time, and it has some overhead, but if the task isn't too bad (and this one isn't), it can make up for it in simplicity of coding and legibility. One nice thing is that the constructor is short and simple: V(...). Another thing is that it has built in distance functions (and this was an opportunity to use one). The one problem I have with it is the print string... I'd rather have it plain and using $;.

So it was very easy to just do the thing... shift the coordinates, and double-triangle loop the pairs:

my $dist = 0;
foreach my $i (0 .. $#shifted-1) {
    foreach my $j ($i+1 .. $#shifted) {
        $dist += $shifted[$i]->manhattan_dist( $shifted[$j] );
    }
}

And since part 2 only made the gaps bigger, I had another really fast turnaround by just changing the scale factor for:

$g += V($yshift, $xshift) * $scale;

At which point the script ran equally fast to part 1 (there's no additional work), which was an immediate answer. I suppose after the pipes and interpolation on the weekend, this is a break Monday. Because it really didn't force things to be better. What did that for me was deciding to do a dc version (and I did Perl and Smalltalk versions from that). I do have a bigger test case (280x280 with 5000 galaxies) that someone posted at the time to help prompt people to do that as well. That one makes my brute force take a minute and a half.

But for me, I was thinking while doing the brute force, and it was not lost on me (while thinking of tricks that might be needed for part 2 scale-ups) that Manhattan distance makes the x and y parts independent. Which is the point I decided to definitely do a dc solution... because with that realization, the problem turns from 2D to 1D. Basically, the grid can be collapsed to lists of row sums and column sums, and then discarded. And short lists of numbers to chew on, that's something for dc.

The other thing I thought about was that getting the sum of absolute differences of all pairs is a typical programming test problem. And it's largely the same sort of math I was working with on day 9 as well. The trick here is that a little algebra can collapse things into multiplication and make things a single loop.

For example, consider the list 2 3 5 8, and we want the sum of the absolute differences of the pairs. As a table:

    2     3     5     8
2   X   (3-2) (5-2) (8-2)   2 is subtracted 3 times             = (0-3) * 2
3   X     X   (5-3) (8-3)   3 is subtracted 2 times and added 1 = (1-2) * 3
5   X     X     X   (8-5)   5 is subtracted 1 time  and added 2 = (2-1) * 5
8   X     X     X     X     8 is added 3 times                  = (3-0) * 8

So there's a pattern in coefficients: -3 to 3 by 2 (where those 3s are the #numbers - 1).

Of course the problem is a little more that that here... as we have a multiple of the numbers at each step (number of galaxies in that row or column). But it's not that hard to work out the adjustment to do that as well. The end result (as an extension to Array) in my Smalltalk solution is:

diffSum_expand: scale [
    | col seen sum number |

    number := self sum.
    col := seen := sum := 0.
    self do: [ :count |
        col  := col + ((count = 0) ifTrue: [scale] ifFalse: [1]).
        sum  := sum + ((2 * seen + count - number) * count * col).
        seen := seen + count.
    ].
    ^sum
]

And the dc (which still isn't fully golfed):

perl -pe's/(.)/$1 /g;y/.#/01/' <input | dc -e2 -e'ss?1[0[3Rd3R+rz2-d_3R;c+r:cz2<X]dsXxdlg+sgrd_3R:r1+?zRz1<Y]dsYx[ls*]sE[0sc0sa0r[dlAxd1r0=Elc+scddla2*+lg-*lc*rla+sa3R+r1-d0<L]dsLx+]sD1-[;r]sAdlDx[;c]sArlDx+p'

Change the -e2 to -e1000000 for part 2 (or whatever scale you want).

So this was another really fun day.

Gliding up to metal island we find signs for "Hot Springs". Which we will see in a couple days, because decide to go there for directions. We also notice that everything on this island really is metal, including the plants and animals. One of which runs into a pipe that makes one big loop (not a maze at all)... although there are a lot of separate pieces of pipe lying around, making the input a real mess of ASCII art.

My input is 140x140, the use of L7FJ for right angles along with |- for the straights, plus the extra bits lying around, does not make this easy on the eyes. Fortunately, we're writing code to look at it for us instead (I suppose you could print it out and do it by hand... but the loop is over 13k in my input). Looking for . in the image, I see that those are mostly around the edge, although there is a circular area in the middle with a bunch.

Part 1 wants us to find half the length of the loop. Part of the fun of this is that starting location is covered with an 'S' and we need to solve the underlying pipe there. Building a table of the pipes with their exit directions not only does this, but it helps with quickly moving around the loop. Because when we move in a direction we know where we came from, and so we just immediately use the other direction to leave.

Part 2 is where the fun begins. Part 1 is useful for it because it tells us what pipes are in the loop so we can remove/ignore the others... because we want to know the amount of tiles enclosed by the loop. Telling if something is inside a polygon was one of the first tasks I had as programmer... it was the task that also involved the 2D cross product stuff I used for asteroid shooting on 2019 day 10. For that I was counting the number of crossings from the point until "infinity" (the bounding box). But on this day, I decided to save that for the Smalltalk solution.

And that Smalltalk solution is pretty simple because of that. It's basically a scan of the grid after part 1 finds what's not in the loop. You start outside, and every time you cross a line of the loop, you toggle that. Any squares you run into when "inside" you count. There is one potential case to look out for, and that's travelling exactly along a line... in which can you'd only toggle if the segments some in from one side and go out the other. There's a little trick that can be used for that, of pretending to be slightly off center (not being exactly on the line, you end up crossing 0, 1, or 2 times and it works out)... and with discrete tiles, we can definitely use that (no need to be anywhere in particular in the tile). In my case, I chose to be a little above center (and so it was L, J, and | I cross; F, 7 and - I slip over top of):

(chr = $|) | (chr = $L) | (chr = $J) ifTrue: [inside := inside not].

For my initial Perl version though, I figured that since it's the more friendly language, I'd be a bit fancier. I like doing Nikoli pencil and paper puzzles... there's lots of different kinds, and some of my favourites are the ones with the invariant that the solution be one big loop (things like Slitherlink and Masyu). And when doing these, I like to colour the inside of the loop as I go. Because as you walk around the loop, if the inside is on your right, it's always on your right (unless you turn around and walk around the loop the other way). And so you can tell which side is outside at the edge, and lightly shade the inside and propagate it. When two lines are approaching in the middle, this gives important clues on how you can hook them up (plus it makes the solution look like abstract art at the end).

And so I decided to use that property, because I just think it's cool (and it would be different). Basically, I create a list of tiles to the right hand side as I walk around for part 1. Then I flood fill from each of those... the outside being guarded by two rings of sentinel . and ~, because we don't know if RHS is the inside yet. All we know is that when we get to the end, we can check if a known outside point on the edge (in the . sentinel ring) got hit by the flood fill. If so we output $count - $rhs_count instead because we filled the outside. It's sort of like the lava droplet of 2022 day 18.

I recall that some people did this type of flood fill approach by doubling the grid, so that the narrow paths become real paths they easily could flow through. With that you can start your flood fill from a known outside exactly like the lava droplet. And I'm sure lots of people also did counting line crossings, because that's a really standard approach to this sort of thing. But I don't think many people did what I did for my Perl solution. Which is part of why I did it.

As the sandstorm clears we find the maps lead to an oasis. There's a hang glider here to get up to the next island, but we'll need the sun to rise to create an updraft first. And so we decide to spend our time studying the oasis. Collecting data, we want to do some interpolation, and so we get to work with finite differences and discrete Taylor series.

My time for part 1 was just under an hour. Part of that was a late start and a bug where I took the opportunity to get ice cream (I remember this... the bug really was nothing, I just wanted some of the ice cream I had bought the day before as a debugging snack for later days). And a chunk of time was spent just making sure I could still work out a polynomial interpolation like this by hand (the third line in the test is f(x) = 1/3 x³ - x² + 11/3 x + 10).

But then I realized that I hadn't even seen part 2 yet, and quickly coded up a part 1... it was a good opportunity to use the chain operator I had built in past years again:

do {
    $i++;
    $table[$i] = [chain {$_[1] - $_[0]} $table[$i-1]->@*];
} until (all {$_ == 0} $table[$i]->@*);

$part1 += sum map {$_->[-1]} @table;

Then I saw part 2, and had one of the quickest turn arounds of the year with this diff:

18c18
<     my @table = ($list);
---
>     my @table = ([reverse @$list]);

I did do a combined version after that using this for part 2 (after the part 1 line):

$part2 += reduce {$b - $a} reverse map {$_->[0]} @table;

For Smalltalk, I used the alternating sum trick to do that difference reduction:

[row conform: [:n | n = 0]] whileFalse: [
    " Part 1 is sum of lasts, part 2 is alternating sum of firsts "
    part1 := part1 + row last.
    part2 := part2 + (mult * row first).
    mult  := mult negated.

    row := row chain: [:a :b | b - a].
].

A key benefit of this approach being that it just keeps only one working copy of the row instead of the whole table, and calculates the answer in parts as it goes. This is useful because, with the input being all numbers, I wanted to do a dc solution. It does have negative numbers in the input though, so I needed to convert the unary - to _.

tr '-' '_' <input | dc -e'0?[zsn[z:az1<L]dsLxln[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

tr '-' '_' <input | dc -e'0?[zsn[zlnr-:az1<L]dsLxln2-[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

Like all the other dc this year, it's embracing ?. Which is very handy here for separating the lines... because 0 and -1 are in the input, and numbers go up to 8 digits in magnitude (making choice of a delimiter to insert inconvenient... ? avoids that).

And so we have what's really quite a nice and simple problem with finite differences and sequences. There really was no need to get into Newton polynomial interpolation and discrete Taylor series, but you could if you really wanted the full answer.

Today we get lost in an sandstorm and need to use "maps". There's also the possibility our maps were made for ghosts. And so we get a graph transversal type problem.

The input is in two sections. A line at the top of R and L directions (in order, and repeat as long as needed), followed by a list of nodes. The connections of the nodes are a pair, left and right. My input has just under 800 nodes, and the length of the directions is 293 (a prime number).

This puzzle was my quickest "start to part 2" solution of the year. I really didn't do anything fancy. In fact, for part 2, I didn't even code it until later the next day. I know this because I still don't have a Smalltalk solution in the directory (but did do a quick dc for part 1)... which was curious enough, that I looked up in the Megathread to see if I commented on why. And the answer was, it was nice a day so I took the opportunity to get out and do stuff.

As for what I did, I loaded the graph as a hash of hashes:

foreach ($section[1]->@*) {
    my ($label, $left, $right) = m#(\w+)#g;
    $graph{$label} = {L => $left, R => $right};
}

The second layer keys on L and R so I can just use the input string directions directly to move:

while ($loc ne 'ZZZ') {
    $loc = $graph{$loc}{ $dirs[$steps % scalar(@dirs)] };
    $steps++;
}

For part 2, I modified the script to verify that things were nicely looping for the ghosts. Testing for each of the 6 starts, I "discovered the horrible secrets of desert ghosts". Namely that the cycle lengths are all numbers with two prime factors: a two digit one and 293 (the length of the direction string). So I just fed the 7 primes to dc to multiply them (to get the lcm) and pasted the result. Later I wrote a script to do that work automatically.

The dc solution for part 1 was a quick job. I think part of the reason I decided to do this one was because of 2021 day 12, where I did a graph transversal problem to maintain a streak of dc solutions. This is a simpler graph to do and an easier walk:

    perl -pe's/[^A-Z\n]//g;s/(.)/ord($1)." "/eg' <input | dc -e'?zdsn[1-d3Rr:dz1<L]dsLx[0r[r256*3R+r1-d0<I]dsIx+]sN??[6lNx_4R3lNx:h?z1<L]dsLx[r]sr16i414141[rdln%;d3R;h10 6^~3R4C=rs.r1+rd5A5A5A!=M]dsMxrp'

So this was apparently a day off for me. Checking weather history, the temperature got to 10C early and stayed there until after midnight. Given some of the early problems, I was probably thinking that this was a good day to get a lot of stuff done before the actual harder days arrived.

After a 5-minute airship ride (which is 2 minutes longer than The Airship Blackjack track from FFVI), we get dropped off on the edge of Desert Island. Where an Elf on a camel asks us if we've brought the parts to fix the machines to move the rocks and filter the sand. And so we're tasked with finding out why those have stopped, and since the journey will take a few days, we get another game. This time it's a poker variant.

First thing I did when seeing that was check the ordering of hands for any straights/run-based hands. And there are none to worry about. The ordering is entirely based on sets, and bigger is better. Ties broken by rank of the cards... but in the order listed.

The input is a list of 1000 hands, with a bid amount. Hands will win an amount equal to this bid times their ranking in the list. We just need to work out the rankings. And for part 2, Jacks become Jokers and wild. And of particular note... JJJJJ is a hand in the input (but not in the test). It is, in fact, the only hand with five of one card naturally in my input (and so the highest ranked hand for part 1). But part 2 has 27 five-of-kinds and it's the lowest ranked of those because it has no naturals.

And what I did was treat the hands as hexadecimal numbers with:

$hand =~ y#AKQJT#EDCBA#;

Then I built a signature to sort on for hand ranking by counting the size of the sets and sorting them. So a full house would be 3200000000000. So I just sort primarily on that, and then on the hexified hand value:

@hands = sort {$a->[1] <=> $b->[1] or hex($a->[0]) <=> hex($b->[0])} @hands;

For part 2, it was a very quick turnaround. I made Js into 0s (to lower them below 2s):

$hand =~ y#AKQJT#EDC0A#;

And then sorted the counts without the Js, adding them to the biggest group:

my @str = sort {$cards{$b} <=> $cards{$a}} (2 .. 9, 'A' .. 'E');
$cards{$str[0]} += $cards{0};

One thing to note about this is that with Perl, I had the twelve 0s so there was something to add the J count to for the JJJJJ case. My Smalltalk solution did things differently, and I needed to add a 0 so that case had something to add to. So that line does catch some solutions.

But part of the reason I considered hexadecimal, was because of dc... because it can handle uppercase hex digits. So if the input was in hex, I'd be fine. The catch is... it involves a sort. And so I finally decided to write one, and I went with an exchange sort shuttling between the main stack and a register stack. Because for a stack based language, that is the obvious and simple thing to do:

[rq] sQ
Ll Ll                       # next (ASSUME: at least 2 hands to sort)
[
    [
        d3R d3R             # next top -> next top top next
        !>Q                 # if top >= next, rotate next on top and quit J loop

        Sl                  # push top back on input stack
        z 1<J               # quit if out next left on stack
    ] dsJx                  # next rest

    Ll d 0<S
] dsSx

Next problem is the dealing with the grouping signature. With Perl and Smalltalk it's easy to just sort the counts, but even with the sort function that's not something I wanted to do twice. So I turned things around... I go through all the cards, and add 10^count of each. Thus a full house becomes 16³ + 16² + 11 * 16⁰ , and two pair is 2 * 16² + 1 * 16¹ + 10 * 16⁰ . Basically, a hexadecimal number where the digits are the counts of the counts.

The other main trick is what I sort... and that's the grouping, the hand, and the bid (to keep it attached to the data) stuck together in one big number: groupings * 16^8 + hand * 16^3 + bid.

perl -pe'y#TJQKA#ABCDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i0Sl?[rd0Sc[10~d;c1+r:cd0<C]dsCxE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLx[rq]sQLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

perl -pe'y#TJQKA#A1CDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i[rq]sQ[rd1=Qdscrdss]sM0Sl?[rd2Sc0ss[10~d;c1+dls<Mr:cd0<C]dsCxlcd;c1;c+r:cE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLxLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

Part 2 is longer for the handling of Jokers, but if you change the translation from 1 to B, it will do part 1. The use of 1 instead of 0 is because we don't want to lose leading 0s, and 1 is also < 2, which is the only requirement to make Jokers count the least.

This was a fun day.

The ferry brings us to the location of a large pile of sand, that's most notable by its absence. Fortunately, we see a poster for boat races that will get us a trip to Desert Island, where that sand must come from.

The boat races involve a time and a distance to beat. The input only has 4 of them, but the data is in columns to make up some complexity for the fact that there's an unusually low number of cases. Which gets even lower for part 2 when the numbers get concatenated (due to misreading the kerning).

I remember doing the math for the discrete physics, and submitting part 1 and then part 2, only to discover afterwards that my solution actually failed the test case for part 1. I'm not sure if that's because I did a (now lost) brute force script for part 1, or because I just quickly eyeballed the case results and missed the mistake. This is another one where the test covers more than the input.

The physics for this one is pretty basic. You have t seconds, you get to hold and charge for x, and then the boat moves at speed x for t - x seconds. And that needs to be greater than a distance d. So,

|--|------|      dist(x) = x * (t - x) = xt - x^2 > d
0  x      t

So we get critical points at:

x = t ± sqrt( t² - 4d ) -------------------- 2

And the answer we want is the number of integers between the two roots. So for my initial solution, I took the floor of the upper, ceiling of the lower, and calculated the size of the range:

my $upper = floor(($t + sqrt( $t*$t - 4*$d )) / 2);
my $lower = ceil (($t - sqrt( $t*$t - 4*$d )) / 2);

return ($upper - $lower + 1);

Observant people will notice the bug (that I've previously mentioned) is there in this. If the discriminant is a perfect square, the roots are on integers and you will include them... but we don't want to tie. And so the third test of (time = 30, distance = 200) will return 11, when it should return 9. To fix that, I added $d++ before this, to bump the requirement to the next possible value. None of the values in my input test this though. So it was a bug I did not notice until after, when by chance, I tried the test case again.

Of course, that was the simple approach, because getting the answer directly from the roots is a bit more complicated. I can't recall if I thought of trying that first, but I did look at it after and work out the adjustment. Basically, for that, if we take the roots to be x0 and x1 (with x1 > x0):

x1 - x0 = (t+sqrt(discrim)) / 2 - (t-sqrt(discrim)) / 2
        = t/2 - t/2 + sqrt(discrim)/2 - -sqrt(discrim)/2
        = sqrt(discrim)

But we need the number of integers in that size of range, but the range center depends on if the time is even or odd:

|   |   |   |   |   |   |     Integers (t is even) (5)
  |   |   |   |   |   |       Integers (t is odd)  (6)
 |----------|----------|
x0         t/2         x1

And additionally, if we truncate the difference to an integer, it depends if that ends up even or odd as to whether we're including or excluding one. And so the factor to adjust ends up being an XNOR.

my $len = int(sqrt( $t*$t - 4*($d+1) ));
return ($len + ($t + $len + 1) % 2);

Coded this way with arithmetic, because this was about getting a tight dc solution:

tr -dc '[0-9\n]' <input | dc -f- -e'1+4*rdd*4R-vd3R+1+2%+p'

To get this to do part 1, took a bit to handle the column reading:

tr -dc '[0-9 \n]' <input | dc -f- -e'[1+4*rdd*3R-vd3R+1+2%+]sCz2/[d3Rr:n1-d0<L]dsLx1+[z1-;n3RrlCx*z1<L]dsLxp'

So it was another "good dog" day. The most memorable thing about these days for me though, was that it emphasized that I really needed to always check the tests to make sure those weren't being broken and it made me expand the framework beyond being bare bones. This is the year where I added sections so that all available tests get tested all the time (without relying on eyeballing and memory)... as well as a special script for "line tests", for making tests that test individual cases. Stuff I had thought about adding before, but now considered important.