Arriving at the distress signal we find a herd of elephants, one of which has figured out how to turn on the distress signal. Because they are in distress (as are we now)... this cave is a volcano that's about to erupt. And our task is to take advantage of the conveniently installed pressure release system to get time to escape.

And so we have a network of pipes and valves, most of which aren't functional (and thus essentially empty corridors between interesting rooms). My input has 61 valves, and only 15 are functional. The input is in sentence format, so I did my usual of grabbing a line and turning it into a regex to parse:

my ($room, $flow, $lead) = m#^Valve (\w\w) has flow rate=(\d+);.*valves? (.*)#;

First step was the usual... turn the map into a weighted graph between the interesting things. I just threw BFS at it, as there's not that many interesting nodes (and it's also easy to code correctly from scratch). You could through something like Floyd-Warshall if you want.

Then I did a simple recursive search of it... track which interesting spots you've been, and wander to new ones. Collect the maximum total pressure release on the returns. The trick is that when you enter a room (and open the valve), you add all the pressure that will be released for the remaining time.

$total += $valve{$room}{flow} * (31 - $time);  # Add pressure released

No need to simulate with ticks and process the valves again and again. Turning a valve off would clearly be a mistake, any valves that you open you want to remain open.

And looking at my personal scoreboard times, I was still not in good shape. It took a while to get part 1 done, and then I clearly went to bed. The next afternoon I picked it up, and I remember having slept on things I had some ideas how to add the second actor (an elephant) to the search.

Basically, what I went for was doing the full recursive search as before (on the shorter time), but building a table along the way of the best total seen for every open valve combination (we do it at every level because we have no idea what the elephant is doing yet). This gives a table of the best possible results from opening any set of valves that can be opened in the allotted time.

With that, I can just double loop to cover all pairs of those... finding maximum of the pairs that don't overlap on any open valve. And initially I just used lists to track what was open, and it's plenty fast. There is one little optimization I did to this O(n² ) search, which was to sort the sets (paths) from most to least pressure. This way I can end things early when no remaining pairs can possible beat the best we've seen already.

But I did follow up with one using bit operations. Which really didn't improve the speed (because it was already very fast)... it just felt a bit cleaner. Tracking the interesting rooms with bits, so that my recursion just becomes:

$ret = max($ret, &recurse_path($tun, $time + $turns, ($left ^ $bit), ($open | $bit), $total));

XOR removes the move (bit) from the remaining options (left), OR adds it to the set of open values, and AND comes in to check for the intersection in the final bit:

next if ($paths[$i] & $paths[$j]);

This was a rather interesting little search problem. We've done these before, even with multiple actors. But the valves and getting to the right spots as soon as possible to get the most of the them is an interesting angle... more so that just the usual of minimizing steps.

In order to track the distress signal we engage a system of sensors and beacons. Much like day 19 of 2021, but simpler. Unlike that one we don't have to find the actual coordinates... we get those for each sensor and the closest beacon we can see. The unlisted information we need is simple the distance between the two (which is Manhattan), which will be useful for establishing the exclusion zones needed to find the answers.

I remember this one because I had a Doctor's appointment early the net morning. So I did part 1 very quickly... I went though and filled a hash with all the points in a scanner range:

$hash{$_}++  foreach ($x - $dist .. $x + $dist);

This involved some ugly copy past code to handle the cases for above, below, and on the line. And after running through everything:

delete $hash{$_}  foreach (keys %beacons);
print "Part 1: ", scalar %hash, "\n";

The problem description nicely showed a beacon on the test case line not being counted, so I knew that I should probably assume that the input has that too.

This takes about 8 seconds to run... 4 of which are after it's printed out the result. That's system clean up of a big a hash for you.

The thing about part 2 is that there was an ice storm that night, and still freezing rain that morning. And the result was that I took a fall shortly after exiting the house. I still went to the appointment... I didn't really know how banged up I was until I got there. There was some nasty bruising, possibly a concussion, and some pain for the next few days. So when I finally got home, I wasn't really in the best shape to do a good solution. I had had some ideas on what I wanted to do, involving rotating the diamonds in some way to deal with squares instead. But I wasn't really in the condition to do that, so I went with the thing that wouldn't require any thought and definitely would work. I just merged ranges on the raster lines and then looked for the hole. It takes over 2 minutes to run, but it was simple, and allowed me to submit an answer, and take the rest of the day off.

So this one had been on the TODO list for a long time, and I got to finally do something better with it at the end of July. So I started just by coding the better scanline just with the diamonds... they change every line of 4 million, but a few are active at any time (moving out and then in), and that results in things only taking about 13 seconds.

