For 2023, we're back to fixing snow production, but on a global scale so the weather machine from 2015 won't do. And so we need to travel to the sky islands. The map this time is a stack of sky islands, which we will work our way up from the bottom and then come back down. Making this another year where the numbers are out of order. And it all starts with us being launched to the sky by trebuchet. Which naturally needs us to do calibration for.

The input for this one is not just numbers this time... it includes lowercase letters which sometimes spell out the digits one through nine. Zero is not involved in any way, which is convenient for some solutions. I will note that vowels do not occur outside of the digit words (where they're required)... and quick test reveals that Chrome does not detect this as any language. So there is some protection against the autotranslate + copy-and-paste issue. Which is an untended gotcha that really don't want people to run into on the first day.

In general, 2023 stepped up difficulty and complexity a bit... and that's particularly noticeable on the early days. Which makes me wonder how much of that was the influence of AI... a little complexity and gotchas to mess a bit with the LLMs so that just maybe, they fail the first try and give the competition programmers a chance (because, they're really fast, especially when allowed to bring their toolkit).

The problem this time is simple... we want the two digit number made of the first and last digit on each line. For part 2, that includes interpreting the words as well. And the gotcha for part 1 is tested for in the word "treb7uchet"... it's a small wrinkle I special cased when the test failed and I saw it:

say "Part 1: ", sum map {(m/^\D*(\d)\D*$/) ? "$1$1" : (m/^\D*(\d).*(\d)\D*$/ and "$1$2")} <>;

For part 2, the gotcha is "twone", "eightwo" and "oneight". Which are present the given test input, but they aren't actually tested. I didn't really notice this issue until after, because I just took my regex to:

m#(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += 10 * $table{$1};

m#.*(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += $table{$1};

With table being a hash of of the words and the digits to their value:

my %table = ('one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' => 5,
             'six' => 6, 'seven' => 7, 'eight' => 8, 'nine' => 9,
             map {$_ => $_} (1 .. 9));

This avoids special casing, and this is because I was thinking of how I was going to do dc for part 2.

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'[+d]sF[s.z3<Lq]sN0?[0d[3R48-d9<Nrd0=F3Rs.z3<L]dsLxrA*++?z1<M]dsMxp'

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'1dd:t18996:t2dd:t32285:t3dd:t24203441:t4dd:t1299471:t5dd:t694023:t6dd:t43444:t7dd:t39325060:t8dd:t49523414:t9dd:t683663:t[dsf]sF[lf0=Fdsl]sN[39-]sS0?[0ddslsf[r48-d9<Sr36*+36 5^%5[d3Rd3R36r^%;td0!=Ns.r1-d0<I]dsIxs.z2<L]dsLxs.llA*lf++?z1<M]dsMxp'

dc doesn't have any string processing, and so these are taking the input as lines of ASCII values. And so it does use ? to process the input (this would be the point where I fully adopted that and trusted it... although it's back to non-functional, so these are dc v1.4.1 solutions).

Half of that part 2 is building the table:

1d d:t 18996:t              # 14 23 24          eno
2d d:t 32285:t              # 24 32 29          owt
3d d:t 24203441:t           # 14 14 27 17 29    eerht
4d d:t 1299471:t            # 27 30 24 15       ruof
5d d:t 694023:t             # 14 31 18 15       evif
6d d:t 43444:t              # 33 18 28          xis
7d d:t 39325060:t           # 23 14 31 14 28    neves
8d d:t 49523414:t           # 29 17 16 18 14    thgie
9d d:t 683663:t             # 14 23 18 23       enin

This maps both the digits and the strings (as essentially base-36 numbers) to the value. The ASCII values are converted to values on the range of 1-35 (0 not being a value in the problem is good here). Note that the strings are backwards because the lines are loaded on a stack and so we parse the lines backwards.

The trick to matching strings here is keeping a window of a five digit base-36 number (36*+36 5^ shifts, adds in the new, and the chops off the oldest with a mod of 5³⁶ ). Then there's a loop that takes progressively shorter mods of the window to compare them against the table until it gets a match. When a match is found, the N macro is called, which always sets l to the value, but only sets f once. Yes, first and last do end up backwards, so we add 10 * l + f.

I also did a Smalltalk version, and chose to run with someone's comment about doing string substitutions on the words... I saw "o1e" as a substitute for "one" and immediately knew what was up, and ran to do it. The overlapping means you can't just replace all the words willy-nilly, but if you replace them in a way such that the later substitutions still can match, you're fine. And "o1e" is doing that... it's leaving the "o" at the front for a "twone" and the "e" at the back for an "oneight". Had 7 been spelt "sevon", then you'd need "on1e". Or, alternately, you could change the order of the substitutions so that the "sevon" is done first and "one" doesn't have to worry about it. In any case, it was easy to hand solve for a table of substitutions to start, but then I followed up with code that generates that table (and so is flexible for other languages). It was a fun little exercise that got some extra mileage from the problem.

And so we get a heavier start than we've seen before... numbers and strings together. This helps get us ready for the fact that more of the early problems are going to be heavier than in the past. I seem to recall a bunch of "good dog/scary dog" memes being posted about the shift back and forth between days.

My original Part 2 solution for this day took 21 seconds and 725Mb to run, so it took quite a bit of wrestling to get it small enough for the Raspberry Pi Pico.

I tried a naive DFS search on key collection order and although that technically worked the proof-of-concept took nearly 80 minutes on my laptop, which would have been over 13 hours on the Pico even if I managed to claw back a 10x speed-up. I tried Iterative Deepening A*, but that didn't even finish after an hour on the laptop; there are just too many combinations that get very close to the optimal path length, and a lot of those come from taking the shortest path early on in the search tree.

I swapped back over to A* and used u/e_blake's heuristic to get the search space down as far as possible. The heuristic is to take the sum of the shortest paths from each robot's current position to the furthest key that they still need to collect. That works way better than my initial heuristic of totalling the shortest paths connected to all uncollected keys:

With each open set entry and each G entry taking 12 bytes (distance, robot locations, collected keys) that gets within spitting distance of the 200KiB target, but not quite optimally. With ~8k+ entries in the G set, we really should be looking at a ~16k element hash table to keep good performance (hash tables are ideally power of 2 on the Pico because % is an expensive operation) and that one hash table blows 192KiB of our 200KiB budget.

