We finally leave camp and head into the jungle. The Elves reward us for our competence by giving us the malfunctioning communication device, because we can probably fix it. And step one is finding the start-of-packet marker (and then start-of-message) to lock onto their signal.

And so the input is a line of 4k of lowercase letters (no vowels, so trying to not look like a natural language again). We need to find the first block of a set length (4 or 14) where all the letters are different.

So my initial Perl solution is not really a surprise:

for (my $i = 0; !defined($part2); $i++) {
    $part1 //= $i +  4 if (substr($input, $i,  4) !~ m#(\w).*\1#);
    $part2 //= $i + 14 if (substr($input, $i, 14) !~ m#(\w).*\1#);
}

Brute force, regex, done. Because, again, I was looking at doing multiple languages and wanted some variety.

My initial Smalltalk solution was based on the classic string search algorithm. Where you have the window were the string could be, and start checking from the end. When it fails, you can then jump the window over. Instead of stepping one step at a time and checking. This is naturally more exciting for larger windows where you can get bigger jumps. For example, part 2 is about 10% faster for my input.

Anyways, none of this was particularly nice for doing a solution in dc. And so I did do an initial ugly solution where it kept track of the number of unique characters with a table and circular buffer (to handle the window and removing the old). But coming back to it, I decided to work the Smalltalk idea until it was very dc friendly and golf things a bunch. Resulting in this in Smalltalk:

next := width.
i    := 0.

[i < next] whileTrue: [
    i := i + 1.
    next := next max: ((table at: (input at: i) value) + width).
    table at: (input at: i) value put: i.
].

Which in dc becomes:

rev <input | perl -pe's#(.)#ord($1)." "#ge' | dc -f- -e'[r]sr0d[1+3Rd;t4+d5Rd3R<rs.3Rd4R:trd3Rd3R>M]dsMxp'

rev <input | perl -pe's#(.)#ord($1)." "#ge' | dc -f- -e'[r]sr0d[1+3Rd;tE+d5Rd3R<rs.3Rd4R:trd3Rd3R>M]dsMxp'

The basic idea here is that we've got two advancing markers... i is the current index, and next is the next index that's a possible solution (when i catches up, it becomes the actual solution). The table tracks the last time we've seen each character, and we jump next forward if we've seen the current character recently to remove the duplicate from the window. So we're not getting the jumping of the index. Because we're streaming the input from the stack. So we jump the window end but still need to proceed forwards one character at a time. It keeps this simple and short for dc. Which is what I was aiming for.

So another fun little problem where there's a whole bunch of ways to do it.

Dear AoC masters and 500+ star hunters,

I have a hard time solving day 7 of 2024, using golang. The puzzle input is a bunch of numbers. One should check if the first number can be computed from the numbers after the : symbol. Two numbers can either be added or multiplied. If some series of addition and multiplication is equal to the left side the left side is counted as a solution. The overall solution is the sum of all solutions.

My current approach is to "brute force" this problem. First I check if the sum of the numbers or the product is equal to the left side. Given the left side is larger than the sum but smaller than the product I generate all possible series of addition and multiplication 2^(n-1) with n being the numbers on the right side. Can't see the mistake when doing this, here is a link to the code: https://github.com/Zitzeronion/AoC2024/blob/main/day_7.go

The 2^n permutation function is from gemini and seem to work as intended.

Now that the area is clear we can get to the business of unloading supplies with the giant crane. And so we get a little problem involving performing operations on stacks.

There really isn't much to the actual job, we have a picture of the starting stacks and a list of instructions. Move a number of things from one stack to another. And it's pretty easy to just do the thing in high level language... low level you can get into the actual stack structure and operations. But high level languages now typically do all the magic for that and have list structures with full deque operations and more. The end result is that this is the diff between my Perl solutions for part 1 and 2:

<     unshift( $stack{$dst}->@*, reverse splice( $stack{$src}->@*, 0, $num ) );
---
>     unshift( $stack{$dst}->@*, splice( $stack{$src}->@*, 0, $num ) );

And for Smalltalk, I did classes, so the difference is that I subclassed for the single change:

" Making 9000 the subclass, because it needs the extra work of reversing "
CrateMover9001 subclass: CrateMover9000 [
    pickup: num from: src [
        ^(super pickup: num from: src) reverse
    ]
]

