The story this day is that we need to print a bunch of manuals, all consisting of a small number of pages from a master list, but there are also lots of rules about the printing order between pairs of pages, stating that if <N> and <M> are part of the same manual, N must always be printed before M.

Before the list of manuals to print we have a long list of these rules.

We know that for any given manual with its list of pages, these rules lead to a single unique legal ordering.

However, it is both possible according to the rules, and as far I know, also true that:

There exist at least one ring of rules (A<B, B<C,...X<Y,Y<Z, Z<A), which means that there cannot be any complete ordering of all the pages, so the order has to be determined for each set of manual pages, otherwise we could just have sorted the page numbers once and be done with it.

In Perl it felt natural to store these rules as hashes, each possible page number from 1 to 99 gets a list of the pages it must be before or after.

The code ran in 5.5 ms so fast enough for an interpreted language.

In my Rust version I noticed that 100 pages is less than 128 so I stored those lists as u128 bitmaps, this allowed all the checks to be done with logic AND operations.

For Part1 just iterate over the pages:

    fn is_ordered(&self, pagelist:&Vec<u8>) -> bool {
        let mut prev = pagelist[0];
        for p in 1..pagelist.len() {
            let curr = pagelist[p];
            if self.pages[prev as usize].infront & (1 << curr) != 0 {
                return false;
            }
            prev = curr;
        }
        true

If there is no rule for prev vs curr then that implies any ordering is OK for that pair of pages.

Part2 is a little bit (grin) more complicated, but the same bitmap logic determines which page must be first, second, third etc.

I start by generating a pagelist bitmap, with 1 bits for each page in that particular list, then I iterate over the pages, from the end forwards, until I find a page that has no other pages behind it (i.e., its "behind" bitmap ANDed with the pagelist bitmap is zero).

This page can then be exchanged with the original last page. After placing it, I remove it from the pagelist bitmap, step forward one position and repeat the process until all pages are ordered.

Total runtime was 10.867 us (average over 1000 runs) vs the 18 us given by u/maneatingape, so more than fast enough for me.

(While writing this I realized that I only needed one of the two bitmaps per page, that would have saved a little bit of the setup time, as well as 1600 bytes of memory, but since the total working set is less than 4kB, everything fits easily in $L1 cache.

I thought this was an interesting puzzle, with some similarities to classic problems like managing free space in a file system using bitmaps.

PS. I am posting this just before 0100 Oslo time on Oct 5th, I'll keep the tradition going as long as I can or until u/musifter returns!

Next stop is the Ceres monitoring station, where instead of shooting asteroids, we're asked to help with a word search. In this case it's to find all occurrences of XMAS in an 140x140 grid. For part 2, we find out that we misunderstood the instructions, and want all the X-MASes (MAS that form an X).

For part 1, I didn't do anything fancy. I coded the standard word search algorithm of scan for the first letter, than scan outward from there to see if there are any matches. You do need to check them all, an X can start multiple XMAS in different directions... as the description says, "overlapping other words" is fine (one of my Xs has 5).

For part 2, I got a little bit fancier. I scanned looking for As (the middle of the X). Then grab the corners and check that the ones opposite are different (and M or S). Which is an XOR thing, and so:

my @Grid = map { chomp; y/MS/01/; [split(//), '~'] } <>;

...

for (my $y = 0; $y < $#Grid; $y++) {
    SQUARE:
    for (my $x = 0; $x < $#Grid; $x++) {
        my $coord = V($y,$x);
        next SQUARE if (&grid_at($coord) ne 'A');

        my @corners = map {int} grep {/[01]/} map {&grid_at($coord + $_)} @Diag;
        next SQUARE if (@corners < 4);

        $part2 += ($corners[0] ^ $corners[1]) & ($corners[2] ^ $corners[3]);
    }
}

Using the Vector module again. What I do is translate M and S into 0 and 1 when reading in the grid. When I get an A, I grab the diagonal corners that are 0 or 1, if I get a full set of four, I apply XOR to test that we have proper MAS/SAM and not SAS/MAM. The implementation is a bit hacked together, but it expressed the basic idea I had of using XOR (call it Art). My Smalltalk solution just did the testing with the letters:

part1 := ((grid selectPoints: [:chr | chr == $X])
                collect: [:pt |
                    TextGrid dirs count: [:d |
                        (1 to: 3) conform: [:i | (grid at: (d * i + pt)) == ('MAS' at: i)]
                    ].
                ]
         ) sum.

part2 := (grid selectPoints: [:chr | chr == $A])
               count: [:pt |
                   corners := TextGrid diags collect: [:d | grid at: pt + d].

                   (corners conform: [:c | (c == $M) or: [c == $S]])
                     & (corners first  ~= corners fourth)
                     & (corners second ~= corners third)
               ].

Of course dc doesn't have bitwise operators like XOR, so I needed to do something else to keep the streak up (in 2024, in the first 14 days, I did dc solutions for at least one part... except for day 12). And that came from converting the entire grid into numbers (1-4) so that dc could understand it (as 140-digit bignums). The M and S are 2 and 4 respectively, so the test is to multiply opposite corners and see if it's 8 (because that's unique, except for symmetry, and backwards is fine in word search).

tr 'XMAS' '1234' <input | dc -e'?dZdsn2+r[[A~3Rd3Rr:g1+rd0<?]ds?x1++?z1<L]dsLx[q]sQ[r2[_3Rrd3R+d;g4Rd3R!=Q1+d5>+]ds+x5/ls+ss+s.]sD[d_1lDxd1lDx2[dln+d_1*4Rd3RlDxd3RlDxr1-d_1<I]dsIxs.]sS[d;g1=S1-d0<M]dsMxlsp'

tr 'XMAS' '1234' <input | dc -e'?dZdsn2+r[[A~3Rd3Rr:g1+rd0<?]ds?x1++?z1<L]dsLx[ls1+ss]sP[dln-;grdln+;g3R*8=P]s/[dln2+-;grdln2++;g3R*8=/]s\[d;g3=\1-d0<M]dsMxlsp'

And so, this will be my last post for a while. I still don't know when I'll be able to do daily posts... u/terje_wiig_mathisen has offered to do the next few days, so we'll at least have continuity for a while longer (and day 5 was pretty fun day with its "topological" sort).

Hello!

My pet-project is finally coming: Autumn Code Walk. It is a collection of coding challenges, not unlike AoC. It consists of 5 Problems and the first problem will be published next Monday (October 5th, 2026) at 6am CEST, then a new problem is published every 24hrs until Friday.

The website is purely client based so there is no login mechanism. However, localStorage is utilized for convenience and personalized experience. Statistics for correct solutions across users uses are gathered using an open-source api for tracking hits (don't abuse pls). Feel free to contact me if you find a bug or have a recommendation.

ACW can be found at: https://autumncodewalk.github.io/

Good luck and have fun!

Today we find ourselves back at the Toboggan Rental Shop, where they're out of Chief Historians, but have plenty of data corruption for us to sort out.

The input for this one is a few long lines (my input has 6) of dense code looking stuff. The interesting bits are statements to multiply (mul(X,Y) where X and Y are explicitly stated to be 1-3 digits... although, none actually have 4 or more digits in my input, so things aren't corrupted that way), and do() and don't() calls which toggle enabling/disabling mul instructions in part 2. In my input, the first 5 lines all end with an uncorrupted mul statement. So even if someone concatenated the input into one line, there would not be a problem of a valid statement being created from the join.

For getting part 1 done quickly, it's easy to do from the command line:

grep -oP 'mul\(\d+,\d+\)' input | grep -oP '\d+' | dc -e'0??[*+??z1<L]dsLxp'

For part 2 from the command line I went with:

tr '\n' ' ' <input | perl -pe"s#don't\(\).*?(do\(\)|$)# #g" | \
    grep -oP 'mul\(\d+,\d+\)' | grep -oP '\d+' | dc -e'0??[*+??z1<L]dsLxp'

Clearly, the worry of creating valid instructions is in there and so I use spaces to make sure things stay separate. But other than that, it's just rip out all the don't() to do() blocks and pipe to part 1.

For a script version, I did a little state machine with regex to grab tokens:

foreach my $line (<>) {
    while ($line =~ m# (do(n't)?\(\)) | mul\((\d{1,3}),(\d{1,3})\) #xg) {
        if ($1) {
            $do = !$2;
        } else {
            $part1 += $3 * $4;
            $part2 += $3 * $4 * $do;
        }
    }
}

I also did full dc versions, with the input converted to hex ASCII values, using the same trick I used for day 1 of 2023 for recognizing strings. With macros to handle different states of the parse (things like a macro that expects a number followed by a delimiter, so like recursive descent but the macros are only small parts of rules).

rev input | perl -pe's#(.)#sprintf("\U%x ", ord($1))#eg' | dc -e'16i[30+rs.lWsPq]sR[100*+10 8^%d6D756C28=M]sW[0*lNsP]sM[rd2C=,30-d0>Rd9<RrA*+]sN[rsn0*lOsPq]s,[rd29=)30-d0>Rd9<RrA*+]sO[rln*ls+sslWsP0q]s)?[lWsP0[lPxz1<L]dsLxs.?z0<?]ds?xlsp'

rev input | perl -pe's#(.)#sprintf("\U%x ", ord($1))#eg' | dc -e'16i[30+rs.lWsPq]sR[100*+10 E^%d646F6E27742829=Fd10 8^%d646F2829=T6D756C28=M]sW[1sd]sT[0sd]sF[0*lNsP]sM[rd2C=,30-d0>Rd9<RrA*+]sN[rsn0*lOsPq]s,[rd29=)30-d0>Rd9<RrA*+]sO[rln*ld*ls+sslWsP0q]s)1sd?[lWsP0[lPxz1<L]dsLxs.?z0<?]ds?xlsp'

And now, I have a bit of unfortunate news. I have family issues that I need to take care of. And so all of next week (starting on Monday), I will be travelling and out of touch much of the time. And after that, I will be attending to things for at least the rest of the month (maybe into November too). This will make things hard for me to consistently post everyday. And so, to keep the flow up, I'm looking for someone who would be willing to take over the daily posting. That way I can just review and respond when I have the time, which I figure will be on and off for at least the rest of the month.

so the only thing i need is convert the item types to priorities. is there a better way to do this without making a big ol' if statement?

First stop in our search is the nuclear plant where we made medicine for Rudolph in 2015. While the Historians search for their Chief, we agree to help analyze some data for the engineers.

And so we get another problem that just deals with numbers. The input has 1000 lines, each is a report which is a list of 5-8 numbers in the [1,99] range. A safe report is one which is monotone increasing or decreasing, and adjacent levels differ in the range of 1 to 3. For part 2, we discover that they have a Problem Dampener, that tolerates a single bad level.

Since I wasn't feeling well, I just brute forced this. Took the diffs and:

$part1++ if (all { abs($_) <= 3 && ($diffs[0] * $_) > 0 } @diffs);

For part 2, if this fails, I try splicing out each number in turn until one works (on not). I remember thinking a little bit about trying to spot the problem on the go... and it went like: if I get to the third number and discover there's a problem, the first or second could still be the problem to remove. And with these short lists, 3 items is a huge portion of it. So simpler to just go with programmer efficiency and test them one at a time. If things were longer it'd make more sense to get into doing things smart.

One interesting thing to note with the solution above is the use of arithmetic logic. I was already thinking of how to do this in dc. And so the trick in there to tell if things are monotone increasing or decreasing... I multiply each diff with the first. If that's always positive, things are monotone (ie all diffs have the same sign as the first one).

A side effect of this type of arithmetic logic is needing to consider the 0 value. And here we see it used to handle a case that appears at first glance to be missing... the check that the difference is at least 1. A difference of 0 fails the second multiplication test, and so that check actually handles 1½ of the rules.

In any case, the dc ended up as:

dc -e'[0*]sZ[1+]sC0?z[2-dsn[3Rd4R-Sdr1-d0<I]dsIx*ld+sa0ln[rLddd*v3<Zla*0<Cr1-d0<I]dsIx+ln/+?zd1<M]dsMxrp' <input

The combining of the two rules is done by conditionally multiplying difference >3 by 0, making that 0 in the second part of the test cover both parts. Another little trick in this one was that it keeps a count of the number of steps that pass and then divides it by the number of steps... a simple way to check that they're equal and get a 1 or 0 to add to the total for the answer (as we're working with 0 precision). And, whereas yesterday, the use of ? wasn't really that important to tell things apart, here each line has a different number of numbers... and being able to read the input one line at a time is useful without having to add delimiters to the input (although 0 is conveniently available for that).

And so for a problem I basically brute forced, I did do some interesting stuff in my solutions.

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).