The distance/priority for both the open set and the G set can easily fit into 16 bits for this day. The collected keys are already pretty optimal, you need 26 bits so you're not wasting much with a 32 bit integer as a bitfield. The robot combinations need to be able to represent 4 entries at any one of 30 locations (26 keys + 4 starts), and since 30 choose 4 is 27,405 then that can in theory fit into 16 bits as well.

The trick to get over (under?) the line is to use a Combinatorial Number System to encode the robot locations into an int16_t. At a smaller 8 bytes per entry for both blocks of memory, we can finally afford a decent sized hash table, albeit at an additional cost of compressing and uncompressing the state data each time.

Final memory budget (at peak) ended up being ~188KiB:

-------------------------------------
LBA Stats
  [Blocks] Total: 9  Free: 1  Used: 6  Sentinel: 2
  [Bytes] Total: 204608  Free: 12672  Used: 191936
  [FreeChain] Free: 1
-------------------------------------
LBA Blocks
[...9FB8][ Sentinel]    0 blocks       0 bytes
[...9FD8][Allocated]  225 blocks    7200 bytes <-- Edges to adjacent keys
[...BC18][Allocated]  113 blocks    3616 bytes <-- Path length to all keys
[...CA58][Allocated]   20 blocks     640 bytes <-- Combinatorial cache
[...CCF8][Allocated]    8 blocks     256 bytes <-- Key locations
[...CE18][Allocated] 1536 blocks   49152 bytes <-- Priority queue (open set)
[...8E38][Allocated] 4096 blocks  131072 bytes <-- Hash map (g_score)
[...8E58][     Free]  396 blocks   12672 bytes
[...BFF8][ Sentinel]    0 blocks       0 bytes
-------------------------------------

Runtime is surprisingly still quite respectable: ~1.8ms on PC and ~340ms on the Pico @ 125MHz.

Thanks again to u/e_blake for sharing that heuristic!

[code]

I am learning (e)lisp for fun and ended up making a highly overcomplicated solution to the "Virtual machine" problem from 2024/17.

In AOC_17_2024_advanced_macro_version.el I define op-codes using lisp macros, leading to a very compact notation. I have furthermore implemented a Wozmon type monitor program to poke the VM (however, not very useful for solving the problem).

I think (e)lisp is very nice for AOC, what do you think?

I was a little worried about being able to squash this one down small enough for a microcontroller. My original solution for this one took ~64MiB and after swapping over to less wasteful data types it would still take >500KiB to store the back end of the transformed sequence, so it needed a re-think.

The approach I took for that first solution wasn't particularly unique, I think a lot of people did more or less the same. Since the second half of the phase transform has coefficients of the form:

1111
0111
0011
0001

It's possible to calculate the next phase with a running sum:

ABCD -> A + B + C + D = W -> A + X
0BCD ->     B + C + D = X -> B + Y
00CD ->         C + D = Y -> C + Z
000D ->             D = Z -> D

But doing it phase by phase, you still need the entire back end of the sequence (up to the signal offset) in memory. For my input that's over half a million elements.

Looking at the sequence of additions, it turns out it's possible to calculate the full history of one row based only on the history of the row below it.

The bottom row is trivially always going to come out the same value, since it only ever depends on the original sequence number and it always gets multiplied by 1, but it's a little easier to see the pattern if we number them anyway:

000D = D₁ -> 000D₁ = D₂ -> 000D₂ = D₃ ->...
=>
D, D₁, D₂, D₃, ...

The row above depends only on the current value and the bottom row:

00CD = C₁ -> 00C₁D₁ = C₂ -> 00C₂D₂ = C₃ -> ...
=>
C, C₁, C₂, C₃, ...

The next row is where it gets interesting:

0BCD = B₁ -> 0B₁C₁D₁ = B₂ -> 0B₂C₂D₂ = B₃ ->...
=>
B, B₁, B₂, B₃, ...

Notice that B₂ + C₂ + D = B + (C₂ + D) and that (C₂ + D) = C₃. Which means B₃ = B₂ + C₃.

If we can store the full history of one row across all phases so that we've got access to [C, C₁, C₂, C₃, ...] we can calculate the whole sequence for the row above: [B, B₁, B₂, B₃, ...]. Since we're doing 100 phases, that full history is only 100 elements.

There's some additional housekeeping, like repeating the signal without actually having that many repeats in memory, and putting the digits into a ring buffer so that we're only keeping the most recent 8 digits processes, but that's the core of it:

    vector<char> phaseHistory(100);
    for (int i = 0; i < signalToProcess; i++)
    {
        int s = baseSignal.Next();
        for (int phase = 0; phase < (int)phaseHistory.size(); phase++)
        {
            s += phaseHistory[phase];
            s = s % 10;
            phaseHistory[phase] = s;
        }
        digits[i & (digits.size() - 1)] = s;
    }

[Full code]

Memory: 650 bytes for the input, 100 bytes for the phase history and 8 bytes for the digits - well under the memory constraints I'm aiming for! The runtime on PC is a respectable but not great ~115ms. (It's easy to get that down to ~25ms by only reducing the phase history with % every 4 loops, but it obscures the logic)

I'm aware that u/askalski and u/maneatingape have got very sophisticated solutions that use magic maths, but I have no idea if those techniques can be used to speed up this approach further. I'd need a couple of weeks of background reading just to take a run at those!

Overall I'm happy just to cross this one off my list of nemeses.

Extraction is going to be hot air balloon, and to get them to fly requires heating the fuel with "Bob" the anthropomorphized (with a pair of googly eyes) fuel heating machine. And in order to do that, we need to sum the requirements, which are in balanced quinary (aka SNAFU numbers). More on balanced numbers (albeit ternary) can be found here:

https://en.wikipedia.org/wiki/Balanced_ternary

And so the input is a list of balanced quinary numbers, one per line, with - and = for the negative digits. All the numbers in the input start with a 1 or 2, which means they're all positive, and so add to a positive value. This makes the problem easier.

My initial solution in Perl didn't use any outside requirements. I did the base conversions myself, and so I did it directly from and to balanced quinary (with the summing done with the regular +). Of course, with everything being positive, and bringing in base conversion from the ntheory module, it can be done with shifting of the values by half the power (and back):

my $sum = 0;
while (<>) {
    chomp;
    tr/=\0550-2/0-4/;
    $sum += fromdigits( $_, 5 ) - floor( 5 ** (length $_) / 2 );
}