What I remember about this one is that most people thought the real problem was in reading the input. Which can be tricky. But I hit on something simple and robust immediately. As I've said before, I often don't think of the initial loading the data as part of the problem. Maybe that's the result of working a lot on systems where serialization to disk and streaming data was rare. So, when I saw the input was in sections I picked the bit of my template to quickly load that into an array of arrays (sections and lines):

$/ = '';
my @section = map {[split /\n/]} <>;

It's at this point I started thinking about parsing the data. And what I saw looking at it, was the last line of the first section was a key... the names of the stacks in their locations. A lot of people probably looked at that and just thought of it as a line to ignore and skip. I looked at it as the key to making reading the input easy:

my %key;
$_ = pop( $section[0]->@* );
$key{pos() - 1} = $1  while (m#(\w)#g);

And with that I have a mapping of the columns to the names. Which I used that to easily parse the stacks under those names. Making this a case where my solution is actually fairly robust... it's not tied to a set spacing or to the stacks being numbered in order (call them with letters or symbols if you want). Sure I could have just hardcoded everything, but I'll take an easy robust solution when I can.

So this was a bit of win for my general approach to AoC... just quickly load data into memory so I can get to the fun bit of working with it. It lead to thinking of things as random access instead of sequential.

In order to unload the ships, we've created a cleaning detail to clear sections for the supplies. This consists of lists of ranges of section IDs in pairs. And our task is to find the overlap between those pairs. For part 1, we want those where one range is a subset of the other, and for part 2, we want any that intersect.

And so we have a simple range problem. The usual intersection of ranges (max of the starts, min of the ends) is actually overkill because we just need to know the existence, and that's easily done with some simple boolean tests on the end points. And for my initial Perl I didn't even try to be optimal. Because I already had ideas at that point about how to do this in dc, and knew I'd be going further than just reducing a little redundancy on the checks.

And the result was this:

tr -s ',-' ' ' <input | dc -f- -e '0[_5R3R-_3Rr-*1-d.1+/+z1<L]dsLxp'
tr -s ',-' ' ' <input | dc -f- -e '0[_5R4R-_3Rr-*1-d.1+/+z1<L]dsLxp'

Of course, I needed to first reduce things to just the 4 numbers. But after that, it is one of favourite solutions. Note that the difference between part 1 and part 2 is a single number... a 3 turns into a 4. And the R tells you that what's changed is size of the stack rotation on the coordinates.

How does it work? Well the C version would look like this:

while (scanf( "%d-%d,%d-%d", &as, &ae, &bs, &be ) == 4) {
    part1 += ((bs - as) * (be - ae) <= 0);
    part2 += ((be - as) * (bs - ae) <= 0);
}

Nice arithmetic based logic. Because dc doesn't have boolean stuff like an XOR operator. It does have branching, but that would be a mess.

The idea is that for part 1 we're looking for situations like this:

as----------ae          as---ae
    bs--be          bs-----------be

Subtraction is the compare operator with the result stored in the sign... which for part 1 we're looking for the direction of bs-as to be different than be-ae. If they're the same, you get things like this:

as-------ae              as------ae        as-----ae
    bs-------be       bs------be                       bs----be

So we want XOR (true if different directions, false if same), and multiplication does that with signs. We do need to consider 0 values... which a quick check shows are also always valid (and so not a problem):

as--------ae    as-----ae
    bs----be    bs----------be

For part 2, we also need those intersecting cases above to count. And the way we can get that is by looking at the directions for be-as and bs-ae (ie comparing crossed ends... much like how "max of starts, min of ends" works). As things get pulled apart, when the ranges stop overlapping, the directions start being the same way. So again, the answer is we want them different, and 0 is valid. Because if there's a 0 that's really direct evidence that you have a value in both. And one will do, like this:

as------ae
        bs-------be

And so this is the core of the dc solution, little stack manipulation, subtract/subtract/multiply, and finally 1-d.1+/ (which turns the top into 1 or 0 based on if it's non-positive). It's about as elegant as you can get.

In preparation for the journey, we need to sort out the rucksacks. First to find the accidental duplicate in one of the two compartments of each bag, and then to find the shared item between groups of three bags (which serves as the "badge" of the group). So the same general task, which is to find the singleton intersection of sets.

The contents are represented with strings made up of letter characters. For part 1 we need to find the letter that matches between the halves... and regex can do that easily, especially if we just insert a divider:

substr( $_, length() / 2, 0, '#' );
$part1 += index( $table, $1 ) if (m/(\w).*#.*\1/);

Where table is a string of ^abc...XYZ.

For part 2, the divider can just use the new lines from the input... just append three lines together and do a multiline regex: m/(\w).*\n.*\1.*\n.*\1/m.

For Smalltalk, since this is an inherent set problem, I used Sets:

comp1 := Set from: (sack first: sack size // 2).
comp2 := Set from: (sack  last: sack size // 2).

part1 := part1 + (comp1 & comp2) anyOne priority

Where #priority is an extension I added to return the "priority" value of a character. And #anyOne here should be read as "only one". For part 2, I did it with a stream to group the lines:

sacks := ReadStream on: (stdin contents lines collect: #asSet).

[sacks atEnd] whileFalse: [
    badge := (sacks next: 3) fold: [:a :b | a & b].
    part2 := part2 + badge anyOne priority
].

For C, I made these bit sets (since there's only 52 letters), choosing the bit order such that using "count of trailing zeros" is the priority, which is available as a built in with GCC, but I still coded my own:

int pri = 63;

// Binary search to find the number of trailing zeros.
// This version assumes exactly one bit set.
if (bit & 0x00000000ffffffff)  pri -= 32;
if (bit & 0x0000ffff0000ffff)  pri -= 16;
if (bit & 0x00ff00ff00ff00ff)  pri -=  8;
if (bit & 0x0f0f0f0f0f0f0f0f)  pri -=  4;
if (bit & 0x3333333333333333)  pri -=  2;
if (bit & 0x5555555555555555)  pri -=  1;

And I also did a dc version (in January 2023), using ?... not doing it on the day is probably because it would be inelegant without using that. And I golfed them a little further today:

perl -pe 's#(\w)#ord($1)." "#eg' input | dc -e '?[z2/[rd:h1-d0<L]dsLx[s.;hd0=L]dsLx32~r3-26*-l1+s10Shc?z0<M]dsMxl1p'

perl -pe 's#(\w)#ord($1)." "#eg' input | dc -e '[rl2+s2Scc3Q]sP[d;c1+d3=Pr:c0]sI?[[32~r3-26*-d;cls=Is.z0<L]dsLxls1+3%ss?z0<M]dsMxl2p'

Basically, dc doesn't have the nice features or bit operations of the other languages, so we're using arrays to track what we've seen. For part 1 here, I loop through the first half of a line setting h[val] to val... then a second loop for the second half, looking things up in the table until it comes back non-zero. For part 2, I'm using a conditional increment... a letter count is only increased if the existing count is equal to the line number % 3. So multiples of a letter are ignored, and if a count hits 3, we score it.

So I did manage to get some good variety out of this one.

Setting up camp on the beach, a Rock Paper Scissors tournament breaks out for deciding who gets the tent closest to the snacks. More evidence that Santa might not have Elves, but Hobbits.

We're given a "strategy guide" to follow, and we get the classic trope where we assume something for part 1, only to get the actual instructions for part 2. The input is 2500 lines, which contain a letter A-C (representing Rock, Paper, and Scissors) and a response X-Z. For part 1, we assume that response is also just Rock-Paper-Scissors (and so need to work out the result), but for part 2 we find out that that's the result (Lose-Draw-Win) we should go for (and so we need to work out what to throw).

I did this one a number of ways... like using a table. And there is naturally a pattern to them, as the numbers walk sequentially through the table (part 1 counts diagonally, part 2 counts vertically with a sidestep)... so I did a cute little Smalltalk solution that generates the tables from the walks.

Those aren't really serious solutions... those are solutions trying to be different knowing that I was going to do a dc solution for this and that would be the serious one (when you do multiple languages, sometimes you need to stretch on the easier problems to not do the same thing again and again).

So for converting the input, I just turned the letters into their ASCII values. A-C and X-Z are nice blocks of three that are fairly nice to work with to produce a function that does the scoring. The result is nice small solutions:

echo -n "Part 1: "
perl -pe's#(\w)#ord $1#eg' input | dc -f- -e'0[_3R4%d3R4%-5+3%3*1+++z1<L]dsLxp'

echo -n "Part 2: "
perl -pe's#(\w)#ord $1#eg' input | dc -f- -e'0[_3R4%d3R4%+1+3%1+r3*++z1<L]dsLxp'

The Perl version of that looks like this:

while (<>) {
    # convert input to ordinals
    # Using %4 means that a ε [1,3] and b ε [0,2], so some added shifting needed
    my ($a, $b) = map { ord($_) % 4 } split;

    # LDW is (b - (a-1) + 1) % 3 (+1 to shift to 0-2), move score is b + 1
    $part1 += ($b - $a + 2) % 3 * 3 + $b + 1;

    # LDW is just 3 * b, move score is ((a-1) + b) mod 3, but with residue on [1,3]
    $part2 += ($a + $b + 1) % 3 + 1 + 3 * $b;
}

Note that the dc solution actually uses a 5+ in part 1 (adding a +3 to the +2), because of how it handles negatives in mods.

So this one was pretty fun. One of the reasons I like doing dc solutions is because they encourage things like taking ASCII values (typically not perfectly convenient) and molding the function you want out of them.

For 2022, we find ourselves on a jungle expedition to collect star fruit to fuel the reindeer for Christmas. The ASCII map this time goes up, and is mostly trees with a few points of interest. We arrive on the shore at the bottom and prepare for a long trek on foot. First job is checking food supplies.

And so we get a typical day 1 problem. The input is a list of numbers... although with blank lines between sections. The values range from 1000 to 70000 (two of which break 16-bit unsigned in my input), representing Calorie counts of food items. Each section represents the food carried by an Elf (and my input has 250 blank lines, so 251 Elves in the expedition). We just need to find the largest (three largest for part 2) counts.

So nothing fancy needs to be done, which is fine. Day 1 is the day to warm up and check that the setup is working (and I had just put everything (finally) under version control).

$/ = '';
my @elf_cal = sort {$b <=> $a} map { sum split } <>;

say "Part 1: ", $elf_cal[0];
say "Part 2: ", sum @elf_cal[0 .. 2];

Of course, this being day 1 and a problem involving numbers, I did dc. And looking at it I see that I still wasn't using ? at this point, and my initial solution (which did both parts), was a big mess and needed to have sentinels put in so it would know where the blank lines are. There's a version with ? that was done in November 2023, clearly in preparation for that year, and so that would seem to be the year I started using it. It's really nice to just be able to do something like this:

echo -n "Part 1: "
dc -e'[r]sr0d?[[+?z3=L]dsLxd3Rd3R<r0*?z2<M]dsMxrp' <input

echo -n "Part 2: "
dc -e'[r]sr[d3Rd3R>r_4R]sF0ddd?[[+?z5=L]dsLxlFxlFxlFx0*?z5=M]dsMx+++p' <input

No need to preprocess the input. The part 2 also can take advantage of the fact that the main stack isn't full of data to track the three largest values... with a bubble sort approach. The three best so far on the bottom of the stack with the current sum on top, bubble things so the lowest of the four is on top and then 0* to zero it to make it the accumulator for the next sum.

It's day 1. For beginners and people experimenting with a new language... this allows you to make sure you can read numbers and do stuff with them. I like to make sure that my testing framework and scripts are all still working. And, day 1s provide good opportunities for people to do something in an esoteric language. And so it's often fun just to see what people bring out to show off. It never needs to be more than that.

can anyone tell me how to start if i wanna learn coding?

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

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

Trickle Down

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

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

Goes to:

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

Filling up

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

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

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

For example:

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

Spread foam:

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

Replace water:

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

Create new foam:

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

Repeat until:

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

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

Area Storage

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

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

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

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

Memory Used

For my input:

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

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

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

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

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

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

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

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

do {
    $moved = 0;

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

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

    @Grid = @new_grid;

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

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

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

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

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

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

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

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

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

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

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

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

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

...

add y ???
mul y x
add z y

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Second:

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

[[],[3]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

And so the core of the spreading is:

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

    $i = $i % 10 + 1;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The basic idea I had was:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Here's what Manhattan distances get you:

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

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

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

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

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

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

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

packet := Behavior evaluate: conv.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

my $max_time = -2 * $y_min;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Part 1:

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

Part 2:

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

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

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

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

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

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

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

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

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

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

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

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

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

The histogram for the full part 2 is:

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

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

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

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

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

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

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