In order to get a better signal for our communication device, we use it to find a nearby hill. And so we're tasked with finding an efficient path up to the top (that doesn't require going up more than two levels on any step).

The input is a relief map in landscape (mine is 41 lines of 154 characters). Where elevation is represented by the letters a-z... with S and E used to mark the start (elevation a) and end (elevation z). The left column is all a (including the start), followed by a column of b, followed by a large plain of c with many large holes of depth a. At the right there's a hill with a spiraling path up it to the end.

One thing I remember about this one is that it has spawned threads of people that missed that you can always go down as much as you want (the only limit is that you cannot go two higher). And the map has a check that you've implemented that correctly on the spiral (on mine you need to go back to j from l in order to continue up the path).

The nature of the map and final path means that BFS is fine for this. Using A* can direct you to cross the plain quicker if you want. But then part 2 shows up. And for it, it wants the shortest path from an a to the E... which is clearly best done by searching from E with a BFS (which is going to whip around that mountain) until you find you find the first a. And with that, you can easily include part 1 in that solution, by continuing until you get to S as well.

And so we get a search problem that isn't that heavy. The map presents opportunities for people that want fast times to specialize the search based on knowledge of the map structure. But using heuristics like that can also allow a beginner programmer to get a solution, because with the structure and blockiness of the map, you could even do this problem by hand if you wanted to.

While making our way upriver, some monkeys grab some of the stuff from our backpack and we need to get it back (while they keep away), while trying not to worry too much.

The input describes 8 monkeys, each with a starting list of items (with 2-digit worry levels), an expression for how to modify the worry level for an item for that monkey, and a section that describes a divisibility test (using the first 8 prime numbers) with the monkeys to throw to if it passes or fails. And so the input requires a bit of parsing... although for the most part you can ignore everything but the numbers. The exception being the "Operation" line which has a simple arithmetic expression: either adding/multiplying with a constant or squaring the old worry level.

And so, I naturally turned the input into code (hello, Bobby Tables):