my $part1 = todigitstring( $sum + floor( (5 ** ceil(log($sum) / log(5))) / 2), 5 );
$part1 =~ tr/0-4/=\0550-2/;

print "Part 1: $part1\n";

This only works because everything is +'ve, though.

However, my initial Smalltalk solution does do negatives... it can handle cases like:

-1
=0

Which is -21. You can also test that with 10-1 + 10=0 - 2000 with a solution that only handles positives.

And the way it does that, is by subclassing Array for SnafuNumbers. So they're treated as arrays of digits, and I do the addition digit by digit handling the carries:

+ other [
    | res val |
    res := SnafuNumber new: maxDigits + 1 withAll: 0.  " +1 to catch overflow "
    (1 to: maxDigits) do: [ :i |
        val := (self at: i) + (other at: i) + (res at: i).

        " do appropriate carry, if needed "
        (val abs > 2) ifTrue: [
            res at: i+1 put: val sign.
            val := val - (5 * val sign).
        ].

        res at: i put: val.
    ].
    ^res
]

maxDigits is set to 32, and 5³² is a 75-bit number, so that should be more than enough.

I also did a dc version, and in converting the input I went with an unusual order of 012=-, because it makes for a cleaner tr command than tr '=\055012 '0-4'`.

tr '012=-' '0-4' <input | dc -f- -e'1d:t2d:t[=]3:t[-]4:t0[r0r1r[A~2+5%2-3Rd5*_4R*4R+_3Rd0<L]dsLx*++z1<M]dsMx[5~d_3R1-2/+d0<C]dsCx+[;tnz0<P]dsPx'

And so we come to the end of another solid year (and I see that this time I remembered to submit part 2 before reading the story). This is the year where people using AI started to make some noise, but it was not a big thing yet.

Having finished planting, we leave the elephants and monkeys to look after it and head towards the extraction point. Which involves going through a valley filled with small blizzards.

The input is a text grid, with a wall around it (except for slots for the start and end). The inner section of my input is 35 rows and 100 columns. So, not prime, with a gcd of 5. Conveniently, no up/down storms are in the columns with the notches for start and end... so the pattern of up/down blizzards cycles every 35, and the left/right every 100... and altogether it repeats every 700 (the lcm).

And it's the dynamic nature of the maze that's the real problem today. Precalculating the patterns is going to be better than repeatedly generating the same things while doing the search. You certainly could do all 700 grids to get the maze at any position. But, I went with doing the vertical and horizontal separately... for 135 instead (you just check the two of them to verify a space is empty).

And so I had two arrays of hash tables (that acted as sets for the blizzard positions). That worked plenty fast for Perl, but Smalltalk doesn't like it (it take minutes), and so I've made a TODO to convert the Smalltalk to using arrays of some form for tracking the blizzards. Bit arrays are a possibility, as the number of rows is <64, so each column can be stored in a integer (unless you only have 32 bits).

But once the dynamic maze is made quickly accessible, things were just a fairly standard A*, with steps to the target as the heuristic. Looking at it now, I was a bit curious... because one little quirk in this A* is that time needs to be part of the visit list:

    next QUEUE  if ($visit{$time, $pos->[0], $pos->[1]}++);

Because circling back to the same spot at a later time can be correct... in fact, the test case given shows that in the first few moves. So we only prune those at the exact same time. So I was wondering how much do we gain... with the circling, its harder to tell how close you really are. And the answer (with a quick test) is that it's more than twice as fast. So worth it, but with the size of the problem, it's the difference between 9s and 4s (for part 2), on the old hardware. This problem is really more about the handling the map... the search isn't that heavy once you have something for that.

Part 2 for this one just required taking part 1, throwing it in a subroutine and calling it multiple times and so was quick to add:

my $time = &cross_valley( 0, $start_pos, $end_pos );

print "Part 1: $time\n";

# Silly elf!  Next time don't forget your snacks!
$time = &cross_valley( $time, $end_pos, $start_pos );
$time = &cross_valley( $time, $start_pos, $end_pos );

print "Part 2: $time\n";

There is an interesting bit of proof for why stitching these together like this works, and you don't have to worry about some better overlap case across these searches. One where you take a different path, arrive 3 turns later and turn around and do much better going back than the one that arrived earlier. And that involves a Strategy-stealing argument. Because we can always wait, any early arrival doesn't have to immediately leave, so it can wait for the same opportunity that a later arrival would use and steal it (thus getting the same performance). So the best from the previous leg will always beat or tie any later arrival.

This was a fun search... a dynamic maze and a little game threory to confirm that what I did was correct.

We arrive at the site of the grove (a large crater) and discover the plants are dead. Because apparently they require volcanic ash... and our messing with the magma flows unknowingly interfered with that. Fortunately, there's a backup plan to plant replacements, we just need to arrange the spacing.

And so we get an automata type problem. The input is a binary grid of cells representing positions of elves, and we have rules for how the elves will move each round until they reach an equilibrium where the each have no neighbours.

Part 1 just wants 10 rounds (and then to find the bounding box and subtract the number of elves from that). This is a usual way to make sure that people have a working simulation before moving on.

And my solution was again simple and basic (just following the steps)... it wasn't fast, although cleanup has gotten it to 20s on the old hardware. Part of that cleanup was moving to bit operations for tracking neighbours:

my $neigh = 0;
foreach my $dir (@Surround) {
    $neigh = ($neigh << 1) + exists( $elves{$pos[0] + $dir->[0], $pos[1] + $dir->[1]} );
}

With that I can easily tell if there's no neighbours, and can also use with bit masks to handle testing the proposed directions (pairs of direction and the bits to test):

my @Dirs = ([1, 0xE0], [6, 0x07], [3, 0x94], [4, 0x29]);

This is another puzzle in this year with a theme of "try" patterns. We had the falling blocks, then the wrap around movement on the cube (which can arrive at a wall and fail), and now we have the possibility that multiple elves could be trying to move to the same square and need to be reverted. And the way I did that here was to push the elves onto lists at the location they want to move to. After everyone submits their proposal, I do a pass and undo the ones with multiple elves (list length > 1).

This was another one where my part 1 time is surprisingly long at 2h (but part 2 was just a few minutes after). There are a lot of commented out print statements in the code... so I'm thinking I probably had some silly errors to debug from still not being 100%.