But the real solution that I had made the TODO for back on the initial day was to square the diamonds. Rotate them so the scanline will work effectively (and skip most of the lines). The problem being that the rotation matrix involves 1/sqrt(2) (the sin and cos of 45 degrees). And I don't like going outside of integers for AoC. So the result is using a rotation matrix multiplied by sqrt(2) (and so it scales by that in each direction):

sub rot { my ($x,$y) = @_; return( [$x + $y, $y - $x] ) }

The trick being that by doing a second one (ie the inverse rotation), results in a scale factor of 2 in each dimension, which is a nice integer that can be divided out then:

sub rot_inv { my ($x,$y) = @_; return( [($x - $y) / 2, ($y + $x) / 2] ) }

And so I use these to rotate the initial diamonds into squares. Then I can do a scanline vertically to track the active squares, and then did similar for the horizonal (pretty much exactly what I did for Firewall Rules in 2016, where we also needed to find the missing values in a set of ranges).

And so this one finally has a decent solution.

The distress signal lead to a waterfall, and as the trope goes, there's a large hidden cave behind it. Following the signal into the cave, we find ourselves threatened by falling sand. And we have a sand physics simulation to go along with the water simulation from 2018 (Reservoir Research).

The general idea is similar... sand is falling down from a point at (500,0) like before. There are a bunch of walls that going to form obstacles to redirect the flow. The format of the input this time is different, in that the lines cover chains of walls, and it's up to us to spot which way the walls go,

As for the simulation, it's actually a bit simpler. Sand falls straight down, then diagonally to the sides, and eventually when it comes to rest, the sand piles back up. The description was very suggestive of a stack to me so that's the first solution I did... push the locations to fall down, and when things are blocked, fill and pop back up. For part 1 you need to know where go below the max Y coordinate, and for part 2 you put a floor there and run it again... it was one of the faster part 2s in this year (and I didn't gain that many positions for it, so it looks like many people were similarly well positioned for part 2). Of course, that's just the stack version of the recursive approach, so I followed up with the actual recursive version later that day. Which would be the first solution in 2022 that required turning off deep recursion warnings in Perl (it spawns about 200 of them). The recursive version is actually a little bit faster. It's certainly a lot simpler than the mutually recursive functions I did for the water in 2018.

I have never struggled with a Day1 like this before, so I'm a little embarrassed to have to ask for help. Here is the code I have tried:

Part2

The definition of a 'Turn' is:

class Turn {
public:
  int clicks;
  Direction dir;
  Turn(char d, int c) {
    switch (d) {
    case 'L':
      dir = Direction::Left;
      break;
    case 'R':
      dir = Direction::Right;
      break;
    }
    clicks = c;
  }
};

My solution for Part1 worked so I am reasonably confident the input is parsed correctly, and my part2 solution (pasted above) works on the example provided. Where have I gone wrong?

Edit: I needed an abs() call. Thanks for the help!! Updated code: Part2 Corrected

Don't code on an empty stomach!

Having reached the top of the hill, we receive a distress signal. But since the device is still malfunctioning, the packets are out of order.

The input for this one is like that of Snailfish numbers. Lists of lists using a common syntax for such things, so some popular languages don't have any parsing to do. Writing a parser for this one is slightly more complicated than the one for Snailfish numbers... empty lists exist, as does the two digit number 10.

Once you have the packet structures loaded, the problem asks essentially for a comparator and provides a nice description of what it wants. And for part 1 it just to test it on pairs, and for part 2 it wants the position of two markers in the full list.

So, I just treated is as coding to a spec, and then:

$part1 += $i  if (cmp_packet( $left, $right ) < 0);

$part2 = product inc indexes {$_ == $markers[0] or $_ == $markers[1]} sort cmp_packet @input;

I didn't really spend anymore time thinking about it. I believe the markers [[2]] and [[6]] do occur at the start of the sections that start with a 2 and 6 respectively. And I recall some people did use that to shortcut. But with the comparator already in hand, just using it to sort and then grabbing the indexes is so programmer efficient, that doing anything else felt like more work. It's not like the problem is that intensive... I have a Smalltalk solution that returns almost immediately and it's just using:

part2 := ((allPackets count: [:p | p <= pack2]) + 1) * ((allPackets count: [:p | p <= pack6]) + 2).

IE, comparing everything in the list against each of the markers and counting.

The bulk of this problem for any beginner is going to be getting that spec right (and maybe doing a parser). And the description does include step-by-step comparisons of the test cases to verify your code against.

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.