my %p = map { (m#(\w+):#) => [m#(\d+)#g] } @desc;

$desc[1] =~ s#new = (.*)#$1#;
$desc[1] =~ s#old#\$_[0]#g;
$monkeys[$n]{op} = eval "sub { $desc[1] }";

$monkeys[$n]{pass} = eval "sub {(\$_[0] % $p{Test}[0] == 0) ? $p{true}[0] : $p{false}[0]}";

For part 1, we get a rule to reduce the worry levels by dividing by 3. For part 2, that's removed. And the description mentions multiple times that this means "ridiculous levels" of worry and the need to "find another way to keep your worry levels manageable". And it means it.

Because this isn't one where you can just invoke "bignums"... the fact that one monkey squares the worrying means that the worry levels quickly exceed the number of protons in the observable Universe (not a problem), and soon after they have a number of digits that exceeds the the number of protons in the observable Universe (which is very much a problem). So the numbers cannot be stored... this is a case where it's very good to have limits set on how much resources your processes can use.

But not being able to store all the digits isn't a problem, because we can easily describe how to compute the number, and so we can use that to extract information about the number. And that's what we need to do to keep the worry level manageable.

As for how... well, it's divisibility and so the answer is pretty much always LCM (Least Common Multiple) and modular arithmetic. And since I was using anonymous subroutines for other parts, I did that here too:

print "Part 1: ", &run_monkeys(    20, sub { floor( $_[0] / 3 ) } ), "\n";
print "Part 2: ", &run_monkeys( 10000, sub { $_[0] % $modulus   } ), "\n";

Where $modulus is just the LCM of all the test values (which, since the values in the input are all different primes, is just the multiplication of them). Which for the first 8 primes, is 9699690. I do remember someone doing this problem on a C-64 with 16-bit integers, and IIRC, they broke it into two parts covering 4 monkeys each. Although, you could also just track all 8 modular values for each number.

In coming back to it, I was curious how big my worry levels get... and so I quickly modified it to also track the log of the length of the numbers. And the answer I got was about 9 * 10⁵⁰⁴ bits in length.

This probably is definitely a memorable one... maybe not for the job that needing doing, but for the size of the bomb the input contains.

Having plunged into the river and separated from the rest of the expedition, we pull out our communication device to find it in need of repair again. This time we need to work on the clock circuit for the display.

And so we get what's marginally an assembly problem. Two instructions, one of which is noop, and the other is addx. For part 1 we want to collect the values at times 20 mod 40. For part 2, we use the timing of the values with the raster beam to produce an image.

For my initial solution I just parsed the input as text and added a noop for the extra cycle that addx took. But in doing that, and thinking about how to do this in dc (I do like to do these ASCII art problems in dc), it immediately became apparent how to turn the opcodes into numbers that dc can parse. Namely, noop has one word and takes one cycle, addx V has two words and takes two cycles... so just turning all the opcodes into 0s provides the correct timing when we just treat the result as a list of 1-cycle adds to the register. In Perl, that looks like:

foreach (map {tr/a-z/0/; split} <>) {
    $display .= (abs($regX - $time % 40) <= 1) ? '#' : ' ';
    $part1 += $time * $regX  if (++$time % 40 == 20);
    $regX  += $_;
}

And for dc I did this:

tac input | tr -s -- '-a-z' '_0' | dc -f- -e '[d3Rd3R*ls+ssr]sS1d[1+d40%20=Sr3R+rz2<L]dsLxlsp'

tac input | tr -s -- '-a-z' '_0' | dc -f- -e '[AP]sR[d3Rd3R*ls+ssr]sS33P1d[d40%d0=R3Rd3R-d*v2r-d.1-/32+Pr1+d40%20=Sr3R+rz2<L]dsLxlsp'

So it wasn't a typical assembly/VM machine problem, but still quite fun.

We get to the rope bridge on the map, and decide to model rope physics as we cross. Even while falling after the bridge breaks.

The input is a list of absolute direction moves for the head of the rope to take (UDLR and a number of steps, at most 19). The rest of the rope follows along... moving when it has to (Chebyshev distance > 1 from the piece ahead), and otherwise staying at rest (as Newton says it should). For part 1, we only have one piece in the tail, for part 2 we extend it to 9. And we want to track how many different locations those end up in.

So I just did the very basic thing of a straight simulation. Since we want all the in-between spots the tails rest on, not just those at the end of the move, that's a pretty good reason to just do the moves stepwise... iterating for the number of steps and pulling the rope along, and throwing the tail into a set/hash to record the unique places it lands.

There are a few little things to work out from the description, like the vector for movement. But just looking at the examples and reading it... I immediately thought "roach movement from DROD". That's not the first or best example of it, but I'd played a lot of DROD. And DROD looks like a hack-and-slash dungeon crawler, but is perfectly deterministic hand designed puzzle game (most of the time). Where puzzles often require you to keep monsters alive and manipulate them into positions. Which means that the movement patterns get really ingrained. So I did end up calling the subroutine to calculate the vector (which just uses <=>) "roach_move".

So this was another one of just doing the thing and staying away from any potential chaos that the rope movement might bring. The problem is small so it's fine (2000 lines, 19 steps max, 10 knots).

Back when we looked at this one, about a week ago, I said that I would like to write a proper bleeding edge (unsafe{}) AVX intrinsic version, well I finally got it done and I'm quite amazed:

        for b in 0..blocks {
            let bl = input.as_ptr().add(b*64) as *const __m256i;
            let b1 = _mm256_loadu_si256(bl);
            let b2 = _mm256_loadu_si256(bl.add(1));
            let b1h = _mm256_and_si256(b1, xyz_mask);
            let b2h = _mm256_and_si256(b2, xyz_mask);
            let b1l = _mm256_and_si256(b1, abc_mask);
            let b2l = _mm256_and_si256(b2, abc_mask);
            let b1h = _mm256_srli_epi32(b1h, 14);
            let b2h = _mm256_srli_epi32(b2h, 14);
            let b1hash = _mm256_or_si256(b1l, b1h);
            let b2hash = _mm256_or_si256(b2l, b2h);
            let b16 =_mm256_packus_epi32(b1hash, b2hash);
            let inc1 = _mm256_shuffle_epi8(part1shuffle, b16);
            let inc2 = _mm256_shuffle_epi8(part2shuffle, b16);
            part1 = _mm256_add_epi16(part1, inc1);
            part2 = _mm256_add_epi16(part2, inc2);
        }

These 15 AVX ops are the full solver that handles a block of 16 input lines, I pad the input with 48 space chars (10048 is divisible by 64) so that I don't have to worry about the tail end.

It is probably clear, but the algorithm starts with u/ednl's packing (AND both chars with 3, shift the second one down 14 bits and merge, that's the first 10 AVX ops.

Next I pack together the two 32-bit arrays into a single 16-bit one (b16 above), before I use that variable twice to directly lookup the 8 part1 and part2 results for these lines.

So, with a single AVX op/cycle this should take a fraction less than a clock cycle per input line, right?

I do measure 3 us on my Acer, but now we get to the interesting part:

When I instead run u/maneatingape on my input file, I get 2.3 us, for much simpler and shorter integer only code!

That time is broken down into 1.2 us to convert all 2500 lines into a 0..8 index, using code like this

pub fn parse(input: &str) -> Vec<u8> {
    input.as_bytes().chunks_exact(4).map(|c| 3 * (c[0] - b'A') + c[2] - b'X').collect()
}

(The original code generates an array of usize, when I switched to u8 the parsing stage dropped to 1.1 us and the total from 2.3 to 2.2 us)

In order to manage this, the CPU has to convert two lines per nanosecond, probably using code somewhat like this, which has a minimum latency of 4 cycles. The CPU must internally unroll the code over a bunch of iterations, enough to gain back the AVX advantage and then beat it!

movzx rax,[rsi]
movzx rbx,[rsi+2]
sub rax,'A'
sub rbx,'X'
lea rax,[rax+rax*2]
add rax,rbx
;; push into vector

We come across a grove of trees that were planted as a reforestation effort. And the Elves decide to think about building a tree house, and so we're tasked with finding a good spot.

This problem is a bit like the Skyscraper/Tower pencil and paper puzzle. Only there the goal is to fill in the grid based on how many can be seen from the outside (with an added Latin square restriction to provide enough constraints). Here we're going the other way for part 1... we've got the grid, we want how far in we can see. And for part 2, it's how far can we see in the 4 directions from a tree.

The input is a square grid of numbers, and just looking at it you can see that there is a pattern. The numbers generally increase up to a circular plateau in the middle.

And looking at my initial Perl solutions... it's really ugly brute force copy-pasta to do all four directions. For the Smalltalk I did a little better, using a state machine approach on the scan that did forwards and back in the same pass. I've done a Perl transcode of that that's slightly better to look at:

for (my $y = 0; $y < $MAX; $y++) {
    my @fore = ([$y, 0]);
    my @back = ([$y, $MAX - 1]);

    for (my $x = 1; $x < $MAX; $x++) {
        my $height = $Grid[$y][$x];

        push( @fore, [$y,$x] )  if ($height > &grid_at( $fore[-1] ));
        shift( @back )          while (@back and &grid_at( $back[0] ) <= $height);

        unshift( @back, [$y,$x] );
    }

    $vis{$_->[0], $_->[1]}++  foreach (@fore, @back);
}

And copy paste for the other axis. The basic idea is that fore does the easy scan of just adding each higher tree as we go. The back scan removes lower trees from the front that the current tree will block before inserting it. It's not great by any means, but it is at least more interesting.

So, in revisiting things. I did that transcode, and for part 2, I decided to do a little state machine there too. Basically using the idea of tracking what we can see behind us. So I keep an array of size 10 that's the count of the number of trees backwards we can see from that height. The idea being that when I look at the next tree in the row, I take it's height and look it up and multiply that in. Then I reset lower heights to 1 (as this tree will block all but itself from the next), and increase the higher heights (that this tree doesn't block). And since I didn't much have much time to do more today, I copy pasted that 4 times for each direction. Again, it's just the start of something more interesting. When looking at puzzles at the end of July to fix up, I had completely missed this one, because the run time was so fast with brute force anyways and it's so early.

The next step in fixing the communication device we've been given is finding enough space to do an update (complete with an INTERCAL Easter Egg). And to do that we get a log of browsing around the system with ls and cd... the filesystem apparently lacks better tools for doing this job, so we make do.

The input is a log, and it's a nicely ordered walk. It starts with a cd / to establish that it begins at the root, no other cd has a / in it... so there's no down-two, up-two, up-and-over stuff to worry about. And the ls is only done once in each directory. So support for that stuff and sanity checks are optional.

I did this with a recursive decent parser in Perl to start... it really fits because we're doing a tree walk, with a very standard collection of the results going back up... recurse down and return the size back up, collecting the sum of them for the current directory. Here we also want to keep those intermediate values, so we can just add them to a hash table on the current working directory string. Then at the end we can just extract what we need with:

say "Part 1: ", sum grep { $_ <= 100_000 } values %dirs;

my $needed = NEED - (DISK_SIZE - $dirs{'/'});
say "Part 2: ", min grep { $_ >= $needed } values %dirs;

I also did another version which was iterative, because the recursion only has the parameter of the current working directory. Which is basically a stack... you append (push) directories on the end when you cd down, and remove (pop) the last directory when you cd ...

And for Smalltalk I did a nice class to represent the system and make queries. That's in line with the fact that this is a "work" problem. It's a real task... I wouldn't do this specific job this way, but there have been times were I've written scripts to follow logs like this and extract information.

I suppose the cutest thing in my solutions is with the Perl, where I did this:

$/ = '$ ';          # break input on cmd prompts

# read input, throwing out the cmd prompts
my @Input = map { [grep { $_ ne '$ ' } split /\n/] } <>;

... to read in the input. Basically chopping it up with the command prompts as the delimiter. So that I get an array of arrays where the first element is the command, and the rest is the response. It does require a bit of mess to chop out the $ delimiters, but it does the job and it means that the code that does the work doesn't need that mess. Up here is the perfect place for such ugliness.

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Second:

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

[[],[3]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

And so the core of the spreading is:

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

    $i = $i % 10 + 1;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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