I got tired of tabbing to the browser to grab inputs and paste answers, so I built a CLI that does the whole loop. Then I rebuilt it in C# to learn the language. Both work end to end.

cargo run fetch -y 2015 -d 1 # puzzle text + input into cache/

cargo run solve -y 2015 -d 1 # run your solution offline

cargo run solve -y 2015 -d 1 --validate

cargo run solve -y 2015 -d 1 --submit

Output looks like:

year 2015 day 1 in 288µs (959ns parsing)

part one: 138 (correct) [216µs]

part two: 1771 (correct) [71µs]

Then --submit turns those into (new star), and running again shows (starred) since AOC only grades each part once.

The part I haven't seen other AoC tools do: --validate checks your answers against fornwall's independent solver before anything gets submitted. Wrong answers on the site cost an escalating cooldown, but the solver answers the same question as many times as you want, for free. So --submit only sends what the solver agreed with. If the solver doesn't cover the puzzle yet (live event), it submits anyway, since that's exactly when you'd be ahead of it.

Some other things it handles:

Solve fetches whatever is missing, so a fully cached run works offline with no cookie.

When part one earns a star, part two's text gets pulled in the same run.

Inputs are cached with a hash of the session that fetched them. Inputs are account specific, so switching accounts refetches instead of letting you submit an answer computed from the other account's input. That one bit me for real.

Day 25's second star is awarded, not puzzled, so the tool knows not to keep asking for its part two.

No solutions ship on main. There's a compiled template to copy for your first day, and my solutions live on a separate branch if you want examples. Inputs and puzzle text stay out of git, per the site's wishes, and it sends a User-Agent with a reachable contact.

https://github.com/scadoshi/rustmas

https://github.com/scadoshi/sharpmas

Credit: Advent of Code is Eric Wastl's (https://adventofcode.com/about). The verification leans on Fredrik Fornwall's solver (https://aoc.fornwall.net/, https://github.com/fornwall/advent-of-code).

On AI: I used it as a working partner on these repos, for doc wording, test scaffolding, and refactors I'd already designed but didn't want to push through by hand. The line I hold is understanding before generation: I write the code I want to write, which is most of it, and hand off what I could write in my sleep. Design decisions are recorded in each repo's context/ directory, including the ones that got reversed and why. Every line was written or reviewed by me.

While being lead by the monkeys through the jungle, they inform us (through the elephants) that we need a password to get through a force field. Which involves tracing a path on an irregular board. A board that happens to look very much like a cube net (both the test and the input... but different nets).

And part 1, we treat it flat... with wrap around in both directions that skips over the spaces. And that's exact what I did... because this is clearly a puzzle you want to confirm part 2 of early. Although, looking at my time, it took an hour and a half... so I'm thinking maybe I had a late start. Because there's nothing complicated about my part 1. I add sentinel spaces to the right and bottom, so that I can just try stepping forward. If it's a space, I loop until I find a non-space. If that square is empty move forward, otherwise don't and go to the next command. The commands being tokenized with:

my @cmds = ($input[1][0] =~ m#(\d+|[LR])#g);

Part 2 is where the input is folded into a cube and things become real. My first thought was that this is the heavy one... like Jurassic jigsaw or the 3D beacons in the past. And having learned from those... my first decision was to not do any fancy folding and handling of different cube nets, but build a table just for the edge transitions of my actual input. And, IIRC, every input uses the same net. Still, I figured this problem was enough without generalizing that bit. I left that task for another day, it is enough of a job to be a day's problem on its own.

But that makes the initial test cast invalid. So one thing I did, was pull out a handy programming aid... the 4x4 Rubik's Cube on my desk, and I added some small circle stickers to it for the walls in the test case. These stickers are handy twisty puzzle solving aids I keep around. I'm not a speed cuber, I just like getting new types of twisty puzzles and coming up with solutions... and it's useful to tag pieces to follow them when trying things out. Weak stickers and Blu-Tack are good for this. And were good here, because it allowed me to make a version of the test case with the same map... as well as follow along when verifying and testing things.

So I had this table for reading the input into 6 squares:

# Assumed Layout:
#    .WB
#    .R.
#    GY.
#    O..
my %sides = ( 'white'  => [0,1], 'blue'  => [0,2], 'red'    => [1,1],
              'yellow' => [2,1], 'green' => [2,0], 'orange' => [3,0] );

Next up was building a table for the edge wraps. And like in the past with these big ones, I just did it by hand. That sounds like work and prone to error, but if I did code it, I'd still go over the table line by line verifying that'd I made the right table. Which is the same work as building it by hand. I would not have done less, just more coding. It's just too important to get right.

And so my table is 24 lines like this:

$wrap{white}[0]  = { side => 'blue',   facing => 0 };
$wrap{white}[1]  = { side => 'red',    facing => 1 };
$wrap{white}[2]  = { side => 'green',  facing => 0 };
$wrap{white}[3]  = { side => 'orange', facing => 0 };

$wrap{red}[0]    = { side => 'blue',   facing => 3 };
$wrap{red}[1]    = { side => 'yellow', facing => 1 };
$wrap{red}[2]    = { side => 'green',  facing => 1 };
$wrap{red}[3]    = { side => 'white',  facing => 3 };

...

Non-cubers might not realize this, but there is a standard pattern of the colours on a cube. So using the colours provides a little more information that you might think to those that know that pattern.

One thing to note is that not all the information is explicit there. It doesn't have any data for how the coordinates are transformed. That's because it's extractable from the directions:

# Only one coord value is important, the other is either -1 or $side
# Because of dir order, parity tells us which of y or x we want.
my $idx = $pos->[$dir % 2];

# When going between 0 and 2 facing, the edge flips
if ($dir % 2 == 0 && $new_dir % 2 == 0 && $dir != $new_dir) {
    $idx = $size - $idx - 1;
}

# $new_pos similarly has one coord as 0 or $size-1, the other
# being set to the index value, based on the direction parity.
my $new_pos = ($new_dir <= 1) ? [0,0] : [$size-1,$size-1];
$new_pos->[$new_dir % 2] = $idx;

And with the geometry and wrapping handled, the rest is pretty much the same as part 1.

This was a problem were I very much took my time to make sure I got everything right and didn't go off on some tangent. And although it is a multi-dimensional problem on the surface of a cube, I had a physical representation of it to check and test everything. Which certainly helped.

Hello!

For part 1 of 2024's day 6 problem, I was able to get some Python code that works for the small example map they gave but not my puzzle input. As it stands I have about 100 extra locations the guard visited than I should have. I was wondering if anyone here could take a look at my code and give me a hint as to where my error is, as I am really struggling to find it. I know it has to be where my movement is programmed, I just can't figure out what part needs some tinkering. Thank you in advance!

with open('Day 6/mapinp.txt', 'r') as file:
    samp_inp = file.read()

format = samp_inp.splitlines()
matrix = []
for item in format:
    matrix.append(list(item))

#locate the guard, return the matrix coords and then the way the guard is pointing
def find_guard(map):
    coords = []
    for item in map:
        if "^" in item:
            coords.append(map.index(item))
            coords.append(item.index("^"))
            coords.append("^")
            return coords
        elif ">" in item:
            coords.append(map.index(item))
            coords.append(item.index(">"))
            coords.append(">")
            return coords
        elif "<" in item:
            coords.append(map.index(item))
            coords.append(item.index("<"))
            coords.append("<")
            return coords
        elif "v" in item:
            coords.append(map.index(item))
            coords.append(item.index("v"))
            coords.append("v")
            return coords


#nice function to track movements
def move(map):
    on_map = True
    step_count = 0
    step_loc = []
    #index error means the guard has left the map
    while on_map == True:

        try:
            coords = find_guard(map)

            if coords[2] == "^":
                if map[coords[0]-1][coords[1]] == "." or map[coords[0]-1][coords[1]]  == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]-1][coords[1]] = "^"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = ">"

            elif coords[2] == ">":
                if map[coords[0]][coords[1]+1] == "." or map[coords[0]][coords[1]+1] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]][coords[1] +1] = ">"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "v"

            elif coords[2] == "v":
                if map[coords[0]+1][coords[1]] == "." or map[coords[0]+1][coords[1]] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]+1][coords[1]] = "v"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "<"

            elif coords[2] == "<":
                if map[coords[0]][coords[1]-1] == "." or map[coords[0]][coords[1]-1] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]][coords[1] -1] = "<"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "^"

        except IndexError:
            print(f"Guard has left the premises after {step_count} steps!")
            on_map = "False"

    return map, step_loc

