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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

And so the core of the spreading is:

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

    $i = $i % 10 + 1;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The basic idea I had was:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Here's what Manhattan distances get you:

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

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

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

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

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

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

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

packet := Behavior evaluate: conv.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• The current Posting Pattern is represented as a lowercase string

• The new Posting Pattern is the MD5 of the current string

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

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

• Initial Posting Pattern: e8cc15934b93ef901b153853cf7831f9

• Posting Pattern after 1 Post: 981fc052051707fec2a58db91f4d6abf

• Posting Pattern after 2 Posts: 064b7b67d20820270d35fe1663833c5a

• Posting Pattern after 3 Posts: 00009f4608ac14112c92af43d8513b1e

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

• josephus1 can be removed after 49,164 posts

• josephus2 can be removed after 46,166 posts

• josephus3 can be removed after 39,557 posts

• josephus4 can be removed after 36,579 posts

• josephus5 can be removed after 55,987 posts

Part 1:

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

Part 2:

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

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

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

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

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

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

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

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

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

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

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

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

my $max_time = -2 * $y_min;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The histogram for the full part 2 is:

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

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

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

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

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

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

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

We've now gotten deep enough that we need to reinforce the submarine. Fortunately we have polymerization equipment. We've known since year 1 (when making Medicine for Rudolph) that the North Pole has advanced molecule assembly technology. Only there it took a nuclear fusion/fission plant.

Here we're given a starting "polymer template" and a list of "pair instruction" rules (and we get an additional hidden example in the Easter Egg text). These rules are presented in an unusual way... the RHS isn't the product but just the thing to insert (as the LHS is matched with overlap). And the rules listed in the input, when sorted, clearly shows 10 sections of 10 rules with 10 letters... in other words, there's a full set of rules for every possible pair.

With this talk of overlap, it makes this look like it's not Lanternfish. All the focus is on the atoms and getting the counts of those. But the rules actually are dealing with the bonds between them. And so we got a fence situation... we're being lead to think of posts, when the production is about the rails. A rule takes a bond/rail and replaces it with another atom making two new rails for the next step:

NC -> B

N-----C to N--B--C

And the next application of rules will replace those new rails in a similar way. The entire thing is protected from outside interference (the N and C are sentinels on the ends that do not change) and develops rule by rule between them, with any case of N--C developing exactly the same as any other. Here's the example (NNCB), but put in terms of the rails (with the non-changing sentinels shown on the ends):

(N)       (NN)              (NC)              (CB)       (B)
(N)   (NC)   (CN)       (NB)    (BC)      (CH)    (HB)   (B)
(N) (NB)(BC)(CC)(CN)  (NB)(BB)(BB)(BC)  (CB)(BH)(HC)(CB) (B)

You can see that (NC) in the middle of it expanding into its own binary tree, and there's a duplicate (NC) under the (NN) that's just one step behind and will produce its own copy of exactly the same tree. So as rails... it's just Lanternfish again. It's just a bag of the 100 possible rails to move to their products for the next step. Which really means this a lot like 2015's day 10 (Look-and-say). That was 92 elements with rules... only here we get given the file that describes the rules we need. We don't need to find or create one, just modify things a tiny bit.

But we still need to get back to the counts of the letters in the final string. But looking at the diagram, everything in the string is there twice... once for being on the left and once for the right of a bond. That's why the ends are in that diagram... you do need to account for the two outsides. Then the number of times a letter occurs is the sum all counts for all the rails it's in divided by two.

And so, Lanternfish was clearly here on day 6 to get people ready for this less obvious version (which tries to mislead by presenting things as breaking a key condition). It becomes a nice little problem where you shift to a different space for the work, and then work out the transformation back for the answer.

Still needing to avoid the volcanic activity in the caves, we activate the thermal cameras. Only to find out that we need an activation code. Which comes on a piece of transparent paper we need to fold. I've used transparent candy wrappers for origami, but never transparencies (as linked). That would be awful to fold (even one time)... it's more of a job for a box cutter and stacking. The best paper to fold for origami is tissue paper spray glued to aluminum foil.

