Today we're searching Santa's Reindeer-class starship. Unfortunately, a couple of The Historians have teleported into other parts of the ship behind doors that are locked by keypads. And having experienced Santa's ship before, it's not surprising to find that there are a lot of hazardous areas. And so we need to use a robot to deal with a numerical keypad in a depressurized area, and then another robot to access the panel to control that one in a radioactive area, and a second robot to access the control panel for that one in an area that's -40 degrees (which isn't so bad). All while we direct this chain from one safe area that's packed with Historians. And we can't just tell them what button to hit, we need to tell them how to move on the keypad grids and then to hit A to signal that the robot should hit the button. For part 2 we go after the second missing Historian with a chain of 25 intermediate robots.

The input for this one is very short. Five lines... each a three digit code to type, followed by A. Because, in addition to the above, we don't know which code we need because the The Historians have forgotten.

This was the slowest part 1 submission in 2024 for me. But a large part of that was that I spend a lot of time playing with the code to map out paths on the keypads... worrying about everything (building tables and carefully checking them). After which I started getting weird uninitialized warnings... it turns out that will happen when the keypad has two 6s and no 8.

I know my first solution for this was initially a mess, and was using paths between buttons that avoided hitting the same one twice on the way. As part of the cleanup I changed that to just the paths that head directly there (ie just getting all the step like patterns... these all naturally have the same length (Manhattan distance), which simplifies things a bit):

my @steps = (($delta->[0] < 0) ? '^' : 'v', ($delta->[1] < 0) ? '<' : '>');

And then a quick BFS using those moves.

The idea being to turn:

# Define the pads (with sentinel Xs)
my @keypad = map {[split //]} ('789X', '456X', '123X', 'X0AX', 'XXXX');
my @dirpad = map {[split //]} ('X^AX', '<v>X', 'XXXX');

Into a table of routes:

my %key_route = &route_pad( \%key_loc, \@keypad );
my %dir_route = &route_pad( \%dir_loc, \@dirpad );

Using BFS between all the starts and ends.

And for handling the chain, I went with recursion. The main trickiness here being that one of levels is not like the others (one has a number keypad, not a direction one). But that's easily done with selecting a table with:

my $routes = ($depth == 0) ? \%key_route : \%dir_route;

The other trickiness being the base case... where the last in the chain just adds the length of sequence (because we get to just type directly... which I suppose means there are two levels not like the others).

The final version ended up as this (and overly fancy I'll admit):

sub recurse_keypad {
    my ($seq, $depth) = @_;
    state %memo;

    my $routes = ($depth == 0) ? \%key_route : \%dir_route;
    my @seq = ('A', split( //, $seq ));

    $memo{$seq,$depth} //= ($depth == $Max_Depth)
                            ? sum chain { length( $routes->{$_[0],$_[1]}->[0] ) } @seq
                            : sum chain {
                                  reduce {
                                      min($a, &recurse_keypad($b, $depth+1))
                                  } (~0, $routes->{$_[0],$_[1]}->@*)
                              } @seq;
}

Making use of my chain iterator that works on adjacent pairs of a list.

And in the end, although part 1 took over two hours, part 2 took about 20 minutes to fix up... a bit of cleaning, upping the depth, and throwing a memo on the function for speed. The end result is that I got part 2 in just fast enough to be top-1000 (the only time that happened in 2024 or 2023).

Today we're back in the computer near the CPU. While the Historians search, we get challenged to a race by a program as part of the race condition festival, with the prize being a mutex.

The input is a 141x141 randomly generated maze. What makes this one different is that all the dead ends have been filled in, except two. Those two ends are the start and end of the race route. In my input, they're slightly more than 20 apart (by Manhattan), and there's a big filled in section between them (much like the test case given in the description).

Since there is just one path, the rules of the race include the ability to cheat once, by ignoring collision detection for a number of picoseconds (2 for part 1, 20 for part 2). Our task though isn't to actually find the best cheat available. That's actually very easily done by looking at the input. The start and end are so close, and the path from the start in mine immediately heads to a spot very near the end with a single wall to jump to it. Instead we want to innumerate the number of cheats that save at least 100 picoseconds.

My initial quick solution for part 1 was to use BFS to find the path (I hadn't looked so closely to notice the lack of dead ends yet) going backwards from end to the start (although that's not really important, that was the choice I went with). Along the way I create a hash map of the points on the path to the number of picoseconds to the end. With that I just try jumping 2 squares in each direction from each point on the path and seeing if it's a valid cheat (is it in the hash and sufficiently closer to the end).

Once I saw what part 2 was, I could move on to designing something for it. First thing was moving to the path finding getting me a list of the points from start to end (ultimately taking advantage of the lack of dead ends to gain some speed). Here, the time we're at a point is encoded in the index of the list. And with this, the grid can be tossed, as this comment says:

# Done with grid, now using just the path:

And with that, I went with brute forcing things. Two loops, one for the start of the cheat and the other for the end (which needs to be far enough away to consider checking:

foreach (my $i = 0; $i <= $#path - ($targ + 2); $i++) {
    foreach (my $j = $i + ($targ + 2); $j <= $#path; $j++) {
        my $dist = abs($path[$i][0] - $path[$j][0]) + abs($path[$i][1] - $path[$j][1]);

        # Check allowed distance, and that we didn't lose too much time.
        if (($dist <= 20) and ($j - $i - $dist >= $targ)) {
            $part2++;
            $part1++  if ($dist == 2);
        }
    }
}

And part 1 falls out as a special case.

It's not very fast, but it is simple. And as I've said, 2024 I was quite sick in November and went into this year with a mindset of being willing to just take easy solutions so I could get to bed earlier.

Will this year also have 12 days of puzzles or back to 25? Personally I really liked that there was "only" 12 days since as Christmas approached and I got busy with family related things I found it difficult to make time for AoC, and I prefer completing a day on the actual day. I hope 2026 will have 12 days of puzzles :)

Today we're back on Gear Island and we get a chance to check out the hot springs (onsen) this time. Where we find a problem quite like the one we had with the hot springs (helices). Which is that we're going to be doing some pattern matching to create designs out of the stripe on the towels.

The input consists of two sections. The first is a one line list of of the towel stripe patterns we have to work with (comma delimited, with spaces to ignore). My input has 477 of those, and they're strings of the letters wubrg (the Magic the Gathering letter codes for colours: white, blue, black, red, green). The second section is 400 lines of patterns to try and create with those.

Part 1 just wants to know if a pattern is possible. A perfect job for a dynamically created regex for a very quick answer:

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

my $patt = '^(' . join( '|', split(/, /, $section[0][0]) ) . ')*$';
say "Part 1: ", scalar grep { m#$patt# } $section[1]->@*;

This was my second fastest part 1 of this year, only beaten by day 3 (Mull It Over) which also fell very quickly to regex ripping into the input.

Part 2 wants to know the number of ways we can make those designs. Having filtered out a few dozen 0s for part 1 is a start. And since this was so much like the previous hot springs, I did a recursive/memoization for my first solution. Which was a good simpler than the 2023 day 12 problem... I don't often expect a part 2 for a day 19 to be as simple and quick as this one turned out to be. The 2023 hot springs was a big recursive function with lots of special cases to carefully handle that I spent a lot of time carefully working on. This one was just this at the core:

my $ret = 0;
foreach my $patt (@patt) {
    my $new_str = $str;
    $ret += &recurse_count( $new_str ) if ($new_str =~ s#^$patt##);
}

Slap a memo on it, run it and wait, because this is going to take a bit (but still just seconds).

In order to play with it a bit more, I decided to reverse the dynamic programming approach... instead of top-down memoization, do it as a bottom-up tabulation. And when I did that... it's so much faster. That looks like:

my @table = (1, (0) x length($str));        # Start with 1 match of empty
my @poss  = grep {$str =~ m#$_#} @patt;     # Only use patterns in str (saves a bit)

for (my $i = 1; $i <= length($str); $i++) {
    foreach my $patt (@poss) {
        # If we've just seen a pattern, add table value from start of match to current
        my $plen = length($patt);
        if ($i >= $plen and ($patt eq substr( $str, $i - $plen, $plen ))) {
            $table[$i] += $table[$i - $plen];
        }
    }
}

return ($table[ length($str) ]);

Note the prepass of the patterns to get just the ones that regex can see in the target (they might not be used, but the ones that don't appear certainly can't).

And you can see why this can be so fast right away, we're just iterating over the length of the string in one pass. And so what we're doing is actually not like Hot Springs 2023, but more like Adaptor Array from 2020 or Dirac Dice from 2021... it's basically a recurrence relation where you sum all the points which correspond to the starts of the patterns that have just matched (bring there counts forward, and combining the branches). Which is how tabulation normally goes, and here it turns out to be great. I might have gone this way first, if it wasn't for the connection to the old Hot Springs that lead me (slightly) astray.

So this was a nice little dynamic programming exercise. It originally ran on a Thursday going into the final weekend, so it serves to be a bit of lighter problem so people can catch up and get ready for the big final weekend.

Today we find ourselves digitized and inside a computer again. The User isn't dropping games on us, just going straight for corrupting data because they misunderstood what a PDA was (and not in a good way, like Public Display of Affection or Personal Digital Assistant).

The input is a list of memory cell coordinates (3450 in my input) to a square 2D grid with coordinates from 0 to 70. These represent the locations that get corrupted (one per nanosecond), and our task is to get The Historians from the upper left to the lower right safely.

Part 1 is just a simple path finding... after the first 1024 have fallen, find the shortest path. If you print out the grid, you'll see that at this point, it's basically drawn a bit of maze from the corners with a gap in the middle to cross. Narrow mazes like this are quickly transversed with basic BFS, so no need to be fancy. Note that the latter part of the input ultimately fills in a lot more than just a maze.

In part 2 we want to find the first dropped block that permanently cuts us off from getting to the end point. For my initial solution, I did just took part 1 and continued with it. Given the path we found, I just kept dropping blocks until one landed on that path:

next if (!exists $path{$pos});      # fell off the path, still unblocked

When that happens, I recalculate the path. If I can't, that's the solution. Very simple and is going to work... and it's not absolute brute force (trying to find a path after every drop).

To improve things for Smalltalk, I loaded the input into a class called TimeGrid. The internal TimeGrid structure is one where the cells contain the time they become impassible. And so I can set a time and searches will treat cells with values less than that as walls.

" Get status of point at current time "
at: pt [
    ^((grid at: ((pt y + 1) * dim x) + pt x + 2) <= time) ifTrue: [$#] ifFalse: [$.]
]

Note that I'm also doing the grid internally as a flat array (faster and cleaner for Smalltalk).

Because I was taking things easier in 2024, I just used this random access of the grid by time, to do a binary search over the space:

" Binary search for first blocking drop: "
range := (timeStart + 1 to: input size).
[range size > 1] whileTrue: [
    range displayNl.
    mid := range at: range size // 2.

    path  := (grid time: mid) getRoute.
    range := (path isNil) ifTrue:  [range first to: mid]
                          ifFalse: [mid+1 to: range last].
].

This was good enough to be faster than the Perl. But I did make a note about what I ultimately wanted to do with this, and later got around to doing that. And that is a dynamic programming/single-pass BFS deal. Where the state tracks the minimum time a block hits the path that state represents. We can take that and use it to track the maximum of those values for a cell in the visited array (thus getting the latest time that cell is available). And so we get a tabulation where we ultimately get our answer in the visited cell of the end point. Here's the key section of the BFS loop in the Perl version:

# reduce path's time to Grid's if it is lower:
my $min_time = min( $time, $Grid[$pos->[0]][$pos->[1]] // ~0 );

next if (defined $visit[$pos->[0]][$pos->[1]] and $min_time <= $visit[$pos->[0]][$pos->[1]]);
$visit[$pos->[0]][$pos->[1]] = $min_time;

foreach my $neigh (map {[$pos->[0] + $_->[0], $pos->[1] + $_->[1]]} @Dirs) {
    push( @queue, [$neigh, $min_time] );
}

I also have a slightly more complicated version of this, where I track number of steps taken in the state and use that to prune when it's >= the value in the current tile (ie it'd be a wall by then). It also has a prune for hitting the end point (after writing to the visit array... we want the answer). However, with measuring with the command line time these don't actually show any improvement (in fact, often it's slightly slower).

But things don't end there, because I made an additional note about a solution type I had seen posted. One that's based loosely on the famous proof that the game of Hex) must have a winner. In this type of solution we add borders of one colour to the top and right, and a second colour to the bottom and left. As we drop cells, they take on the colour of the cells they're connected to (so there's an invariant that cells connected to an edge have that edge's colour). But if the dropped cell is adjacent to cells of both colours, then we've just completed a path between the coloured edges. And if that exists, then no path from start to end remains. I had some fun working out the details of that today (I used bits for the colours) and coding it, and it really does come out nice and tight once you get it right, and it's blazingly fast compared to the other methods.

And so we have another great problem where there's a lot of approaches.

EDIT: The title is a typo, this is 2024 Day 17.

Today we find ourselves suddenly falling through time, and need to fix the device. Which has that trope of unfolding into an entire computer. I like this old school touch (I like this trope, like in Brain Donors with the laptop that unfolds into a desk with CRT and printer). Nowadays, the small device would just produce a large holographic display up in the air to poke at and I'd be suffering from sympathetic Gorilla Arm Syndrome.

The input for this one is a list of initial values for the three registers, followed by the code (which is comma delimited integers, like the Intcode problems of 2019). We're given that this is a 3-bit machine, but the registers can be bigger (but with my input, only the bottom three bits of B and C ever matter, and so only A makes use of that).

For part 1, we just need to run the program and collect the output. This is one of the rare problems with a string answer, in this case, it's got commas between the output values. So I did my usual, hash of anonymous subs dispatch table approach:

sub c_op ($)  {my $op = shift; return (($op & 04) ? $reg[$op & ~04] : $op)}

my %opcodes =
    (
        0 => sub {my $op = c_op shift; $reg[A] = $reg[A] >> $op},           # adv
        6 => sub {my $op = c_op shift; $reg[B] = $reg[A] >> $op},           # bdv
        7 => sub {my $op = c_op shift; $reg[C] = $reg[A] >> $op},           # cdv

        1 => sub {my $op = shift;      $reg[B] ^= $op},                     # bxl
        4 => sub {my $op = shift;      $reg[B] ^= $reg[C]},                 # bxc

        2 => sub {my $op = c_op shift; $reg[B] = $op & 7},                  # bst
        5 => sub {my $op = c_op shift; push(@out, $op & 7)},                # out

        3 => sub {my $op = shift;      $ip = ($reg[A]) ? $op - 2 : $ip},    # jnz
    );

Could have been an array, but this way I get to reorder the instructions to pair them. With that, running the machine just becomes:

while ($ip < $#code) {
    &{$opcodes{$code[$ip]}}( $code[$ip+1] );
    $ip += 2;
}

Part 2 reveals why the output is that way... we're asked to find the value for register A that makes it a quine) (technically it's not because supplying the value for A is an input, but the job is the same).

The trick with doing non-trivial quines is outputting the command to print. After all, the print can print the rest. For example, if I want to do a 1-line quine in dc, I can output a number (without a newline) with n, and output that number as a character string (ASCII coded on bytes) with P. A duplicate d is needed because n removes the value from the stack. And so the number that's needed is 0x646E50 (the packed ASCII encoding of dnP), which is 6581840 decimal:

dc -e'6581840dnP'

You can also similarly do a two-line quine, using p (which outputs the top value with a newline, but leaves it on the stack).

And so we should expect something similar from the code in this problem. Given that, all the inputs are probably something like this:

bst A       # B = bottom 3-bits of A
...
adv 3       # A >>= 3
...
out B       # output bottom 3-bits of B (could also be out C)
jnz 0       # loop until A is gone

A loop that decodes the values 3-bits at a time in A (from the little end). Given that, it's probably safe to believe that everyone's code is 16 long... which is 48-bits to encode in A (17 would be a bus error, and 18 would be problematic for floating point native languages).

And so with that in mind, I made the code to run the machine into a function that takes a value to initialize A with and breaks to return the first output value, which allows for calculating things 3-bits (one digit) at a time:

my %poss = (0 => 1);
foreach my $digit (reverse @code) {
    my %new_poss;

    # shift left possibilities one octal digit and try all 8 lower options
    foreach my $val (map {($_<<3) .. ($_<<3) + 7} keys %poss) {
        $new_poss{$val}++  if ($digit == &try_code( $val ));
    }
    %poss = %new_poss;
}

Here I brute force over all 8 possibilities for the next 3-bits, for each of the numbers that worked last time. In the end, there at 42 values in that hash that work, and I just take the minimum one for the answer.

I did do dc solutions for this one... they are absolute monsters (part 2 is about 350 characters). For tracking the possible values, I do it on the stack (the new values go into a register stack, and then I dump that out onto the main stack for the next loop) and there's no duplication of them (everything is 3-bit aligned and won't overlap), so technically, that hash could have just been a list in the Perl too.

This was a fun one, even though the reverse engineering wasn't much, the quine aspect was a nice touch.

Next place to look for the Chief is at the Reindeer Olympics, which are on again this year. So while the Historians do the work, we take the opportunity to watch the Reindeer Maze event. The goal of this race isn't just to get to the end quickly, but to do it with few turns, as those cost 1000 per 90 degrees.

The input is 141x141 bounded maze (and so it comes with a sentinel ring already). The start is in the lower right, and the end is in the upper left (on both input and test, so you can just calculate those positions if you'd rather not parse for them). As usual, it appears to be a classic random recursion generated maze, where you start with a grid and a starting cell:

#########  
#.#.#.#.#    
#########  
#.#.#.#.#
#########
#S#.#.#.#
#########

And randomly choose an unvisited neighbour cell. Knock out the wall and recurse into it. If there's no unvisited cells, just return (ie back up until you find a place you can branch). There are a number of things you can do with this, like not using uniform chance for your options (eg track direction and give more or less weight to forward and you can control twistiness of the passages). By poking out some additional walls (which is what we have here), the maze gains loops (needed for part 2) and becomes such that there can be islands that are unreachable with a left-/right-hand rule.

I bring this up, because this is one of the few of these that I actually used the fact that this also means that you can treat all moves as effectively 2-steps (first step checks for a wall, second is the full move into the next cell), and so you can use that to skip around the maze a bit faster. Normally I'm happy to be more flexible about the map and not assume that alignment. But I didn't do much else other than basic Dijkstra from S to E, so I felt like I should do a bit more.

By the BFS nature of Dijkstra, the first time you arrive as E you get part 1, and then you just need to run the priority queue while it stays at that value (to find the others that reached the end at the same time). For my input, that's 571 more items, of which 192 are shortest paths (so lots of 2s in the factorization, which would probably be from branching/merging pairs around islands). By tracking the path as I go and collecting them into a hash/set when I get to E, I get a list of all unique visited locations for part 2. It's a very simple approach, but given the nature of the problem, there's probably better that can be done to avoid tracing every combination of the branching/merging options (looking at the end hash, I see that much of the part 2 answer is traced all 192 times, and the lowest I see is a short bit that's done 48 times). Maybe a DFS search with memoization.

The other little optimization I did was from Clumsy Crucible, which was to make turn-and-move a move (but this time we also need to add going straight if available, because we're not in the position of being forced to turn). This makes sense, because there's no point in turning if there isn't a path off that side (in which case we might as well move into it). There's no need to ever make a U-turn, because the only time you'd ever want to do that is the starting position (when you wouldn't be turning around to backtrack). And given the position of S in the lower left, that's not something you'd ever want from an East facing start.

So, this isn't really too intense a search, you can get away with a weak implementation and still get the answer in a reasonable amount of time.

Today we're back in the ocean, and while The Historians search in their mini submarines, we set about to helping the lanternfish with a rampaging robot that's messing up the lanternfish logistics and lanternfish inventory management of their food supplies.

The input for this one comes in two sections. The first is a 50x50 grid map of the warehouse (with a surrounding wall, so no need to add sentinels today). The second part is a list of movements the robot will attempt to make... there are 20 lines of 1000 characters of these (for 20k total moves). The map has boxes that the robot will multipush (so not your regular Sokoban) if it moves into them.

For part 1, I simulated the robot, and when it runs into a box, I scan ahead to the first non-box... if it's a wall, the move is ignored, else the multipush is completed:

my $end = $move;
$end += $Dirs{$d}  while (grid_at($end) eq 'O');    # multipush

next MOVE if (grid_at($end) eq '#');                # bump

# Put box at empty end, clear front of push, move robot to it.
$Grid[  $end->[0] ][  $end->[1] ] = 'O';
$Grid[ $move->[0] ][ $move->[1] ] = '.';
$robot = $move;

For part 2, we find out there's a second malfunctioning robot in a warehouse with the same floor plan, only twice as wide (including the boxes, but not the robot). The fact that the robot is still the smaller size is what makes this problem interesting. Horizontal pushes can be tested and completed as before, but vertical pushes can end up pushing an expanding cone/tree of boxes (once a horizontal push has offset their alignment). The description nicely gives a small example with three boxes that shows that, but in the input it can chain much further and wilder. The key is that the same invariant still applies... the boxes get pushed only if all the spaces at the leaves of the tree are empty. If a single one has a wall, the push fails.

And so I used a recursive binary tree walk to test. The call is:

my $test = &test_vert_push( $move - $vx * (grid_at($move) eq ']'), $Dirs{$d}, \@boxes );

Note that the first parameter here is the location of the box, and that we regularize it to always be the left side so we don't have to worry about special casing. I also notice that I decided to return the boxes in the structure by-reference (\@boxes), leaving the result value as a simple boolean (0 or 1) scalar.

    # Get both squares ahead of box push
    my @ahead = map {grid_at($pos + $_)} ($dir, $dir + $vx);
    if (all {$_ eq '.'} @ahead) {
        return (1);
    } elsif (any {$_ eq '#'} @ahead) {
        return (0);
    }

    # Got more multipushing to do
    my $ret = 1;
    if (join('', @ahead) eq '[]') {
        $ret *= &test_vert_push( $pos + $dir, $dir, $boxes );   # one box straight ahead
    } else {
        # A box to the left or right ahead, maybe both:
        $ret *= &test_vert_push( $pos + $dir - $vx, $dir, $boxes ) if ($ahead[0] eq ']');
        $ret *= &test_vert_push( $pos + $dir + $vx, $dir, $boxes ) if ($ahead[1] eq '[');
    }

My Smalltalk solution is just an OOP version of the Perl, and that structure is instead returned as an object of type VerticalPushResults which holds both parts.

Once I get a valid push and it's list of boxes, I chose to keep it simple. One loop that replaces all the boxes with .., then a second loop that puts [] in the new locations. Because this is the sort of thing that you can end up spending a lot of time debugging if you try to be fancy. Even with 20k moves this is still fast, so it fine to just write this to be more expressive.

Hi there, im new to coding in general. The language I am learning is Javascript, would appreciate being signposted to AOCs that would help me build and grow as a coders.

Today we're back at Easter Bunny HQ to use the bathroom. Last time we were here we were dealing with entering codes on a keypad, but now they've upgraded to swarms of patrolling robots that we need to avoid.

The input is a list a 500 robots, with a 2D starting position and a velocity vector. The robots will not collide and teleport to wrap around on the sides. The room is 101x103 (a pair of twin primes). For part 1, we're calculating a hash of the positions after "simulating" 100 seconds (naturally, there's no need to run all the seconds, you can get the position directly with (pos + 100*velocity) % roomsize), which involves dividing the grid into quadrants (tossing out the axis), and multiplying the number of robots in each of the four.

The real fun for this one is part 2. Suspecting that these might actually be North Pole robots, we're given the task of finding the hard-coded Easter Egg: most of the robots at one point will arrange themselves to form the image of a Christmas tree. No example is given of what that looks like or exactly means, only that it happens. And so it's left to us to work out a heuristic or approach to find that. Which, I remember for some people, was just calculating images for every second and dumping them in a folder and looking through the icons.

I also remember that another heuristic some people used (and got away with) was the assumption that the tree would occur at the time when no robots overlapped. That's sort of "reading the mind of the creator" puzzle solving... it essentially assumes that the initial state was created by backtracking from the target (a safe assumption), but also that that was produced that without an overlap (one could have been set or the input generator may have generated one randomly (it appears to avoid this)). So that last bit isn't so safe, but it practice it works here.

My initial approach though was using the heuristic that an image of a Christmas tree will require a lot of the robots to be orthogonality adjacent. So I just simulated second by second and output the grid each time the number of adjacent robots improved until I saw the tree. Which was also the first time that more than half the robots were involved (thus "most of the robots" as described) so after submitting the answer, I just changed the check to use that. This is a bit slow, but pretty much guaranteed.

For Smalltalk (which is considerably slower), I took advantage of having seen the tree to do a bit better, and having seen how small the image is went with variance (I remember people experimenting with all sorts of heuristics, including using the hash from part 1... and the signal of the tree tends to be very strong, and so works well with many, many things). And after doing a solution with that, I then realized that it doesn't need to be precise, and so I loosened things a bit by going with the approximation of using a running mean (calculating and using the mean as we go... after 500 points, this ends within 2% of the actual variance). And it was simple and faster:

approxVariance [
    | sum var |
    sum := 0.
    var := 0.

    self keysAndValuesDo: [:i :val |
        sum := sum + val.
        var := var + (val - (sum // i)) squared.
    ].

    ^var // self size
]

The bigger trick was taking advantage of the prime side lengths, which guarantee that all the robots are moving in cycles of 101 on their x-coordinate and 103 on their y. And so by just running things for 103 seconds (tracking the times of minimum variance for x and y independent of each other), we have all the information needed (for both parts):

invMod := (dims x) raisedToInteger: (dims y - 2) modulus: (dims y).
('Part 2: %1' % {minX + ((invMod * (minY - minX) \\ dims y) * dims x)}) displayNl.

For the Perl version of the same approach, I decided to use libraries and actually call a Chinese Remainder implementation for once (I figure I did this mostly to have one coded for reference somewhere):

say "Part 2: ", cr_combine( mod($minX, $DIM[X]), mod($minY, $DIM[Y]) )->residue;

Of course, the exploration into a variance approximation was in preparation for a dc solution. And I did do that, but then considered, after seeing how strong the signal was, just using a constant mean of 50. Which produces an error of 49% on one of the critical iterations, but the signal is so strong you'd need more than 100% error to lose it (and the rest all come within 2%):

tr -- '-p=v,' '_ ' <input | dc -f- -e'[1[rld+lm%d51-d*3Rdd4Rrlvx+rlVx1+dlm!<I]dsIx+s.]sR[s.d]sN[d[d3Rdlvx3Rlvx<Nr1-d0<L]dsLx+]sF[A3dsm+sd[;v]sv[:v]sVrlRxA1dsm+sd[;w]sv[:w]sVlRxz0<M]dsMxA1lFx[;v]svA3lFxd3Rr-A1+51*A1%A3*+p'

Part 1 was also pretty fun to do in dc:

tr -- '-p=v,' '_ ' <input | dc -f- -e'[lydd*v/lxdd*v/2*3r-+d;q1+r:q]sQ[A3+A0*3R+A3%51-rA1+A0*3R+A1%50-dsxrdsy*0!=Qz0<M]dsMx6;q4;q*2;q*0;q*p'

The trick in here to quarter things is that I calculate the positions on the residues of [-50,50] and [-51,51]. So if x*y == 0 that's on an axis and should be ignored. Then I get the signs of the values (dd*v/, safe because we know it's non-zero), and use this simple hash to track them:

2*3r- +                     # index = 3 - sign(x) * 2 + sign(y) => {0, 2, 4, 6}
d;q 1+ r:q                  # q[index]++

This is one of the most memorable problems in this year. There is so much freedom given on what you can do for part 2.

When I use the example data, it returns 14 (correct answer). However, when I try the real puzzle input my answer is wrong and I think smaller than what it should be. To preface my bad variable naming, "a" is current range and "b" is either the previous or next range.

from pathlib import Path
path = Path(__file__).parent / "input_5_ranges.txt"
with open(path, 'r') as file:
    text = file.read()
ingredient_ids = text.splitlines()



# Take an item ["13-16"] and conver it to ["13", "16"]
def create_range(items):
    ranges = []
    for item in items:
        ranges.append(item.split("-"))
    
    return ranges


# Order ranges by starting point
ranges = create_range(ingredient_ids)
ranges.sort(key=lambda x: int(x[0]))


# Loop through ranges
i = 0
while i < len(ranges):
    # Define item; range
    item = ranges[i]
    int_item = list(map(int, item))
    # If loop is on atleast the second iteration, check if the starting point of the range falls within the bounds of the first range
    if i > 0:
        # print(int_item)
        # print(int(ranges[i-1][0]), int(ranges[i-1][1]))
        if int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])) and int_item[1] in range(int(ranges[i-1][0]), int(ranges[i-1][1]))  :
            ranges.remove(ranges[i])
            continue
        elif int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])):
            a = item
            b = ranges[i-1]
            # If a falls within b, replace the first digit of a, with b + 1; ex: [10, 14], [12, 16] --> [10, 14], [15, 16]
            a[0] = str(1 + int(b[1]))
           
        if i + 1 < len(ranges):
            # If end point of a connects with start point of b, combine ranges; ex: [16, 18], [19, 20] --> [16, 20]
            if int(ranges[i+1][0]) - int_item[1] in (0, 1):
                print('merging')
                print(ranges[i+1][0])
                print(int_item[1])
                a = item
                b = ranges[i+1]
                a[1] = b[1]
                ranges.remove(ranges[i+1])
                continue
    i += 1
print(ranges)


# Find the total amount between each range; ex: [2,5] would be 2, 3, 4, 5 or 4 added to total


total = 0
for item in ranges:
    int_item = list(map(int, item))
    total += 1 + (int_item[1] - int_item[0]) 
    print(f"added {1 + (int_item[1] - int_item[0])}")
print(f"total is {total}")

Next up is the resort with the hexagonal life floor tiles, where we tried to have a vacation in 2020, only to be called back immediately. They now also have an arcade with claw machines, and so we set about calculating which prizes are winnable and how few tokens we'd need to spend to do that.

The input lists the configuration for each of 320 machines in paragraphs of 3 lines. There are two buttons: A and B (that cost 3 and 1 tokens to press respectively) that will move the claw some positive distance in the X and Y axis. The goal is to get it to the given prize coordinates. And since the buttons can't be partially pushed, that makes each a system of linear Diophantine equations.

My initial solution was just to brute force by looping from 0 to 100 for each button and testing them. This is the classic quick solution to see what exactly part 2 will be. Which is that the target just gets shifted by 10 trillion on each axis.

So I quickly did some algebra:

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Solve:

    (94a + 22b = X) * 34
  - (34a + 67b = Y) * 94

 => 34(22b) - 94(67b)     = 34X - 94Y
    b * (34(22) - 94(67)) = 34X - 94Y

    b = (34X - 94Y) / (34(22) - 94(67))

Can do the same for a.
Test for integer solutions with (numer % denom == 0).

That's the note in the directory. Yes, I used numbers as variables... they're constants, and I find that its sometimes easier to see what's happening if everything isn't a letter. Of course, once you see this, you notice these are determinant/determinant, and so I had just derived Cramer's Rule. Making it a bit of a callback to the hailstones in Never Tell Me the Odds.

my $a_numer = $target->[X] * $b->[Y] - $target->[Y] * $b->[X];
my $b_numer = $target->[Y] * $a->[X] - $target->[X] * $a->[Y];

my $denom   = $a->[X] * $b->[Y] - $a->[Y] * $b->[X];

# Test for integer solution
if ($a_numer % $denom == 0 and $b_numer % $denom == 0) {
    return (A_COST * $a_numer / $denom + B_COST * $b_numer / $denom);
}

There are other ways to get to this. For example, you could use Linear Algebra, and express things as Ax = T with matrices:

[91 22] [a]  =  [8400]
[34 67] [b]  =  [5400]

Then x = A^-1 * T (after multiplying both sides by A^-1 on the left). This is easy to solve if you remember the formula for the inverse of a 2x2:

        -1
[ a b ]     =     1     [ d -b ]
[ c d ]       --------- [-c  a ]
               ad - bc

Note: the determinant = ad-bc, so constant in front is 1/det(A).

The nice thing about this problem is that this just works... none of the determinants for the button pushes is zero (and so this gives the unique solution, you just need to verify if it is integer). In serious code you'd need to protect against and handle that stuff. For AoC, I ran it and saw no division-by-zero errors pop up and submitted the answer. Because things turning out surprisingly nice isn't so surprising in AoC.

Of course this is a simple formula, so once we get rid of the non-digits in the input, dc can handle it easily (it also doesn't have negatives to worry about converting):

tr -c '[0-9]' ' ' <input | dc -e'?10000000000000' -e'so[dlar/3*rlbr/+ls+ss0]sS[lo+sylo+sxdlx*3Rdly*3Rr-sa3Rdlx*5Rdly*3R-sb4R*_3R*-ddlar%rlbr%+0=Ss.z0<M]dsMxlsp'

The use of ? here is just to slurp the entire input in (tr is also replacing the newlines here) before putting the amount to shift the targets on top (change that to 0 for part 1), and so will work still with the new dc. Nothing really fancy here.

And so, this was a light algebra problem, very suitable for a day 13.

So my solution works for the example data and theoretically should work for the real input. However, it is so slow that it would take about 25 minutes to return an answer.

I think the issue is that, for every single coordinate, I'm checking 8 other coordinates.

Please let me know if you have any ideas for optimization.

Edit: I let it run and it got exponentially faster, took about 2 minutes -- correct answer as well.

from pathlib import Path
path = Path(__file__).parent / "input_4.txt"
with open(path, 'r') as file:
    text = file.read()
grid = text.splitlines()


grid_width = len(grid[0])
grid_height = len(grid)


# From the input, create coordinates for the toilet paper rolls

def find_coordinates(grid):
    coordinates = []
    for i, row in enumerate(grid):
        for n, item in enumerate(row):
            if item == "@":
                y, x = i, n
                coordinates.append([x, y])
    return coordinates

# Find all of the neighboring rolls of any given roll

def get_neighbors(coordinate):
    x, y = coordinate
    neighbors = []

    for dx in [-1, 0, 1]:
        if x + dx < 0 or x + dx >= grid_width:
            continue

        for dy in [-1, 0, 1]:
            if y + dy < 0 or y + dy >= grid_height:
                        continue
         
            if dx == 0 and dy == 0:
                continue

            neighbors.append([x + dx, y + dy])
    return neighbors

# Find which of the rolls has less than 3 rolls in its 8 neighbors

def find_removable_coordinates(coordinates):
    valid_coordinates = []
    for coordinate in coordinates:
        counter = 0
        neighbors = get_neighbors(coordinate)
        for neighbor in neighbors:
            if neighbor in coordinates:
                counter += 1
        if counter <= 3:
            valid_coordinates.append(coordinate)
    return valid_coordinates

# Run loop

def main():
    count = 0
    
    coordinates = find_coordinates(grid)
    while True:
        print('cycle start')

        accessed_positions = []
        removed_positions = find_removable_coordinates(coordinates)
        if not removed_positions:
            break
        count += (len(removed_positions))

        # Add the removed rolls to a list
        accessed_positions.append(removed_positions)

        # Remove all accessed positions from the coordinates that are being searched
        for coordinate in removed_positions:
            coordinates.remove(coordinate)
        print('cycle complete')

    print(count)

main()

Next stop in the search for the Chief Historian, is the gardens we helped get running again last year on Island Island. Which provides a convenient food stop for The Historians after having searched the infinite mazes of Pluto yesterday. Having worked out the planting, we're now charged with calculating the cost of fences around the different regions of contiguous crops. Since the cost is area * perimeter (and area * sides for part 2), the fences between regions are effectively doubled up even if they aren't literally so (they need to be counted in the cost from the regions on either side of them).

The input is an 140x140 grid of capital letters (A-Z). Looking at it, you can see that it looks splotchy... like the result of some sort of cellular automaton. It could also have been done by placing a bunch of random seeds and randomly expanding them to fill the space.

My solution for Smalltalk is largely just a OOP recoding of the initial Perl. But there is one difference in part 1. In both, I use BFS to map out the regions, building a list of the plots in it as well as the neighbours (when we overstep... sentinels are naturally added to the sides). The neighbours also track a list of all the ways they get entered into from that region. With this in Perl, I count the inner plot edges of the region (those that go between plots of that region's type) when queuing the search. I use this to get part 1:

my $perm = 4 * $area - $inner;

Start with all 4 of the sides of all the plots, then subtract all the inners.

In Smalltalk, though... I got it from the other side:

" Perimeter is the number of ways into a neighbour: "
perimeter   [^neigh inject: 0 into: [:acc :n | acc + n size]]

The size of the neighbour (n size) is the size of the Set of ways it was entered. This part was quite reminiscent of finding the surface area of the lava blob in Boiling Boulders in 2022.

For part 2, both do it in the same way. I go through the neighbours, and slide along that edge until I get to the corner. To mark that edge, the most convenient place is where you stopped (so any duplicates from other neighbours on the edge find the same spot and don't get counted). We can use the direction the neighbour was entered to get the leftwards direction and make all our sliding go widdershins around the region. And so the sides of the region are counted by the number of corner posts at their widdershin ends. Something that's a bit ironic given the Easter Egg text (and it wouldn't have been a problem to count posts along the sides for part 1 either... the Fencepost Problem is an off-by-one error that comes from counting non-looped fences, but looping them makes posts equal to rails).

The problem description comes with a lot of examples, that were really helpful for getting this right. In particular, the importance of tracking the direction we slid into the corner is covered (same coordinate can have posts from different sides):

foreach my $d ($neigh{$n}->@*) {
    my $left = V( -$d->[1], $d->[0] );
    my $curr = $pos;

    # Slide widdershins down edge to find the corner:
    $curr += $left  while (exists $neigh{$curr} and grid_at($curr - $d) eq $plant);
    $corners{$curr,$d}++;
}

So this isn't the most efficient solution (it retraces edges a lot, but the problem isn't big so it's still quick), but it was a relatively simple one to implement.

Today we find ourselves on Pluto, and leave the searching of the infinite doughnought maze to the Historians. Our attention is instead taken by a set of what appear to be quantum-locked stones, that move and reproduce whenever we blink. Each stone has a number, and they're in a perfectly straight line... numbers with an even number of digits split, else they get multiplied by 2024 (or incremented to 1 if 0). The starting configuration for my input has 8 stones, with a 0 plus numbers with each of 1-7 digits.

This one is one of those one's where it emphasizes that the stones are ordered in a line, which should make you think how important that really is. Especially since the answer we want is order independent. And when you start looking at it that way, you see that you've got things in states, that have products that are independent and never interfere with the products of others. In other words, it's a Lanternfish problem.

And so typical Lanternfish approaches are going work for getting the scale up for part 2. So with Smalltalk that's moving things from a Bag of states to a new Bag based on the rules. In Perl I used substr to split the numbers in half, but arithmetic is much faster in Smalltalk for this:

stones contents keysAndValuesDo: [ :value :num |
    len := (value floorLog: 10) + 1.    " Note: floorLog returns 0 for value == 0 "
    (len even) ifTrue: [
        factor := 10 raisedToInteger: len // 2.
        next add: value // factor  withOccurrences: num.
        next add: value \\ factor  withOccurrences: num.
    ] ifFalse: [
        next add: value * 2024 + (value == 0)  withOccurrences: num.
    ]
].

Note that Boolean has been extended to promote to zero for the odd case.

Of course, there's one little detail to worry about with this problem and Lanternfish approaches... and that's that you should be somewhat concerned that the rules might make the states potentially open ended or very chaotic making the number of states explode with the stones. But this problem is nicely designed not to do that... my input tops out at 3811 states (and only 3759 are used for the first 75 generations), with the largest at ~38.6 bits. That's a very large matrix if you want to do that Lanternfish approach.

Since the input is numbers, I did do a dc solution for this one where you can just echo in the number of blinks you want:

echo 75 | dc -finput -e'?st[1+]s+[*1+q]sZ[_4R++s.q]sM[+s.A0 0]sH[dZ2/Ar^~3Rd3RrlRx_3RlRx+d3R:mq]sE[d0=Zd1-3RdA0*4R+dd9d^<H_4R;md0<MrdZ2%3R=E2024*d0=+rlRxd3R:m]sR0[rltlRx+z1<L]dsLxp'

This was originally written for v1.4.1, but you needed a hacked version like mine with skip lists if you wanted it to run reasonably (otherwise it could take minutes because of all the array accessing... it's fast to 50, but then it explodes). But the use of ? here just to read the number of blinks and is not a problem for dc v1.5.2 with hash table arrays, so it run well with that.

EDIT: Did a bit more exploration into the patterns in the input. Although my input stabilizes to 3811 states in every generation, there are 3849 different states that occur. The highest value is actually about ~44.44 bits and occurs 2 blinks in from the largest value in the input. That value is also responsible for the last new values that are reached... seven 4 digit numbers that all arrive on the 73rd blink, and all trace their origin back to that same largest input value.

Today we are going to help a reindeer reconstruct the hiking trail map of an area recently scoured by lava. We have a digital height map (0 to 9) and are told to, for all starting points (elevation 0) find out how many peaks (elev. 9) can be reached from that point while always climbing exactly one level per step.

The total peaks sum is the part1 answer.

Solving this reminded me a lot of several previous map search puzzles, so I did it the obvious way: Use the input as a linear flat map, with newlines as a guard between each horizontal line and the next. I also put a line of guard characters before and after the input.

Next was a scan of the input map, for each '0' start a recursive DFS, using a parallel seen[] array to note visited cells, then just aggregate the counts.

In hindsight, it would probably be better to cache the search results from each visited cell, so that later searches could reuse the work previously done.

For part2 we are instead told to count how many different ways there are to reach a top, here I also used a recursive search, but totally forgot to make it memoizing!

Adding just two lines just now to return early with a cached answer, otherwise do the search and cache the result made my code more than twice as fast. The only reason it wasn't even larger was because every path had to be just/exactly 8 steps long, with very limited fanout, so the total overhead wasn't anything like previous search puzzles where a cache could very often save 95-99% of the work.

Today an amphipod has a classic problem: It has a disk that is fragmented and it wants to defragment it.

The disk map is stored in a compressed format, alternating between a file length and a free space length. If there is no free space between two files, the free space length is 0.

For Part1, the amphipod moves blocks, starting with the last file block which it then moves into the first free block, systematically moving all blocks as close to the front as possible, and as a side effect reversing the storage order for all moved files. We then produce a disk checksum consisting of summing up for every file block the product of the file number and the block position.

For Part2, because the amphipod realized that the disk becomes too fragmented, it will instead only move full files as close to the front as it can find a large enough free space for them. The checksum is then calculated in the same way as Part1.

My Perl code solved this one using brute force for Part1:

First expand the run length encodings, using -1 to designate free blocks, the filenr ID for the files. My input contained 10K files, so worst case this could be expanded to an array with 9*2*10K = 180 K entries, but the average should be closer to half of this.

This setup made part1 really easy, just iterate from the front to locate free blocks and from the end to find file blocks to move.

For part2 we need to find open gaps large enough for a full file, so here it made much more sense to have free lists, either organized by size (1-9) and location, or just by location. Since all partially filled free spaces would result in a tail space which would have to be inserted in the right order in the smaller map I decided to use the simpler setup of a single free list.

I thought about keeping a cache of the last found free list entry of each size, but went brute force instead, always scanning from the beginning. I counted the scan iterations, the average was 133 entries inspected before finding a large enough slot, so a better data structure would have been faster.

Perl runtime was 271 ms on my slow Surface.

I started on a more ambitious Rust version but never had time to finish it the way I would have liked.

It would in fact have been easier to solve the defragmentation problem in an optimal way, using size-ordered free lists and always try to move files to an exactly large enough gap, only fall back to larger slots if none could be found.

Later edit:

Watching TV with my wife ("71 degree North", check it out if you can!) and waiting until Oslo midnight to make the reddit post, I looked somewhat unhappily at what I had written above:

I decided to at least implement the simplest possible cache I mentioned, just a table of the last found free entry for each size, this immediately dropped the runtime to 47.8 ms, so nearly 6x faster!

The number of free list steps dropped from 133 to 4.6 per file.

The only small problem was that I had to update the cache also for the tail end of a partially filled free space, when that was before the current cache entry.

    if ($flen >= $len) {
        my $remfree = $flen - $len;
        $free[$f] = $remfree;
        $free[$f+1] += $len;    # update free block position
        $files[$i+2] = $fpos;   # The file is moved here
        $lastfree[$len] = $f+2; # Next scan starts after this entry

        if ($remfree && $lastfree[$remfree] > $f) { $lastfree[$remfree] = $f; }
        last;
    }

Note that my lastfree[] array has entries for 0..9, so that I could blindly update it also for totally filled slots, but it was a percent or two faster to check for this situation and skip the zero updates.

We're on the roof of the top-secret Easter Bunny installation, where we realize that the city contains a bunch of antennas, at many different frequencies. They are named with single digits, upper or lower-case letters, so there can be up to 62 different kinds.

For Part1 we are told to look for antinodes, defined as a location that are in line with a pair of same-frequency antennas, at the same distance away as the internal pair offset. We want to determine how many total locations contain one or more anti-nodes.

In Perl I created a hash of arrays, the hash is keyed by the antenna name (ascii byte value), this points to an array which contains the (x,y) coordinates of every antenna with that name. The list of anti-nodes was another hash table, keyed by the corresponding (x,y) pair. The main issue is that we have to ignore any locations that are outside of the city grid.

This worked pretty much as quickly as I could type it in.

For Part2 we need to iterate over all multiples of the internal distance, so we get a lot more antinodes, but otherwise it was more or less the same process. The only possible wrinkle was that if an offset between two antennas (dx,dy) has a common divisor, then we must get rid of that so I had to write a gcd() function to fix this even though it seems like it never actually happened?

Total Perl runtime 16 ms.

In Rust I first implemented it the same way, using HashSet, but later on decided that the name key set was small enough that it didn't matter if I extended it by filling in the gaps between '9' and 'A' and between 'Z' and 'a', and instead of a HashSet of antinode addresses I just used a linear byte array, using bit 1 for Part1 and 2 for Part2 locations.

When I ran my code just now the fastest was 3.9 us, so I'll have to average 1000 iterations to get a more precise measurement:

...

The average over 1000 iterations was 3519 ns, so less than half the 8 us shown by u/maneatingape.

I therefore tested 'cargo bench year2024::day08' and got

running 3 tests
test year2024::day08::parse_bench ... bench:       3,745.39 ns/iter (+/- 247.27)
test year2024::day08::part1_bench ... bench:         724.87 ns/iter (+/- 29.24)
test year2024::day08::part2_bench ... bench:       1,375.97 ns/iter (+/- 94.11)

So his total was about 5.8 us on my machine, not a very big but still somewhat significant difference.

Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report.

what do they mean finding the most common bit in the corresponding position? what's the corresponding position? I thought at first that the most common bit is how many 1's or 0's there is in the binary number, but it's not, I couldn't find the pattern here plus my native language is not english

edit: okay now i get it, thanks for the replies!

Today we need to cross a bridge which is currently under repair, only the final calibrations remain, but the engineers have a problem: Each calibration consist of a target value and a computation which is supposed to reach that value. A group of nearby elephants have stolen all the operators so that only the numbers remain, our task is to figure out where we can insert '*' (multiplication) or '+' (addition) between the numbers to make it come out OK.

These equations ignore normal operator precedence rules, both are at the same level and will be applied as soon as possible.

In the test data set the number of values is so low that it seems OK to just try all combinations, in the real input we find up to 12-14 numbers but we would still only need to test 4096-16384 possibilities.

However, it is immediately clear that if the last operator is a multiplication, then the target value must be divisible by the last number. Otherwise it must be an addition, so then we can just subtract that value from the target and retry with the remaining set.

The obvious choice is therefore a recursive descent where we for each level first test if multiplication works, if so divide and recurse down, otherwise subtract and recurse.

This process finished in a ms or two in Perl.

For Part2 we are told that one elephant had hidden away a third operator, concatenation!

At this point all Perl programmers rejoiced since for Perl any number is both a string and a numeric value, so that checking if the last N digits match an N-digit value is dead simple, and so is removing the corresponding digits from the current target so that we can recurse.

My Rust code started out with the exact same logic, converting numbers to ascii and back for each concatenation attempt, and it took about twice as long as the Ape, even though I started with a sanity check: For concatenation to be possible, the last digits had to match so I checked this before doing the string conversion and comparison.

After I had stared at this logic for a while I realized that I could repeat the final digit check until it either stopped matching or all digits were OK, at which point the temporary target would contain the remaining leading digits, without any need for any binary-to-ascii and ascii-to-binary conversions!

At this point the inner logic was quite short & nice, it ran in 163 us:

fn try_part2(target:u64, nums:&Vec<u64>, pos:usize) -> bool
{
    if pos == 0 {return false;}
    let pos = pos - 1;
    let n = nums[pos];
    if pos == 0 { return n == target; }

    if target % n == 0 {
        let rem = target / n;
        if try_part2(rem, nums, pos) {return true;}
    }
    let mut n2s = n;
    let mut t2s = target;
    while n2s > 0 && n2s % 10 == t2s % 10 {
        n2s /= 10;
        t2s /= 10;
    }
    if n2s == 0 {
        if try_part2(t2s, nums, pos) {return true;}
    }

    let diff = target - n;
    try_part2(diff, nums, pos)
}

I guessed that u/maneatingape should have very similar logic, his time of 136 us on an Apple CPU could easily be explained by the optimized divider circuit in later Apple cores, but when I tested with cargo bench year2024::day07 I got 133 us on my Intel CPU, so he is still a fraction more efficient!

I am using the standard library to split the input into lines, I then parse each line with an extract_u64() function. When I tried to go hardcore with a full custom input parser, it turned out to be significantly slower.

The task for the day is to search a rectangular area (130x130 cells in my input) of a lab where a single guard is patrolling. Since there are no walls around this area, the guard will leave (and then randomly return presumably?) if her walk hits one of the edges. Before this happens, she always walks in a straight line until she hits an obstacle, whereupon she will turn right and keep going.

For Part1 we just need to simulate this process in order to count how many unique cells she will have visited before leaving.

Direct step-by-step simulation was the obvious choice, and afaik probably also the most efficient, except when walking in a horizontal direction where a language like Perl provides index/rindex, but I did not bother, just brute forced it to get the first star.

For Rust, C(++) and other low-level languages, direct simulation is a reasonable choice, so that's what I used here, recording in each cell that it had been visited with a bit per direction of travel.

For Part2 we want to introduce a single extra obstacle in the path the guard is about to walk, placed in such a spot that her path will turn into an infinite loop. I recorded the path taken in Part1, so for Part2 I just iterated over this path, checking what would happen for each possible choice. I could not see any obvious ways to short-circuit this search.

I first had the good idea (NOT) to think that any choice had to be placed just after a point where the guard had previously passed going right. Such a location would indeed work, but not if the real solution depends on hitting one or more previously unhit obstacles before starting the loop. Since we need to determine all possible locations, this means that part2 is going to require far more work than Part1, but we are all used to that at this point.

My main problem is that u/maneatingape is about an order of magnitude faster, so I must in fact have missed at least one huge optimization here!

Perhaps it makes sense to backtrack from each turn taken by the guard and check if a reverse path will hit a point previously visited, such that a right turn there would start the loop?

There are far less turns than steps in the Part1 path, so this should be faster!

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

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

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

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

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

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

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

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

For Part1 just iterate over the pages:

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

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

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

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

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

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

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

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

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

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