comp_map,coordinates = move(matrix)

move_counter = 0

for item in comp_map:
    for pos in item:
        if pos == "X" or pos == "^" or pos == "<" or pos == ">" or pos == "v":
            move_counter += 1
        else:
            continue


print(f"The guard has visited {move_counter} distinct locations.")

The monkeys have returned, this time to help us if we can answer a riddle (which is basically doing algebra). We know this because the elephants speak monkey, and we can speak elephant.

The input is a long list of expressions. Some are just a constant for a monkey to yell, others are basic arithmetic (+, *, -, and /) for a monkey to apply to the numbers yelled by other monkeys. It's ultimately a big expression tree and we want the value at root, much like problems like "Some Assembly Required" in 2015.

For my initial solution in Perl for part 1, I went for was the classic brute force job queue... queue up all the rules as you read them in, then run through the queue. Solve what you can, requeue what you can't. Until you solve you want. I did follow it up later that day with the recursive approach... where you start from the root and recurse to get the parts you need and combine them. Both are fast (the problem isn't big), but the recursion is twice as fast because it solves things in order.

Part 2 reveals that the expression for the root monkey is actually =, and we need to calculate the humn value to yell. My initial solution for this was to use recursion to build the expressions for both sides as stings (it's an infix walk, so every return gets parens added around it). The side without humn I can just eval to solve to a number. Then, I did some testing... the operations suggest that the relationship could be linear. And it is (I ran a loop evaling the string for humn from 0 to 1000, and they had the same delta). This is further confirmed by looking at the string, as all the / in the expression on the humn side come after it... so there isn't a 1/x situation, it's just an Ax + B situation (where the constants could be rational).

And so, I took the values at humn = 0 and humn = 1, and with an initial value and the delta from those, interpolated the value for humn. Which was fine for my input, where the denominator of the delta is 4. But I do have a second input in my directory... I'm not sure if it was someone else's or handcrafted... but it has a delta of: -47488/2673. That number comes from my Smalltalk version of this solution (Smalltalk automatically promotes the division to Fraction). But the initial Perl solution, runs into floating point accuracy problems and completely misses. This could be fixed by making Perl do the same thing Smalltalk does (track the value as a rational, using gcd).

However, I decided to make a note to do a Perl solution using symbolic arithmetic instead. And I did do that, although I cheesed it a bit. Basically, the idea is that we get a number on one side, and an expression tree on the other... we apply algebra to reduce that tree and isolate the humn by doing the opposite to the number on the other side. Making the computer do things like we would be hand (which in all honesty, looking at the expression string... it isn't that long, you could take that and do it by hand if you wanted).

But, looking back at the initial brute force solution I thought about that sort of solution. The rules you have still define a tree, but they don't all get applied bottom-up (because the target's in the middle, so some things need rotating to get it to the top). IE, given a = b + c, you could get to the position where you know a and c, and need to calculate b, but this isn't the rule for that. But we can make and add that rule (b = a - c). And so, basically the idea is to just do symbolic algebra on all the rules (which are simple)... to solve them for each variable in terms of the other two, and add all three rules to the job queue. Eventually, one will activate to solve the full thing. Optionally, this could also be done just by having the rule once in the queue, and detecting when you have two of three and doing the symbolic algebra as part of the loop to get the third.

So this was a pretty cool problem, and the fact that the expression is kept linear makes getting a solution for this more accessible. Linear numerical interpolation has been an option for a number of puzzles.

Still unable to contact the Elves with communication device, we turn to trying to decrypt the star fruit grove's coordinates from a file on it.

And so we get a ring structure puzzle. Which was a pleasant break from the previous day. In fact, for the Perl solutions, I just went with array splicing:

@list = map {[$_, $list[$_]]} (0 .. $#list);

for (my $i = 0; $i < @list; $i++) {
    my $idx = 0;
    $idx++  until ($list[$idx][0] == $i);

    my $item = splice( @list, $idx, 1 );
    splice( @list, ($idx + $item->[1]) % @list, 0, $item );
}

The elements of the list are a pair of the ordering index and the value. Brute force search to find the next one in the order, and then splice it out, and the in at the destination. To get the final sum, I search for the zero and get the three values I need with sum map {$list[($zero + 1000 * $_) % @list][1]} (1 .. 3). Nothing fancy about this at all. It's simple, and for part 2, slap a foreach (1 .. 10) around it. It slows down a bit... to 12s on the old hardware, but that is very tolerable for getting a solution with very little work.

For a fast version of it, I did a C version with actual pointers and structures. Doubly-linked ring and an array to track the order (which could have been a separate second constant single-linked ring in the structure if you wanted). Instead of modular indexing (because I wasn't maintaining a list), I just walked the ring using modular arithmetic to shorten the length... and since both directions are needed anyways, I'm already set up to "choose the shorter way". The ring size is only 5000, so the most we ever need to walk is 2500, even if the numbers are 800 million times larger in part 2.

So, this is a good break day after the past few, and leading into the final stretch.

Having discovered that obsidian is forming, we decide to use it to crack some geodes by building geode-cracking robots. To get the obsidian we need obsidian-collecting robots, which need clay-collecting robots, which need ore-collecting robots. Fortunately, we start with an ore bot, so we have initial production, but the rest requires building additional robots which cost varying amounts of materials, and can only be built one per turn.

And so we get to this problem. This one I managed part 1 in under two hours, but part 2 took 3 more hours and is still not very good. Part of that might have been still not feeling to great. And cleaning it up now has made it faster (just over a minute for part 1, and half that for part 2), but I haven't had time to really work on it this month.

My initial solution was a job queue one. With the mining at Saturn, I remembered making a mess with a recursive approach, and scrapping it for a queue. So I decided to start there this time. One thing I did do as part of clean up was to do a recursive version... it's not any faster, but I wanted it anyways in case I got any ideas that could use that.

In trying to get a solution, I applied heuristics. Basically using a couple decades of German board game experience with building economic engines. First up was realizing that you don't need to build robots past the the maximum cost for that material... because you can only build one thing a turn. If you're producing enough ore to cover any ore cost and recoup it every turn, you don't need more... it will stack up and be worthless. Although it's not necessary the best to max things out, in part 2, blueprint #3 in my input only wants 3 ore miners to be able to build geode crackers every turn (every other robot costs 4 ore... so this is an impact on the engine building for efficiency on the end game).

Another heuristic was a little less safe... I did some estimating on how long it would take to set up an engine to start producing geodes, and came to the conclusion that the game is probably too short to really catch up if you fall 2 geode crackers behind. Because it could be better to be behind for a little bit to build a stronger engine... but that engine needs to be strong enough to get ahead with enough time left to make up and exceed the amount you fell back. And going from -2 to +1 crackers with still enough time to make up all the geodes (all while the "opponent" is also building more crackers, so it's probably not just 3 you need) really doesn't seem likely. It is a bit like flexible version of the greedy algorithm... of always just build a cracker when you can (which IIRC some people used). And adding that to mine, I get a tiny improvement with having both.

The one other thing I did was that if you don't build a robot in a turn, any that you could have built are removed as options on the next turn. That sounds like greedy, but that's standard board game strategy. If you're saving up for something you can't buy yet, that's okay (and you should buy it as soon as possible), but completely passing a turn and then turning around to build something you could have built a turn earlier... that's a mistake.

So, this one is one where I can do any of the searches reasonably fast with my solution, it's just that it asks for doing so many of them. Which adds up. And although my recursion has memoization (although I'm not sure how much benefit it really gives)... when the blueprints change, it needs to be reset.

[ Removed by Reddit on account of violating the content policy. ]

Having reach the exit of the cave, we shelter there while the lava continues to rain down. Watching the lava fall into a pond and cool, we decide to measure its cooling rate to see if it could be making obsidian. And to do that we need to calculate the surface area.

The input is a list of 3D coordinates of cubes that make up the drop. The coordinates only range from 0-19, so it's not a huge volume.

And for part 1, my thoughts were along the lines of an inductive solution. One cube has 6 sides, for a surface area of 6. Add a second and you add another 6, but if it's adjacent to the first, you need to subtract 2 (one from each cube). And assuming you have the correct surface area after n cubes, the next cube is going to add 6 new faces, and subtract 2 for each adjacent. So we can just iterate over the list in one pass doing that. That makes for a nice simple solution even for dc:

tr ',' ' ' <input | dc -f- -e'0[6+_4R1+5C5*_3R1+1F*r++d2r:tddddd1+;tr1-;t+r1F+;t+r1F-;t+r5C5+;t+r5C5-;t+-z1<L]dsLxp'

Just converting the 3D coordinates into a flat array index. To mark a cell as occupied we put a 2 in the array. This means we don't need to test for the existence of a neighbour, just to subtract the values of all the neighbours.

For part 2, we realize that the surface area for cooling is just the outside that's in contact with the water. And so what I visualized was casting/molding around the drop. So I extended the bounding box by one on each side (to guarantee a path all the way around), picked a corner of it, and BFS flood filled it. The result being a visited list that was a molding of the outside of the drop. It has an internal surface (which is the outer surface of the drop) and an external one (which is a cube and easily calculated). So I applied part 1 to those cells and subtracted the outer cube surface.

my $encase_surface = &get_surface( values %encase );
my $outer_surface  = 6 * (($max - $min + 1) ** 2);

print "Part 2: ", $encase_surface - $outer_surface, "\n";

The values of the encase table (which is the visited list) are the same as a key, but the key is converted to a string by Perl and would need converting back, so we might as well use the value to avoid that.

I really liked this one. Part of that is probably because I came to quick revelations (this was my fastest part 1 time since day 6) that allowed me to avoid having to really work with the 3D structure. There was a bit of extra incentive in that I still didn't feel 100%, and so was going to try for anything simple before moving on to mapping 3D surfaces.

I've always enjoyed low level programming so this year I decided to scratch that itch by starting to do some hobby programming with microcontrollers. There's nothing more frustrating than trying to learn everything (new toolchains, new SDKs) all at once while trying to build something non-trivial, so the obvious answer was to take my existing, known-good 524 star repo and port that over to a microcontroller. It would also give me a chance to revisit some of my original solutions that were significantly sub-optimal.

I chose the Raspberry Pi Pico (RP2040) as the target microcontroller because it's geared towards learners, it has a thriving ecosystem and I really admire the work the Raspberry Pi Foundation do.

The repo is more or less in a fit state to be public after the first four years (2015-2018) have been squashed, the support libraries have been exercised and the workflow has had the major rough edges knocked off. There's still plenty more to do though, so I'm expecting it to be in a state of flux for the next 12 months or so.

Performance

The RP2040 is on average between ~100-200x slower than the laptop I'm using for development and I've set myself a soft target of 1s per solve on the microcontroller hardware (including IO transfer time), meaning that I need to target ~5ms or under on PC. What's really nice though is that by the time a solution has been squashed enough to fit in the memory restrictions, that's almost always a significantly faster solution than my original solution and often sub-ms without any further faffing.

The high level summary for puzzle solution times on the RP2040 so far:

There's a full breakdown of current timings here.

Note: I do my timings a little differently to a lot of the forum regulars who work on producing ultra-fast solutions. The timing starts on the host PC when I start transmitting the input over USB and stops when I get the final byte of the answer back. I time both parts separately and each part is an independent solve, I don't have any solutions that calculate both part 1 and part 2 answers at the same time.

There are some things that are absolute Kryptonite to the RP2040. MD5s are a particular weakness, hence the bad Max and Average times for 2015 and 2016, and anything that requires 64-bit maths is emulated in software.

IO can be an issue as well. 2016 day 7 has an input file ~170-180Kb in size, which takes ~1.5s just to transfer over USB-CDC. Many of the days are ~400-600x slower than PC purely because of the time it takes to send the input file.

Common changes

The most common changes I've made are to variable types and to data structures. 64-bit integers were always my default choice so that I didn't have to worry about figuring out which puzzles needed more than 32-bits and which didn't, but that's not practical with the 32-bit Pico. With an existing solution as a reference it's pretty quick to swap types and check that we still get the same result, and thankfully most of the days so far are perfectly solvable using 32-bit maths only. 2017 day 15 is probably the one that suffered the most from software emulated 64-bit integers; there is a way to implement the generators using only 32-bit arithmetic, which is what I use, but it's quite a few instructions and so it ends up being the slowest solution for all of 2017.

My default choice for data structures in my full-fat repo has always been std::set or std::map, even for data that would naturally go into an array. The main reason is programmer efficiency: you don't need to worry about getting a correct array size and insert returns a value to indicate if the element has been inserted or not, which is a very common test required in a lot of the algorithms. For the microcontroller, especially when trying to squeeze solutions into the memory limits, arrays/vectors are the default choice wherever possible, and I've written simple open-addressing (with linear probing) hash maps and sets templates. This is where a significant proportion of the speed-ups have come from compared to my original solutions.

Algorithm changes

Surprisingly, fewer than 20 have needed a complete overhaul on the algorithm used.

2015 day 13 is the first one which needed a change, swapping from a brute-force scoring of all possible permutations to a recursive DFS. Day 19 in the same year was the only other one which needed a completely different approach. That one was originally one which made my nemesis wall with a really horrible home-brew parser-adjacent algorithm, but after seeing in the megathread that it could be solved using a greedy algorithm it ended up significantly faster on the Pico than my original solution running on a fast PC by a few orders of magnitude.

2016 and 2017 also only needed a couple of days swapping over to a different algorithm. 2018 is the year so far that's required the most, with almost half of all days being revisited in terms of how they're solved.

Bit Packing

Of all the changes I was expecting to make, bit-packing values is the one I haven't needed anywhere near as often as I thought.

2016 day 18 didn't need bit packing to fit into memory, but I thought it would be fun to parallelise the logic into bitwise operations anyway. 2016 day 11, one from my wall of shame needed the search states packing in order to keep the queue size small. The others have largely been ones where we're dealing with large (for a Pico) 2D areas, like the infection states in 2017 day 22 and the cave terrain in 2018 day 22.

Windowing

Windowing, or working on only a small chunk of the full data range at any one time, has been a life-saver on a few occasions. 2018 day 17 has been the one I'm most pleased with, although the chunked seiving on 2015 day 20 was nice to work through, especially with the approximation function I iterated on to get a good lower bound starting point.

Maths

I tend to avoid closed-form solutions and have a personal preference for programmatic approaches, but there's really no beating the closed form solutions or using maths insights for speed and size. The Josephus problems are an immediate example of not having enough memory to process large rings of elves, or the Cosmological Decay approach to the Look-and-say sequence completely bypasses the need for large amounts of memory.

Recursion

By default when using the C/C++ toolchain each core on the Pico gets 2KiB of stack assigned. That's really not a huge amount by any stretch, so most recursive solutions are a no-go. Approximately ~9 solutions have needed swapping over to using an explicit stack, making it one of the most common changes I've had to make.

While it's true that all recursive algorithms can be implemented in terms of a stack based algorithm, the devil really is in the details and I never appreciated how many little decisions about state representation and return values would need making.

Take a normal recursive function:

int Func(int n)
{
    // ...
    int n1 = Func(n + 1);
    int n2 = Func(n + 2);
    return n1 + n2;
}

Stack frames and function calls give you 3 separate things:

1. Local variables - these are what an explicit stack structure trivially gives you
2. State - after the call to Func(n + 1) you need to encode somehow the fact that you've made that call and the next recursive call is the one to Func(n + 2)
3. Return values - do you put the return value in the current stack top and let the parent take care of popping after reading, do you let a child pop its own stack and write the return into the parent stack frame, or something different. It was a real eye-opener to sit down and actually code up something like 2015 day 22 using an entirely stateful stack based approach.

Forum Help

I have a general rule that I won't look at anyone else's solution until I've got a solution of my own. Even if (and it commonly is) it's a rough and ready solution which take seconds or minutes to run and chews through half the memory in my machine. I'm pleased that for 523 of the 524 stars I've been able to get to a working answer with no hints, but there's absolutely no way I'd have been able to get the 200 on the microcontroller so far without the valuable suggestions, and the public repos of forum regulars. There have been over a dozen of these solutions that are either direct re-implementations of other people's solutions, like 2018 day 9 or 2018 day 14, or have used suggestions and explanations from information posted on the forum such as the equivalence pruning for 2016 day 11. u/musifter's review series has been a great focal point to discuss the problems with people who really know their stuff.

Thank you one and all!

Microcontrollers

The hardware you can buy now is utterly incredible for the price: I've been targetting the Raspberry Pi Pico as far as possible, but the Raspberry Pi Pico 2 W is a 150MHz 32-bit CPU with 520KiB RAM, Bluetooth and WiFi for under £10. As someone whose first computer was a Spectrum 48K, this is a ridiculous amount of computing power to have for very little money and in a tiny space. If I had kids who wanted to learn how to program, I would definitely think about sitting them down in front of Thonny and a microcontroller. It has exactly that same immediacy of feedback I remember from typing out Basic listings to see something cool happen on screen.

Having found an alternate exit, we find ourselves at the bottom of a tall shaft with boulders falling down it. And so we need to simulate them to avoid being crushed... but the "real" task is apparently proving the accuracy of the simulation to the elephants.

And so we get this Tetris inspired problem. The shapes aren't just the set of tetrominos. a couple pentominos are also included in the set. And there's no rotation, just side to side movement and falling.

The input is a list of left and right moves for the pieces as they fall. Mine is 10091 long, which is a prime number. And both it and the list of 5 blocks cycle.

For part 1 we just want the height of the tower after 2022 rocks (and it is not a very efficient packing at all).

My first choice was to store the block shapes in a table of relative indexes of the squares:

my @Blocks = ([[ 0,0], [ 0,1], [ 0,2], [ 0,3]],              # —
              [[-2,1], [-1,0], [-1,1], [-1,2], [0,1]],       # ✚
              [[-2,0], [-2,1], [-2,2], [-1,2], [0,2]],       # ⅃
              [[-3,0], [-2,0], [-1,0], [ 0,0]],              # |
              [[-1,0], [-1,1], [ 0,0], [ 0,1]]);             # ⬜

Then the plan is essentially to stream over this list and the input list. In the case of Smalltalk, that literally involved BlockStream and MoveStream classes with a stream interface. But in Perl, it's just indices being incremented mod the size of their list.

Then for dropping the blocks, I went with a simple "try" pattern (this is using a Vector class for the coordinates and directions):

do {
    my $move = $Input[$Inptr = ($Inptr + 1) % $Input_len];

    # Try sliding
    my @try = map { $_ + $Dirs{$move} } @squares;
    @squares = @try if (all {0 <= $_->[1] < 7 and !$Grid{$_}} @try);

    # Try dropping
    @try = map { $_ + $Down } @squares;
    @squares = @try if ($dropped = all {!$Grid{$_}} @try);
} while ($dropped);

# Place piece:
$Grid{$_} = '#' foreach (@squares);

Nothing fancy... attempt the operation and accept if it succeeds. There are multiple ways to do this sort of thing, try-catch blocks are another one.

Part 2 tells us that the elephants are not impressed yet and want more... a lot more:

my $Num_rocks = 1_000_000_000_000;

But of course, iterating a trillion times is out of the question, so we want to find when this loops (and then do the calculations to jump to the solution). This is one of the two problems in 2022 that I broke into the top-1000. I wasn't that fast for part 1, but part 2 only took me 14 minutes... so I wasn't amazingly fast on the second part, but it gained a lot of positions. So my code was apparently better positioned for doing part 2 than many.

For finding the loop, I went a hash table with the state being:

my $key = "$Inptr:$blk:" . join( ',', @tops );

Where $Inptr and $blk are the indexes of the moves and blocks, and @tops is the highest point in each of the 7 columns (relative to the highest point). This involved simply changing the subroutine for doing the dropping to return the final resting squares of the new rock (instead of just the highest point), which I then use to update the @tops array. I figured this was probably safe... and it worked.

But in regular Tetris, you can slide a piece under an overhang. And so, with that unease, and a desire to do different things for the Smalltalk solution, I went for being a bit more robust. First off, I represented the shaft with bytes there... 7 bits wide and using bit operations to place things. Which I can treat as characters (ASCII ones even, although often not printable ones). And so for detecting a repeat of the the position of the shaft what I did was build a string (starting from the top) while also ORing the characters into a mask... when the mask hits 127, all bits set, so we've seen a rock in every column. And so we have a map of the full structure at the top, not just the tops. So the elephants get to be a little more confident.

This is was a really fun one. It's another in the category of game inspired problems, and those always tend to stand out.

I need help finding where my understanding is off because my answer agrees with the test case but doesn't give the right answer for the real input. I'm also using AOC to learn Rust so there's probably something I'm missing about the language itself as well.

The main idea is to add up the differences of the quotients of the before and after positions of the dial for each rotation. I've included my main.rs:

use std::env::args;
use std::fs::File;
use std::io::{BufRead, BufReader, Lines};
use std::path::Path;

const DIALSIZE: i16 = 100;

fn parse_input(path: &Path) -> impl Iterator<Item = i16> {
    let file: File = File::open(path).unwrap(); // open the file
    let lines: Lines<BufReader<File>> = BufReader::new(file).lines(); // iterator to the reader of the lines of the file
    // iterator over the lines but with L replaced with - and R replaced with nothing to be positive
    let rot_strs = lines.map(|line| -> String { line.unwrap().replace("L", "-").replace("R", "") });
    rot_strs.map(|rot_str| -> i16 { rot_str.parse::<i16>().unwrap_or_default() })
}

fn print_dial(dial: i16) {
    println!(
        "Dial at {}",
        (dial % DIALSIZE) + DIALSIZE * i16::from(dial.is_negative())
    );
}

fn main() {
    // open the file
    // read line into buffer
    // replace L with -1 or R with nothing
    // parse into integer
    // only work in raw position, never mod
    // count += abs(div(old_pos + rotation, DIALSIZE) - div(old_pos, DIALSIZE))
    // repeat
    let args: Vec<String> = args().collect();
    let path: &Path = Path::new(&args[1]);
    let roterator = parse_input(path); // iterator over input lines that gives integers
    let mut pre_rot: i16 = 0;
    let mut post_rot: i16 = 50;
    let mut pre_div: i16 = 0;
    let mut post_div: i16 = 0;
    let mut hits: i16 = 0;

    roterator.for_each(|rot| {
        // update dial position
        pre_rot = post_rot;
        post_rot += rot;
        print_dial(post_rot);
        // update zero hits
        // div_euclid rounds toward negative infinity for negative lhs and postive rhs
        // if postive or zero add zero, if negative add 1
        pre_div = pre_rot.div_euclid(DIALSIZE) + 1 - i16::from(pre_rot.is_negative());
        post_div = post_rot.div_euclid(DIALSIZE) + 1 - i16::from(post_rot.is_negative());
        hits += (post_div - pre_div).abs();
    });
    println!("Final zero count: {}", hits);
}

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.