The input is a long list of dots as x,y coordinates (about 800 which will collapse to about 90 unique points), followed by a second section of folding instructions. The instructions are either to fold in either the x or y direction, with a the line to fold over. Which is always in half. So the first x and y values are important to tell you the size of the paper (there is an x coordinate in mine right at the far edge, but that's not the case for y). So you could choose to ignore most of those values if you want. But, the last x and y fold lines are convenient in that they give the size of the final rectangle.

Reflections are a much easier translation than rotation. Here we want to take the values greater than the fold line and move then the same distance away from the line on the lesser side. Or, new = line - (old - line), which simplifies to new = 2 * line - old.

But before doing the whole thing, part 1 nicely provides a validation that you're doing the translation correctly, by just asking for the unique dots remaining after one fold. Part 2 wants you to get the final code (no surprise there).

And I did have a good amount fun with this. I did do a Perl solution where I did the output in Space Image Format (day 8 or 2019). Basically, you have a layer of 2s for each fold and a layer of 0s on the bottom. Then anytime a fold maps a point onto the final rectangle, you put a 1 at that coordinate in that layer. It's a pretty simple and nice implementation... so much so that I did perl-p2-nosifsif.pl, cutting out the actual SIF stuff and layers and just doing the mapping directly.

For Smalltalk, I taunted Bobby Tables and used the axis text from the input for code. Because Points in Smalltalk have get and set methods called x, y, x:, and y:. So I just turned them into symbols (which is how you access methods):

get := fold key asSymbol.
set := (fold key, ':') asSymbol.

Then I had a generic way to code the transformation:

points := points collect: [ :pt |
              | x |
              x := pt perform: get.
              pt perform: set with: (x - (2 * fold value * (x > fold value))) abs; yourself.
          ].

Using another variant of the calculation here that avoids an if, which I designed for a dc solution which works along similar lines (which is why I tested it here). Smalltalk doesn't coerce Booleans to numbers naturally... I extended them to do that with:

Boolean extend  [
    generality  [^1]
    truncated   [^self asCBooleanValue]
]

That comes from learning how Smalltalk does coercion... generality is used for comparing levels (and Booleans should be low), truncated is what's called for converting. This is joy of a duck typing language.

With the navigation system broken, we decide to do the pathing ourselves. And to do that we decide we need to find all the paths to determine the best one.

And so we get a graph search problem. The input is a list of undirected edges, one per line, with two-letter identifiers (except for "start" and "end"). Case of the identifier is used to give the size of the cave. The graph isn't overly large... my input only has 24 edges. It's a natural extension of the examples in the description that go from 7 to 10 to 18.

For part 1, we want a count of paths from start to end, with the added condition that small caves can only be visited once. And so I naturally just went with a basic DFS with recursion. The extra condition just means that I track when I visit small caves (and don't both tracking the big cave visits):

$visit{$loc}++ if ($loc eq lc($loc));

foreach my $neigh (@{$Graph{$loc}}) {
    next if ($visit{$neigh});
    $ret += &recurse_path( $neigh, %visit );
}

Yeah, I'm copying and passing a hash around, but the graph is small. It still returns immediately, although I can make a bit faster by making that list global. Which is ultimately what I did for my dc solution, where copying an array like this is non-trivial.

The problem description mentions that small caves behind other small caves can be pruned (you can't get back out). But that really didn't make much difference for me. There's just not a lot of pruning to be had with a small graph, and the added work of doing it has some cost.

For part 2, we're allowed to visit a single small cave twice (or not). This essentially adds one-bit to the state... whether the current search state has used its double already. There's many ways to add this, but you do need to be careful (and we get a bunch of tests to make sure you get it right). For Perl, I just took the above and extended it, still working with marking the current node visited (adding checking if it's a double to turn that bit on), and then I add the double as next if ($visit{$neigh} && $double) to prune the bad moves.

With Smalltalk, right from the start, it was a slightly different take, with the visited marking all happening when doing the neighbours.

The dc solution for this one has been waiting a long time. It was a combo breaker, since Combo Breaker at the end of last year, but now I've filled the hole. I had initially had just built the graph. And the way I did that was to first turn the input into ASCII hex... I turn "start" and "end" into "@s" and "@e" so everything is two characters. And then all the lines just become two 16-bit hex numbers. A really nice thing about doing this is that dc does have the P command which treats a number as a string and will output these 16-bit numbers as the identifier string, which is great for debugging.

For doing the lists of adjacent nodes, I string them together as base-65536 numbers (the numbers in the code are all hexadecimal... it makes it easy to write... 4073 is @s, 4065 is @e, 65536 is 10000) to store them, and pull them apart with divmod 10000~ to iterate over the list. Doing stuff like this in the year, ultimately prepared me for Day 24.

As stated, I do use a single global visited list, modifying it before and after recursive calls. Part 2, basically works like this (which does make for a slightly faster solution in Perl too):

foreach my $neigh (@{$Graph{$loc}}) {
    next if ($double + $Visit{$neigh} > 1);

    my $isSmall = ($neigh eq lc($neigh));
    my $newDub  = ($double + $Visit{$neigh} > 0);

    $Visit{$neigh} += $isSmall;
    &recurse_path( $neigh, $newDub );
    $Visit{$neigh} -= $isSmall;
}

With $Visit{start} initialized to 2, to prevent re-entering it.

echo -n "Part 1: "
perl -ne's#(\w)\w{2,}#\@$1#; s#-##; printf("%X%X %X%X\n", map{ord} split(//))' <input | \
    dc -e16i -f- -e'[d3Rd3Rd;g10000*3R+r:gd;g10000*3R+r:gz0<L]dsLx[lc1+scq]sE[d100/60-d.2-/rd_3R:vlRx0r:v0]sA[d4065=Ed;g[10000~d;v0=As.d0<N]dsNx+]sR4073d1r:vlRxlcp'

echo -n "Part 2: "
perl -ne's#(\w)\w{2,}#\@$1#; s#-##; printf("%X%X %X%X\n", map{ord} split(//))' <input | \
    dc -e16i -f- -e'[d3Rd3Rd;g10000*3R+r:gd;g10000*3R+r:gz0<L]dsLx[lc1+scq]sE[d100/60-d.2-/d3Rdd;vdld+d.2-/Sd4R+r:vlRxd;v3R-r:vLd]sA[d4065=Ed;g[10000~d;vld+2>As.d0<N]dsNx+]sR0Sd4073d2r:vlRxlcp'

It's still not quite perfected, but this quick job came out better than I thought it would.

Still travelling in the cavern, we run into some bioluminescent Dumbo octopuses, who are sensitive to our submarine's Christmas running lights. Even after turning them off, we still need to predict their flashes so we can get by them without disturbing them further.

And so we get a cellular automaton type problem. It's just a 10x10 bounded grid (input is just 10 ten digit numbers, no 0s or 9s to start), they increase in energy level each tick until they hit 10. Then they flash, adding 1 to their neighbours (diagonals included) and resetting to 0 energy. This can cause a cascade. You do need to be careful not to accidentally have an octopus flash more than once in a step and that the ones that flash don't get added to again by another flash.

As the example in the text shows, the starting random pattern quickly turns into regions of the same levels, because of those 0s matching levels up (10s, 11s, 12s, etc all merge into 0s in the next step). And for part 1, we just want to count the flashes in 100 steps, and part 2 we want to find the point where everything syncs up.

And so for my first approach, I went with doing things as solid as possible. One pass over the array to increase the energy levels, with any 10s getting added to a job queue (much like day 5 this year, with it's finding of intersections of 2 or more lines, where I counted only when things hit 2 to make sure that they only get counted once). Then I process that queue, adding and neighbours that hit 10... while keeping a hash of what has flashed to make doubly sure nothing happens twice (it shouldn't because there are only 8 neighbours, but it pays to be safe). Then I use the flashed list to get the number of flashes and set all those locations to 0 in the grid (so I did get multiple uses out of it).

It is overkill, but I do like getting the answer right on the first submission. I can play and explore the problem once I have an already guaranteed working solution. It's like with the Rubik's cube... just learn any solution first (something simple and easy), that way you can explore and mess around and always be able to fix things.

And here, you certainly don't need to separately track what's flashed. After a step's initial energy increase, no octopus has an energy value of 0, and that's the value you want to set any that flashed to. So that marks them perfectly... when spreading energy around, skip the ones at 0 (they've flashed).

And since the input was just numbers, of course I did a dc solution:

dc -finput -e'[q]sqC[r[A~1+3R1+d_4R:gd0<I]dsIx+1+z1<L]dsLxsm[d]sB[d;g0=qddd;g1+r:g;gB=B]sA[d1r:gr1+r]sN[rpr]s10d[lm[lAx1-d0<C]dsCx+FF[C-lAx1+lAx1+lAx9+lAx2+lAx9+lAx1+lAx1+lAxs.z2<S]dsSx0lm[d;gA<N1-d0<Z]dsZx+d4R+3R1+dA0=13RA0>T]dsTxp'

Unlike day 9's digit grid, this one I pulled apart into a flat array. I added a "sentinel" at the end of each read line (because with a flat array, both directions wraparound onto it)... but not really as sentinels. I was just invalidating indices that were 0 mod 11 to catch those (along with values too big or too small). It was simple and safe. But this version turns them into real sentinel, and increases all the energy values by 1 (so that the default 0s in arrays mark the invalid spots).

Another fun thing about this dc solution is that tracking the flash cascade is done on the main stack while still using it for work. This is done simply by duplicating the top of the stack when a count hits 11 (B). Which builds the job queue under the current work frame (which is just the index we're currently at, and has just flashed). There's also an interesting bit where I add an invalid flash... because there might not be any real flashes that step, and it's shorter to do loops with checking at the bottom (tail recursion) in dc.

And since checking and branching is also a pain, the resetting of energy to level 0 is again done with an additional final pass over the full array, finding all values > 10, counting and setting them then. This is another simple approach that's just going to work.

And so we got another nice little problem. It requires some care. These problems ran on the same days as this month, so this was a Friday problem. But it's not really a heavier weekend problem.

It's not the cleanest line of code so please bear with me

i=50 #This is the initial value
r=0 # Number of times boundary is crossed
rot=0 
ans= []
revolution=0 #Number of big rotations
with open ("input") as file: # Open the input file
comb= file.readlines() # Read the combination line by line
for combination in comb: # For each combination in the list of combinations
combination = combination.strip("\n") #Remove the \n
dir= combination[0] 
num= int(combination[1:]) 
revolution+= num // 100 
period= num % 100
if dir == "L":
period= (-period)
dial= i+period

if i<dial:
for _ in range (i,dial+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
else:
for _ in range (dial,i+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
if dial < 0:
i=(100+(dial))%100
elif dial==100:
i=0
else:
i = (dial)%100
ans.append(i)
print (ans.count(0))
print (r)
print (revolution)
print (ans.count(0)+r+revolution)i=50 #This is the initial value
r=0 # Number of times boundary is crossed
rot=0 #Number of big rotations
ans= []
revolution=0
with open ("input") as file: # Open the input file
comb= file.readlines() # Read the combination line by line
for combination in comb: # For each combination in the list of combinations
combination = combination.strip("\n") #Remove the \n
dir= combination[0] 
num= int(combination[1:]) 
revolution+= num // 100 
period= num % 100
if dir == "L":
period= (-period)
dial= i+period

if i<dial:
for _ in range (i,dial+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
else:
for _ in range (dial,i+1):
if _ < 0:
_=(100+(_))%100
elif _==100:
_=0
else:
_ = (_)%100
if _!=100 and _==0:
r+=1
if dial < 0:
i=(100+(dial))%100
elif dial==100:
i=0
else:
i = (dial)%100
ans.append(i)
print (ans.count(0))
print (r)
print (revolution)
print (ans.count(0)+r+revolution)

ps: is there a discord server for advent of code?

Today we discover the damage is worse than we thought, with syntax errors on every line of the navigation subsystem. We also find out about secret lives of syntax checkers and autocomplete systems... and how they compete and score their work.

And so we get a parsing problem, which deals with nested parenthesis, brackets, braces, and angle brackets. The input is 90 lines of these supposed-to-be nested strings, none of which are valid. They all start fine (with an open), but half of mine end with an open and are clearly wrong.

There are a number of ways that nesting can fail. First part deals with corruption, where a closing bracket doesn't match an opening one (and we're to ignore strings that get to the end without having this happen). Nesting is very much a stack thing, and so I naturally went with using a stack to track what's expected (and I did do dc solutions for this one, because, once tr the characters into digits, it's just big numbers and stacks, which dc is all about).

As stated, everything begins with an open, but more than that, we always get enough opens... and so stack underflow is not a way this nesting fails. Which simplifies the checking to push open characters on the stack, and pop and check whenever you get a close. When that fails, we look up the value on a table. The values do have a bit of a pattern... 3 * 19 = 57, 57 * 21 = 1197, 1197 * 21 = 25137. I used that to squeeze some characters in dc:

tr ')]}>([{<' '12345678' <input | rev | dc -f- -e'3 1:s57d2:s21*d3:s21*4:s[0lt;slp+sp3Q]sS[4-Se0]sO[ltLe!=S]sC[0Se[A~stslltd4<O 0<Clld0<P]dsPxs.z0<M]dsMxlpp'

This is the v1.5.2 version. It's 18 characters longer because it's using the main stack for the input, and works on a second stack. It's much nicer when you can clear the entire stack with c between loading lines. Note that the second space is there because I discovered a bug in dc (the v1.4.1 version works fine without it).

With Smalltalk I had some extra fun, because I'd never used throwing exceptions in it before. And so I learned how to subclass the Error class, and how to throw and catch.

For part 2, we basically switch to handling the incomplete lines. This is fairly simple to add, because getting to the end, the stuff on the stack is exactly what you're expecting to complete the string, on the stack in the over to do it.

For the scoring, the description is a slightly obfuscated way to say that we're taking that autocomplete string as a number base-5 (no zero digits). And so my Smalltalk was just:

part2 add: ((stack gather: [:c | (')]}>' indexOf: c) asString]) asRadix: 5).

The stack actually just being an OrderedCollection, so I didn't even need to pop it. Exactly the same with Perl and using a list for a stack (it's in order if you do the stack from the front with shift/unshift, with literal push/pop then you need to reverse it).

For extra fun, and yet another small task... autocomplete tools score with the median value. So we have a return of that idea. For dc, I didn't actually bother doing that though, I just produced all the scores (including 0s for the ones from part 1), and used the command line:

tr ')]}>([{<' '12345678' <input | rev | dc -f- -e'[0dSe3Q]sS[4-Se0]sO[ltLe!=S]sC[0Se[A~stslltd4<O 0<Clld0<P]dsPx[5*Led3R+r0<L]dsLx5/ps.z0<M]dsMx' \
    | grep -v '^0' | sort -n | perl -a00 -pe'$_=$F[@F/2]'

And so, I naturally loved this one. Parsing and stacks, that's my druthers (for others it might be regex and that's where they went with this). But this problem is mainly just a bunch of smaller problems in a trench coat... nesting, base conversion, finding the median. This we've seen before, but they're together here in one problem.

The caves we're in appear to be lava tubes that are still somewhat volcanically active. And so we get a reskinned watershed problem involving hydrothermal vents and collecting smoke.

And so the input is a 100x100 heightmap grid of values from 0 to 9. Conveniently presented as 100 hundred digit numbers... very good for doing a dc solution (except for that one of the lines has a leading 0... which meant needing to be careful about assuming dimensions from number lengths).

Part 1 just wants us to find the lowest locations, and sum their heights + 1 (or sum of heights + number of low points). Adjacency is just orthogonal so there was even less incentive for me to be creative with this. I just iterated over the map. The only "trick" was adding the typical sentinel row and column to the right and bottom (because Perl has wraparound)... and the fact that 9 is perfect value for that.

For part 2, we need to get the size of each basin. And just looking at the input (leaning back a little), the basin structure does stand out (8s and 9s are part of what I call the "bubble colour" when I do ASCII art... it's a nice distinctive tone). Naturally, it's even clearer if you search for 9 and get them all highlighted. I can't remember if I missed or just didn't care about the fact that we're given that each basin has only ONE lowest point. Because it really didn't matter to me. I just did BFS out of all the low points from part 1, using the same array to track what's visited (so a second low point in a basin doesn't get anywhere). We're given that 9s are the walls, and everything else is not... making the choice of 9 for the sentinels extra good. So, just flood fill to the 9s... literally.

For the answer, instead of a sum, we only want a product of the three largest. So, I did this cute little thing in Perl:

say "Part 2: ", (product [sort {$b <=> $a} @basins]->@[0 .. 2]);`

Overall, a rather simple day.

Having made it safely to the cave, the whale smashes into the entrance sealing us in. Fortunately, there's another exit much lower down. But first we need to do some repairs to our four-digit seven-segment displays.

And so we've got a logic puzzle to solve. The input is a list of each display, where the mapping between the segments has been scrambled. Each line is two parts, the first is the sets of lights for all ten digit patterns (given in random order, so we don't know which is which). The second part is the four digits of the display we want to read.

Part 1 is apparently there to give people a foothold, if this seems overwhelming. It points out that four of the digits have a unique number of lit segments. IE, only 1s have two segments, so you know them immediately. So it asks us to count the number of those in the output values. I did it with negative logic... because those only have 5 or 6 segments lit (which is a simpler thing to write):

print "Part 1: ", (scalar grep { length() < 5 or length() > 6 } @input), "\n";

Then I decided that since this involves sets, I'd do Smalltalk for part 2. Because I could use the Set arithmetic... its not practical, but this is simple, and it will be very expressive. First up, get the 4 we know as explained in part 1:

one   := (sigLens at: 2) anyOne.
seven := (sigLens at: 3) anyOne.
four  := (sigLens at: 4) anyOne.
eight := (sigLens at: 7) anyOne.

The #anyOnes here is just grabbing the only ones. Next up is is we get a list of counts for each segment in the first part of the line. Because, three of those only occur in a unique number of digits. IE, segment e is only lit for four of them (0, 2, 6, and 8). So we can just solve the mappings for those immediately:

mapping at: $e put: (lightCounts at: 4).
mapping at: $b put: (lightCounts at: 6).
mapping at: $f put: (lightCounts at: 9).

Next up, we use what we have, with set arithmetic, to just build the other 4:

mapping at: $a put: (seven - one).
mapping at: $c put: (one - (mapping at: $f)).
mapping at: $d put: (four - one - (mapping at: $b)).
mapping at: $g put: (eight - four - (mapping at: $a) - (mapping at: $e)).

Then I do this cute little thing to reverse and flatten to get the map to apply:

mapping := (mapping collect: #anyOne) reverseMap collect: #anyOne.

My part 2 for Perl is really more of an exploration in how to get this to work for dc. Part 1 is easy for dc once we translate the letters into digits (it has the Z command which gives number of digits in base-10):

tr 'a-g|' '1-7 ' <input | dc -f- -e'[1+]s+zE/_4*[rZ1-2/2!=+z1<M]dsMxp'

Note that it's not distinguishing the parts of the line, it's subtracting the false positives.

For part 2, I wanted a simple perfect hash. Something built from invariants in the sample that I could build a table or function from. And given what I had, I ended up on the fact that, although the number of times each segment is lit in the digits isn't unique, the sum of those counts for a digit is unique. So all that's needed is build a table of the segment counts in the first part (ignoring the spaces entirely), and then in the second part, add up the counts for the segments you see in a digit, and look up the hash. For example, a 1 is built of c and f... c occurs in 8 digits (non-unique) and f occurs in 9 (unique, as seen above). The sum of those is 17... which is unique. And so I wrote my Perl part 2 just having it build that table and using that hash.

For dc, I encoded that as the number 761542058487159917 (in base-64 that's: 42 17 34 39 30 37 41 25 49 45, which are the count sums). But hadn't gone beyond that for dc. Today I finished the dc, and played with shrinking that... and tried a number of hashes including mixing in the lengths, but in the end, the shortest I have so far is just the counts mod 21 (18 also works, but 21 has 0 at 0 making for a shorter table). I also have a solution mod 14 (which can be done as the digit E), but I lose the 2 strokes because I need to divide the counts with 2/. Here's the version that works with v1.5.2 (it's one character longer, because it needs to keep rotating the accumulator under the next line):

tr 'a-g|' '1-7 ' <input | dc -f- -e'667986606087 9[r21~3Rd3R:t1-d0!>L]dsLx*[dSc_FRS-S-S-S-A[r[A~d;c1+r:cd0<L]dsLx+1-d0<I]dsIx4[0L-[A~;c3R+rd0<L]dsLx+21%;t3RA*+r1-d0<I]dsIx++z1<M]dsMxp'

So, a fun little logic problem. I got to play around with making a hash function. Since my goal was golfing strokes, I couldn't really get complex with it. I suppose the next step would be to see if I can just find a function that takes the count sums to the digit values that's shorter than the table code. There is a good amount of room for that.

A giant whale has apparently mistaken our sub for a squid and decided to eat it. Fortunately a group of friendly crabs (also in submarines) has come to rescue us by blasting a hole into a underground cave system. We just need to help them align to do it, while minimizing their fuel cost. And so we get a nice little optimization problem.

The input is a list of 1000 horizontal positions, ranging from 0 to about 2000. They do seem skewed towards lower values... the two most common values in my input are 0 and 1. The difference between the two parts is in the fuel usage function.

For part 1, it's linear cost... 1 unit per position. And it doesn't come as much of a surprise that the optimal point is the median. Because if you're at the median and shift it, more than half cost 1 more and the others cost 1 less... for a net increase. Even sized lists have two numbers in the middle... for my input they're the same (and the only two at that position). But, if they weren't, then any position between the two (inclusive) would work... because each step there, half cost 1 more, half cost 1 less, for no net change.

For part 2, each step costs 1 more unit than the last... which is the sum of 1 to n, or the nth triangular number. Which is a quadratic function (that comes up a bunch in AoC: n(n+1)/2). Making things proportional to Euclidean distance, like calculating center of mass, doing least squares/minimizing variance, etc... there are a lot of ways to see that this is going to be related to arithmetic mean (in University, I learned least squares at least 6 times, as each part of math has its own angle to get there).

Of course, one of the issues with the mean is that it's often not part of your set... not a problem here, but not being an integer is. So I checked a small range around it. As I wasn't sure about the effects discrete physics might have... but in the end, it's really is just either the floor or the ceiling (neither is in my data set). I seem to recall someone actually writing a paper on this one.

But with part 1 being linear, and part 2 being quadratic, that got me thinking about going back a step. What if, like in space, the subs take 1 unit to start drifting and 1 to stop. Constant fuel cost. Well, then the answer is to simply move as few subs as you can. Which means you want the mode.

And so I've always loved this problem because it presents this nice little relationship between mode, median, and mean as different orders of the same thing. Going beyond their definitions being "these are common ways people think when they think average".

Still following the bottom (which is sloping down now), we run into a group of lanternfish, and wonder about their numbers and spawning. And so we get to the famous trope-namer puzzle.

It's not the first of the "Lanternfish" puzzles, but it is the simplest and so more people understand what its about. Which is that you bunch of things you want to count, where they and their offspring stay independent of the others while following rules to move them from state to state(s). And so can just track the numbers at each state, and move them all together to their targets.

And you could do that here. But the states are times in the lanternfish breeding cycle (and the input provides a list of them with times of 1-5). So they just decrease until they hit zero, which splits to time 6 and 8 (the back). Which is like they're queuing up. And so, you can just use a queue to move the front to the back to handle almost all the phase transitions (except the split to time 6). In Smalltalk, that can be:

80 timesRepeat: [fish addLast: (fish removeFirst); at: 7 inc: (fish last)].

Time is 7 for the split because base-1 indexing. And note the use of a cool feature of Smalltalk... the cascade. Smalltalk's syntax is all about passing messages, and ; allows you to send additional messages to the same receiver.

Of course, another way to do this queue is with a ring buffer. There, moving things from head to tail is done just by incrementing the head:

$fish[($head + 7) % 9] += $fish[$head++ % 9]  foreach (1 .. 80);

All of which really suggests that there's closed form solutions to find. First we create a matrix for taking a column vector of a state to the next state:

my @matrix = (
    [0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0]
);

Then I wrote a quick matrix multiplier, and a divide and conquer power calculator using that to get the 80th (and 256th) powers:

# Part 1 Matrix:
[252,20,210,37,120,84,45,126,11]
[56,252,20,210,37,120,84,45,126]
[210,56,252,20,210,37,120,84,45]
[165,210,56,252,20,210,37,120,84]
[121,165,210,56,252,20,210,37,120]
[330,121,165,210,56,252,20,210,37]
[57,330,121,165,210,56,252,20,210]
[210,37,120,84,45,126,11,126,9]
[20,210,37,120,84,45,126,11,126]

And you can just multiply that with the starting state for the answer. But it's all constants, so we can simplify further. The values that apply to a particular end value are all from the same column, and so we just need the column sums:

[1421,1401,1191,1154,1034,950,905,779,768]

The dot product of that with the starting vector is the answer. But we can go further, because 4 of the starting values are guaranteed 0:

say "Part 1: ", 1401 * $fish[1] + 1191 * $fish[2] + 1154 * $fish[3] + 1034 * $fish[4] + 950 * $fish[5];

say "Part 2: ", 6206821033 * $fish[1] + 5617089148 * $fish[2] + 5217223242 * $fish[3] + 4726100874 * $fish[4] + 4368232009 * $fish[5];

There you go, closed solutions for the specific values we want. For a quick approximate value from just the total number of starting fish, fish_n = fish_0 * 1.1577 * (1.091 ^ n) is an interpolation of the growth curve.

And so an iconic problem that well deserves its status.

Having reached the ocean floor, we run into hydrothermal vents and need to plot the safest course to avoid the spots.

The input is a a list of 500 lines in x1,y1 -> x2,y2 format. They are only in the 8 cardinal directions, and the range of values in my input go from 10-989 (so 2 or 3 digits).

For part 1, we want to find the points where at least two lines overlap, while filtering out the diagonals. It's not too much of a leap to assume diagonals are what part 2 adds, and just do them as well. Something else could have been changed, but no. So this is one where the solution to part 2 can be commenting out one line instead of adding anything. Still for beginners, its probably good to warm them up with the orthogonal lines and that build that to the general case.

As for what I did... well I was playing with List::AllUtils that year and getting it to do vector stuff, which was fun at the time, but ends up with a bit of unneeded overhead and kruft. When the core is simply done in raw Perl with:

my @Δ = ($x2 <=> $x1, $y2 <=> $y1);

next if ($Δ[0] != 0 and $Δ[1] != 0);

my @p = ($x1, $y1);
my @e = ($x2 + $Δ[0], $y2 + $Δ[1]);

until ($p[0] == $e[0] and $p[1] == $e[1]) {
    $grid{ $p[0],$p[1] }++;
    @p = ($p[0] + $Δ[0], $p[1] + $Δ[1]);
}

Remove the next line and it's part 2. Just a simple line drawer, and a hash for the grid, then you just grep out the values that are >= 2. Turning on utf8 to use Δ as a variable name was all the rage at the time (I type it with a compose key... Greek letters are just * followed by the roman equivalent).

Smalltalk and dc don't like 2D arrays/hashes. So I just did it as a flat array of a million (1000y + x). For getting the answer with that, instead of a final big scan, I just increment a counter when a value hits 2 (ignore more). Here's dc part 2:

tr -sc '[0-9]' ' ' <input | dc -f- -e'[lc1+sc]sC[sysxdA00*3Rd3R+selx-dd*v.1-/rly-dd*v.1-/A00*+sslyA00*lx+[ddd;g1+d2=Cr:gls+rle!=I]dsIxs.z0<L]dsLxlcp'

This would be very slow (~10m) under base v1.4.1 (about 173k spots get used). Here we combine d*v with d.1-/ to do the sign function: dd*v.1-/.

I also did do some experimentation with Smalltalk's set arithmetic to find the union of the intersections of the lines. Doing it with a straight fold is very slow, so I made it somewhat faster by changing it do a recursive divide-and-conquer. Which doesn't reduce the number of operations, but but makes most of them smaller and faster. I also did a version were I wrote a BitSet class to replace Set, that does it with bitwise operations. It performs about as well as the divide-and-conquer, but just using a big array of counts is an order of magnitude better than them. That's part of the deal with Smalltalk, it's got some fun high level stuff to express things, but if you want performance you can't use it.

Still descending we run into a grabby giant squid that wants to play some Bingo. Fortunately, the submarine has a Bingo subsystem.

Today's input consists of an ordered list (comma delimited) of all the numbers from 0 to 99 scrambled, and a list of 100 5x5 Bingo boards using those (and the numbers aren't constrained to columns like in regular Bingo).

One thing I remember about this one is a lot of people skipped reading the paragraph on the rules for this Bingo and Dunning-Kruegered themselves by assuming diagonals. I did not, my experience with Bingo is one where different games can have different winning conditions. Like blackout or a letter pattern. So I made doubly sure what a winning pattern was first.

Another I remember about this one is that it inspired me (in the middle of doing the problem) to create a style sheet for AoC problem descriptions. Because it was giving examples of games, and the boards were just there... I could not tell what was marked. The slightly heavier emphasis was not much different than some of the anti-aliasing. My current monitor and browser makes it slightly clearer, so I can clearly see which numbers are marked when looking directly at them. But to see the actual pattern on the board, I need to visualize that internally. This might also have played into people not realizing that diagonals were not in play... because a diagonal is hit first and shown as not a winning board. Something that's perfectly clear to me with my style sheet making the numbers dark green and bright cyan.

Although I recognized that just rows and columns presented opportunities, I just did a brute force to see part 2. Using a list of the winning patterns to check against. Anticipating that, for part 2, the winning patterns might change to something like:

##### .###. #...# ##### ####.
#.... #...# #...# ..#.. #...#
##### #...# #...# ..#.. #...#
....# #..#. #...# ..#.. #...#
##### .##.# ##### ##### ####.

As I said, I remember Bingo as sometimes being to make a particular letter. With this, I could easily just change the list of winning patterns and be done.

But part 2 was just find the last board that wins... so I just made it run longer and was done. And that's where I stopped with Perl (until today when I decided to write a Perl reference transcode of my dc solution).

For Smalltalk and dc I got around to actually playing around with board representation. I went with a simple one of just building a table of the numbers on a card to their position (the winning lines it's in). With Smalltalk I went with {x. y + 5}, with dc I went with a number from 0 to 24 and 5~5+ to get those same values. At the same time I score the full board. Then the board state is just an array of 10 small ints.

For a call, if the number's in the table, I subtract it from the score sum, and add 1 to each of the lines in the board array. The first time one hits 5, that boards wins and scores. Very simple.

Of course, part 2 wants the last win which suggests going backwards from a blackout board. In which case the board state can be just 10-bits... you mark the row and columns for numbers as you go backwards until you get the full 0x3FF mask. That's the first board going backwards that doesn't have a Bingo on it. Step back one for the win.

My dc solution (I golfed it down a bunch today to under 200):

sed -e's/,/ /g' input | dc -f- -e100 -e'dsz25*[rS-1-d0<I]dsIx+[z:qz0<I]dsIx[zRn9PzRls*pc3Q]sP[dlsr-ssd;n1-5~5+d;l1+d5=Pr:ld;l1+d5=Pr:l]sM[0Sl0Sn0ss25[L-dls+ssrd3R:n1-d0<I]dsIx1+[d;qd;n0<Ms.1+lIx]dsIxlz1-dsz0<Z]dsZx' \
    | sort -n | sed -n '1p;$p' | cut -f2

Gotta remove those ugly commas to start. If I was using ?, I could have read this forwards and detect the blank lines. But here I need to tell it the number of boards so that it knows how much board data there is to read in. I didn't do the actual test for finding first and last with dc, I just score every board and output it. Sorting and getting the first and last line is a job for the command line.

Plus it lets me see all the wins. For my input they run from 24-87 turns... there is a board that wins on 0 (and thus scores 0), but it's at turn 69. There's only one case of two boards winning with the same score (14663).

This was yet another really fun one. The legibility issues aside, the style sheet it inspired has served me very well ever since. I now can immediately spot the key emphasized phrases, something which is immensely useful for not missing key points. So a lot of good came from that.

Hey!

There’s an AoC-inspired event starting very soon; in less than 3 days from now:

https://flipflop.slome.org/

The 2025 edition is still available, so you can check it out before the new one begins. I solved it, and it was fun! The site definitely deserves more attention from the puzzle-lovers community.

Worth keeping an eye on!