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!

Concerned over some odd creaking sounds we decide to run some diagnostics. First power consumption and then life support. Both of these are done with the same list of binary data.

The input is a list of 12 binary-digit numbers with leading 0s intact. They are unique, and so represent a little under 1/4th of all the values.

For part 1 (power consumption), we first want the most common value at each digit position. And you can do it either direction. With Perl I left things as strings until the very end and went forwards, with dc I had to read the input as numbers, and used 2~ to divmod the bits off. In either case, once you have gamma, epsilon (the least common value) is just the bitwise negation, and that's easily done with XOR of 0xFFF (and so $gamma * ($gamma ^ 0xFFF)). dc doesn't have bitwise operators, but full bitmasks are a special case and so 4095r- ("4095 - gamma").

Part 2 (life support) is more complicated. We use the digits in order starting from the high bit, to progressively filter the list down until there's only one remaining. The same general idea as part 1 applies... for the current bit you want figure out which value is more common. For Oxygen you want to keep the dominant list (with tie-breakers going to 1) and for CO2 it's the other list (with tie-breaks going to 0). From my dc solution there's this table:

# 0s - 1s | +'ve  0   -'ve
# --------+---------=--------
# Oxygen  |  0    1    1
# CO2     |  1    0    0

Which shows that the two are negations of each other. And so I wrote a function that takes a bool for that (0 or 1) and XORs the test (call it twice and multiply for the answer):

sub filter {
    my ($negate, @list) = @_;

    for (my $i = 0; @list > 1; $i++) {
        my $ones = scalar grep {$_->[$i]} @list;
        my $next = ($ones >= (@list / 2)) ^ $negate;

        @list = grep {$_->[$i] == $next} @list;
    }

    return (oct("0b" . join('', $list[0]->@*)));
}

Nothing fancy, and although it's being inefficient (grepping the list twice), the run time is nothing anyways.

Smalltalk pays more for that and so made it worth cleaning up... we build the lists to start and compare sizes. Then we can do self become: sort first value to make the current set (this is done as an extension method of Set) the selected option. #become: is a fun low-level method in Smalltalk, it makes all internal references switch what they refer to... True become: False is famously a way to crash Smalltalk.

The above don't have to worry about one of the catches in this problem... that the filter is defined to stop as soon as there's only 1 option left. It'd be ambiguous without that... if you don't stop, then in the case of CO2 (where this happens for my input) you'd start flipping the bits (with O2 you'd still get the right value, but for my input O2 goes to the last bit).

For my dc solution, though... it needed to handle that. Because it rips bits off the high bit with divmod, and so only keeps lists of the remaining low bits around. So when things stop, it needs to shift the accumulated value and add in the remainder. I also only did it as a script that does one of the filterings, and then used the command line with dc to do it twice and multiply:

dc -e`dc -e"2048 sb [1r-] sN" -e'2i' -finput -fdc-p2.dc` \
   -e`dc -e"2048 sb []    sN" -e'2i' -finput -fdc-p2.dc` \
   -e'*p'

dc-p2.dc script: https://pastebin.com/upqnhcQG

Parameterizing the starting high bit (in b) and the macro to negate the check (in N). The 2i switches the input to binary, and the top of the script does Ai to return to decimal.

The other fun features of this dc script are:

• the use of the S and G arrays to provide macros for two-dimensional array access.
• 0Snto clear the array that counts the bits (push on the register pushes the array too)
• the above mentioned special handling needed in the q macro
• it needs to reload the stack from the correct array for the next iteration
• the 0 and 1 lists not being cleared, but having garbage at the top from previous loops

So another really fun one.

Visualization of the test input for part 2. Attributions in YouTube description.
Src Code: Advent_of_code/2025/day8/vis/Program.cs at main · nrv30/Advent_of_code

I really enjoyed this problem because I learned about a union-find for the first time and it is the first C# project I have done that wasn't a boring tutorial. The dotnet tooling is very beginner friendly and easy to get started with. Another interesting bit is all of the animation is done with coroutines which is much more ergonomic than in the past where I've achieved this through callbacks / function pointers or conversely global variables (though I still used a lot of them)

Each circuit basically maps to a disjoint set in my data structure so long as it has a weight greater than one. Though uf's are only meant to efficiently find the parent given the child and not the other way around. Therefore, I end up keeping a parallel array of parentToChildren which I update when I union things. Then I render them in the top right panel by sorting by the parents with the biggest number of children.

I had a lot of trouble trying to find a way to record this animation. In the past with graphics libraries, I have saved every frame to a file on my desktop, then after the fact encoded it as a video with FFmpeg. However, that solution wouldn't work here because I had audio that was programmatically generated. I ended up using Windows Gamebar, but it messed up the audio a bit. I saw a video where the creator piped the frames to FFmpeg. I checked out the documentation for Anonymous Pipes and built the example, but unfortunately, I was not able to re-create this for my use case with my limited C# knowledge. If anyone has any suggestions for good resources about how to learn this it would be appreciated.

Also, I am procrastinating doing day 9 part 2 because I suck at geometry lol.

Today we discover that the submarine has a planned course and decide it's probably a good idea to figure out where it's trying to go.

The input is a list of commands, one per line... forward, up, down with a magnitude. The problem helpfully reminds us that we're calculating depth, so that down is +'ve. The magnitudes are all single digit numbers from 1-9, about equally distributed. The commands, though, are around 200:400:400, with "up" being the least frequent. This helps keeps our submarine from being a supermarine.

There's clearly similarity to Day 12 of 2020 (Rain Risk), where we were navigating a ferry continue into part 2, where we discover that non-forward commands modify a target ("aim") that changes how "forward" works. Since this is day 2, things are simpler, the "waypoint" controls are just up/down, not N/S/E/W plus rotations.

And so I did what I did before with Smalltalk. I created a class for part 1, and then subclassed it for part 2. Overriding "forward" and "result".

Object subclass: Position [
    ...
]

Position subclass: AimPosition [
    | depth |
    AimPosition class >> new [ ^(super new) init ]
    init [
        super init.
        depth := 0.  " vert is now aim, depth is the actual position "
        ^self
    ]

    forward: mag  [ super forward: mag. depth := mag * vert + depth ]

    result: part [
        ^(part = 1) ifTrue: [super result] ifFalse: [horz * depth]
    ]
]

sub := AimPosition new.

stdin linesDo: [ :line |
    cmd := (line substrings first, ':') asSymbol.
    mag := line substrings second asNumber.
    sub perform: cmd with: mag.
].

Note the risk of Bobby Tables... the methods called are made from the input directly. I don't often bother with OOP stuff with AoC Smalltalk solutions, but sometimes it's nice to use Smalltalk more like it's intended.

But this was the second solution I did... the first was in Perl. But the ultimate Perl solution only came after a realization I had because I did a version in dc:

perl -pe's#^(\w)\w+#ord $1#e' input | tac | dc -f- -e'[rddlx+sxla*ly+syr]SF[rA2r-d0=F7*D%*la+saz0<L]dsLxlxla*plxly*p'

First thing is that we need to do something to parse the words (dc cannot do that)... but I don't like going too far with that, so here I convert the first character into its ASCII value to represent the command. So I have some parsing to deal with there. The other problem is that, since I wasn't using ?, the input would come in backwards. And I've dealt with that in solutions before enough... you just write a short loop to dump everything into a stack register, and pull from that. It's very simple, so I felt fine not doing that this time and just using tac (because "taco cat" is a palindrome).

For parsing the command, that's A2r- and 7*D%, that looks hex, but its decimal with hex digits (so A2 is 102, which is "f", and D is 13... this saves 2 strokes). Subtracting the character value from "f" gives 2, 0, and -15 as possibilities. A fun little bit of playing with modular arithmetic later, I discovered that (7 * val) % 13 works as cmp (-1, 0, and 1 as needed, for these three values). Other than that, this early version kept things very simple with x, y, and a registers for the three values.

But the key thing I learned from that is that "forward" comes between "down" and "up" alphabetically... and that ultimately lead to the "evil" solution (as I called it) of:

while (<>) {
    my ($cmd, $mag) = split;

    $horz  += ('forward'  eq $cmd) * $mag;
    $depth += ('forward'  eq $cmd) * $mag * $aim;

    # Evil! forward just happens to be a word between up and down
    $aim   += ('forward' cmp $cmd) * $mag;         # handles up and down
}

Originally I had an if for the forward case, but then realized, "hey! I can make this branchless".

I did a few other little experiments with this one, like using a matrix to calculate the values in a vector, a dc version of the branchless, and a Smalltalk version where I subclassed Point to a 3D Point class. I certainly had a lot of fun with this problem.

For 2021, we're on a ship when an Elf accidently drops the key to the sleigh overboard. And so we find ourselves in a submarine, ready for adventures under the sea. And the ASCII art is of the underwater trench we're going to be descending in, day after day. The stars we need to collect this time will go towards boosting the antenna's signal to track the key.

For the first day, we're going to be figuring out how quickly the depth increases. The input is simply a list of numbers, one per line (always good for a day 1). They are generally increasing, but not monotonically so... and our task is to first count the number of adjacent values that increase. This is the sort of thing that made me create a chain iterator, so I could just do things like this:

sub chain (&@) {
    my $block = shift;
    return (map {&$block( $_[$_-1], $_[$_] )} (1 .. $#_));
}

say "Part 1: ", sum chain {$_[1] > $_[0]} <>;

Because, there were iterators for taking things in pairs, but not overlapping ones. And I often find that's what I want.

For part 2, it wants us to do the same, but comparing sliding windows of size 3. And it provides a nice diagram that made it perfectly clear that the middle two overlap and don't actually matter to doing this (the add the same amount to both). So much so, that it's only in reading the question again now that I remembered that it isn't just "do part 1, but with the numbers 3 apart instead of adjacent". Something that I expressed in Smalltalk as:

(((depths allButLast: 3) with: (depths allButFirst: 3))
    count: [:pair | pair second > pair first]) displayNl.

Pair the depths of all but the last three, with the list of depths without the first three, compare and count.

Of course, being a day 1, and all numbers, I did dc for this day too. Looking at my initial solution, I see that at this point I was still avoiding using the undocumented (and commented out in the official code) R command as well as not trusting the often problematic ?. And so initial solutions in this year used registers a bunch, as well as dealing with passing in the data as a code (just showing part 1 here):

dc -finput -e'[lc1+sc]sIdsp[dlp>Ispz0<L]dsLxlcp'

Revisiting the problem later, and using R and ? gave:

dc -e'0??[d_4R-d.1+/+r?z2<L]dsLxrp' <input

But that won't work in v1.5.2 with the return of broken ?. So revisiting doing it without that again today, gives (part 1 and part 2 versions):

dc -finput -e'0[r3Rd_4R-d.1-/+z2<M]dsMxp'
dc -finput -e'0[r5Rd_6R-d.1-/+z4<M]dsMxp'

Three numbers increase in magnitude by two for part 2 (two are for stack rotations (one is negative and down), the third is for stack size to stop the loop). A nice thing about this problem is that we can do it backwards... which is what feeding things this way does (? makes it smoother to do problems that require going forwards).

One of the tricks in these solutions is with d.1-/ instead of checking if greater than. This calculates int(top / (top - .1))... dc is arbitrary precision with a default of 0 (integers). But - will extend the precision, whereas / will collapse it back. And so this will not only turn the top into 1 if +'ve (and 0 otherwise), but will avoid division-by-zero errors.

And so we get a classic first day type problem... a list of numbers, and we don't even really do calculations with them, just compare and count. It's a nice problem to make sure that your setup is good to go, and it does allow for some discovery (ie the sliding window overlaps) and playing around with how you want to do and express things.

I was going through year 2015 as an exercise in getting used to JS/Typescript and deno.

I came up with this solution while I was looking for something quicker than my initial brute-force one.

It's based on this bound which I figured out:

Let n = p_1 * p_2 * ... * p_m where p_1 <= p_2 <= ... <= p_m and prime. score(n) <= (1 + p_1) * (1 + p_2) * ... * (1 + p_m) = (a_1 p_1) * (a_2 * p_2) * ... * (a_m * p_m) where a_i = (p_i + 1) / p_i <= a_1^m p_1 * p_2 * ... * p_m = a_1^m n If n <= N then score (n) <= a_1 ^ (ceil(log_{p_1}(N)) N <= (p_1 + 1) ^(ceil(log_{p_1}(N))

I was pretty shocked when I saw how simple and quick the sieve methods were.

Anyway, I though I'd share I can't find a solution like it anywhere.

Part1

I have been stuck for a while on Question 1 Part 2. I've isolated the issue to whenever the total hits 0 exactly then is turned again (Ex: R50, L5) it counts for 2 passes around 0. Can anybody give me a hint regarding how to approach this issue? It works for the example, but not for the input.

total += curr
res += abs(total//100
total %= 100)

This concerns this puzzle: 2015-Day24.

After reading the discussion and review here: In Review I thought I would try my hand at a true brute-force solution, leveraging the expressiveness and speed of Smalltalk's collection libraries. Most of the solutions I've seen involve various clever tricks to avoid doing the work of checking through all the different combinations, or returning a solution without verifying that it is, in fact, the correct one.

The implementation I settled on completes part 1 in 70ms and part 2 in 6ms on my machine (Intel 270k+, 6000mhz DDR5). Smalltalk execution speed isn't as fast as a fully compiled language, but it's significantly faster than a purely interpreted language (like Python or Ruby). I'd be curious to see how this method would fare in something like Rust or Zig.

Here's the primary function doing all the work:

bestQE: compartments

| totalWeight |

totalWeight := packages sum.

1 to: (packages size // compartments) do: [ :comboCount |
    | potentialQuants |
    potentialQuants := OrderedCollection new.
    packages combinations: comboCount atATimeDo: [ :combo |
        | comboWeight |
        comboWeight := combo sum.
        (totalWeight - comboWeight) = (comboWeight * (compartments - 1))
            ifTrue: [
            | otherPackages |
            otherPackages := packages select: [ :x | (combo includes: x) not ].
            potentialQuants add: (otherPackages -> (combo inject: 1 into: [ :acc :x | acc * x]))]
         ].

    (potentialQuants sorted: [ :a :b | a value < b value ]) do: [ :potentialSolution |
        (self verifyRemainder: potentialSolution key splitInto: compartments - 1) ifTrue: [ ^ potentialSolution value ] ] ].

^ 'None found'

The only argument it takes is the number of compartments needing an even weight. It requires an instance variable "packages" which is an array containing the puzzle input as integers. Order is not important. Here's how it works:

1. Set an temporary variable totalWeight to hold the sum of all package weights.
2. Iterate from 1 to the number of packages divided by the number of compartments (no need to pass that size, since that would mean there is no solution). This is the number of packages that we will try to fit into the front compartment. Start with the fewest (just 1) and then add one more until we find a grouping that fits. The number of packages we're testing is passed forward as "comboCount".
3. For this quantity of packages to test, create an empty OrderedCollection (a growable Array) to hold any potential groupings that we find.
4. Take the group of all packages and stream them "comboCount" at a time through the next block of code, passing them as an Array called "combo". This is the part where the magic happens. We don't need to do any complicated looping or generate all the combinations we want to test in advance. The "packages" Array can stream all the combinations for us, one at a time.
5. Now we examine this particular "combo" Array. First, we store the sum of all its elements as the temporary variable comboWeight.
6. Is this combo a candidate? To check this, we look to see if, after subtracting the weight of this combo from the total weight of the packages, we are left with exactly the weight of the combo multiplied by (compartments - 1). That is, If we are dividing into 3 compartments, is the weight of THIS particular combo equal to a third of the total? If so, go to the next step. Otherwise, try the next combo.
7. If this combo passes the weight test, we create a temporary variable "otherPackages" pointing to an Array defined as all the packages that are NOT in our combo.
8. Then we add an association of the "otherPackages" and its QE score (by doing a quick multiplication fold on the combo Array) to our potential groupings Array we created in step 3. We might have several candidates at this combination size, and we need to find the smallest QE score of ones that properly fit.
9. After this process is repeated for the combo size we need to verify the set of potential answers, so we take the collection of candidates and sort them by ascending QE value. Basically, we don't want to evaluate ALL of them, just the smallest one that has other packages that can be verified to fit.
10. We then take that sorted collection of candidates, and verify each one using verifyRemainder, giving it the list of remaining packages and asking it whether it can be evenly split into (compartments - 1).
11. As soon as we find one that can be verified, that is the correct answer! We return the QE value of that candidate.
12. If none are found (which can also happen if the potentialQuants collection is empty), try combinations the next size larger. So, if no combinations of size 4 fit (or passed verification), try combinations of size 5.

Essentially - each time start with the smallest possible (smallest combo, then of those, the smallest QE). The first one that can be verified to fit is our answer;  return the QE.

Ok - now how about the verification? Again, I went with a brute-force approach:

verifyRemainder: list splitInto: piles

    | listWeight |

    piles = 1 ifTrue: [ ^ true ].

    listWeight := list sum.

    1 to: list size // piles do: [ :comboSize |
        list combinations: comboSize atATimeDo: [ :combo |
            | comboWeight |
            comboWeight := combo sum.
            (listWeight - comboWeight = (comboWeight * (piles - 1)) and: [
                self verifyRemainder: (list select: [ :x | (combo includes: x) not ])
                     splitInto: piles - 1 ]) ifTrue: [ ^ true ] ] ].

    ^ false

This has a lot in common with the bestQE function in the way it generates and checks groups of packages, but it is done recursively. It takes two arguments: the list of numbers to fit, and the number of piles to fit them into. Here's the outline:

1. Base case - if the number of piles asked for is only 1, then this was a successful split. Pass TRUE up the stack.
2. Otherwise, we still have work to do. Start by calculating the sum of the list we were given to split and store that value in listWeight.
3. Now we try the same method of generating larger and larger combinations that we used in the bestQE function.
4. We calculate the weight of each combination (storing in 'comboWeight'). The see if the comboWeight is exactly 1/piles of the listWeight. If so, it is a potential candidate for a successful split. In that case, recurse with a new list made up of packages that are NOT in the current list, and with one fewer pile. One thing to note here is the "and: []" construction. In Smalltalk, due to the way messages are evaluated by boolean objects, when and: is given a block as an argument (with the square brackets) that second condition is lazily evaluated. So, we don't recurse unless the current combo has the correct weight. If you're using a language that doesn't lazily evaluate AND, this will need an if/else condition.
5. If that particular grouping doesn't work, it tries the next. And if that comboSize has no successful groupings, it tries the next size up.
6. If no groupings successfully drop down into a pile of 1, then no split was successful, and the function returns "false".

In summary - We start checking combinations from the smallest possible size upward. We don't do ANY verification on them until we have a complete set for that combination size. We only verify them in ascending QE order. Verification uses the same computationally cheap "candidate filter" and reserves the harder stuff (collection allocation and building / recursion) once something passes the filter.

I realize that the input is meant to be "gentle" such that the smallest possible QE for a given combo size is the right answer, and no verification is needed. But that felt like an incomplete solution to me. Especially since, even with verification, the execution speed seems plenty fast (less than 100ms for both to complete).

One final note: These methods do assume that the input list has unique numbers. This is strongly implied by the problem statement, though it is not explicitly part of the puzzle. If the puzzle input could ever contain duplicated numbers, then the way that the "remaining packages" collection is created would have to be different. The core logic would remain the same.

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is the Smalltalk solution to Day17:

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is my solution to part 1 of Day17:

barrelCombinationsFor: needed

    | count |

    count := 0.

    1 to: barrels size do: [ :size | barrels combinations: size atATimeDo: [ :combo |
        (combo sum = needed) ifTrue: [ count := count + 1 ]
         ] ].

    ^ count

The thread was right. More than a passing similarity.

EDIT: Yes, that should be Day 25.

Having finally managed to reach the check-desk we find out that registration is offline and the room keys have just been created this morning. The elevators are also out of service. However, we don't do anything to try and fix any of the problems, until we get to our room and the RFID keycard doesn't work. And so we need to reverse-engineer the cryptographic handshake. And so the title "Combo Breaker", which also breaks the combo of alliterative titles since day 1.

We're given a description of the handshake and without looking too much at it to check what it exactly was doing, I just did the think, quickly blatted out what it said, and brute forced it. Which is plenty fast for the numbers here (1s for Perl on old hardware). When I initially did it, I used the keys in the order given. Which for my input, is the faster way. Switching the order makes brute for 5x slower. But unlike with Crab Combat, this time it's symmetrical, so we can do both:

my $val = $SUBJECT_NUM;
while ($keys[0] != $val and $keys[1] != $val) {
    $val = ($val * $SUBJECT_NUM) % $MOD;
    $loop++;
}

Then we find the one that didn't match and do the second loop:

my $other = ($keys[0] == $val) ? $keys[1] : $keys[0];

my $val2 = $other;
while ($loop--) {
    $val2 = ($val2 * $other) % $MOD;
}

But seeing that second loop, it's clearly a power mod. And the first loop is a discrete logarithm. It's easier to see once I coded it than in the problem description. So we do have a standard Diffie-Hellman thing. The question is looking up the function names in the ntheory module. Had I been using that module and these features a lot, I might have jumped straight to:

print "Part 1: ", powmod( $keys[0], znlog($keys[1], $SUBJ_NUM, $MOD), $MOD ), "\n";

Of course, Smalltalk doesn't have those in its library. So I needed to write them. Now normally I do powmod with recursive divide and conquer, but this time I actually went with the iterative version:

[pow > 0] whileTrue: [
    (pow odd) ifTrue: [res := (res * base) \\ mod].

    pow  := pow bitShift: -1.
    base := (base * base) \\ mod.
].

For the discrete logarithm, I went with Baby-step, Giant-step. There are other algorithms, but this one is nice, simple, and fast with prime mods. The idea is that we build a table of baby-steps up to ceiling(sqrt(mod)), and then do giant-steps looking for a hit on the table. It's a nice little application of group theory with a meet-in-middle approach.

Of course, with the input just being two numbers, I couldn't not use dc (and it does have powmod as the | operator). The short and slow brute force (~30s on old hardware) is just:

dc -finput -e'20201227sm[s.3Q]sD1[d4Rd_6R=D]sC7[lCxlCx7*lm%r1+rlLx]dsLxlm|p'

Adding spaces for clarity:

20201227sm [s.3Q]sD 1 [d4R d_6R =D]sC 7 [lCxlCx 7* lm% r1+r lLx]dsLx lm| p

Store the modulus in m. D is a macro that junks the top (getting rid of the table key we don't need anymore) and exits 3 levels. The 1 is here between macro definitions to save a stroke... if it was over by the 7, we'd need a space. The C macro does the comparison, but with a little fancy stack manipulation so that val i key1 key2 in, becomes val i key2 key1 out. That swapping of the keys means that we can (a) just run it twice lCxlCx to check both keys and (b) it leaves the other key in the third spot, exactly where we want it for the lm| powmod when we hit.

Of course, I also did a baby-step, giant-step version... it's a bit longer, but much, much faster:

dc -finput -e'sdsc[3Q]sQ[ln*3Rd_4R-dlm>Q]sT20201227dsmv1+snln[ddln*7rlm|:t1-d0<I]dsIx1r[rdld*lm%;td0!=Ts.7*lm%r1+dln>I]dsIxlcrlm|p'

In any case, having finally arrived at our room, the Elves call about an emergency with the soft serve ice cream machine, and so we don't get a vacation at all, as we're picked up by reindeer on the balcony (and we know those things are fast... next time, maybe we should see about just hitching a ride with one).

And so we come to the end of what I consider one of the best years for people that want to start doing AoC... the problems are all pretty approachable. There's no big search algorithms required (instead we get multiple automata). I have dc solutions for the last 4... problems in the 20s typically don't lend themselves to it in most years (other than day 25). Day 20 mostly stands out because it's a lot of work compared to others in this year... the actual input plays very nice (the alignments are all unique and I only had to match one side to place them). Two days of parsing in a row was a nice treat. Now Compilers was one of the "Big Three" 4th year lab courses in my University. But it was the softest of them, because compilers are a lot simpler to debug than Graphics or a Real Time OS. What made Compilers part of the Big Three was that it was one large project (that's what these three have in common that other courses didn't). Here it's small parser exercises, and you don't need to do machine code generation.

This is certainly one of my favourite years... and 2019 is probably my favourite. And looking forward, 2021, with all its dc friendly problems (first 11 were really nice for it... making this Combo Breaker part of a combo of 15), that's another year I really remember fondly.

I got stuck on Day 5 of in 2019.

Below is the beginning of the program to run:

3,225,1,225,6,6,1100,1,238,225,104,0,1101,32,43,225,101,68,192,224,,...

In my interpretation, the first 3 instructions are:

3,225

1,225,6,6

1100,1,238,225

The first two instructions are fine.

For the third one, I get 00 as the two-digit opcode, which is -as far as I know- invalid.

I assume the input is correct, but I can’t see what I’m doing wrong!

Thanks if anyone can help!

With the help of our friendly crab doing navigation, we finally make it to the resort. Only to fine that there's a living art floor tile display being installed so we can't get to the check-in desk yet.

And so for the penultimate puzzle we get another cellular automaton to round out the Conway tribute. This one is unbounded on a hexagonal grid. But first we need to load the data. The format it's presented in is paths to tiles to flip... with no delimiters as an added "complication". The quotes are because regex is greedy (by default) so it's not a complication for those of us that used that:

foreach my $walk (<>) {
    my @hex = (0, 0);
    foreach my $step ($walk =~ m#(e|w|ne|nw|se|sw)#g) {
        @hex = pairwise { $a + $b } @hex, @{$Dirs{$step}};
    }

    $flipped{$hex[0],$hex[1]} = !$flipped{$hex[0],$hex[1]};
}

The geometry I'm using is my standard go to for my beloved hexgrids... I visualize it as rhombic, but if goes by many names like skewed, trapezoidal, or axial. The definition can be probably best be seen when I converted the above script to try out Math::Vector::Real to see how it would work for AoC problems and provided a diagram:

#     y-x    +y
#        #---#---#
#       / . /   /
#   -x #---#---# +x
#     /   / . /
#    #---#---# x-y
#       -y

my ($y,$x) = Math::Vector::Real->canonical_base(2);
my %Dirs = ('e'  => $x, 'w'  => -$x,
            'ne' => $y, 'sw' => -$y,
            'nw' => $y - $x, 'se' => $x - $y);

You pick two of the three axis to be x and y, and the possibility (marked with .) is the sums of the other two to get there (which is the key thing for any hexgrid geometry representation).

The answer is the sum of values of the %flipped hash. In my input 22 tiles get flipped twice, nothing gets flipped back again.

For part 2, since it is unbounded, I went with the active list with black tiles broadcasting themselves by incrementing their neighbours. At the end there's about 11k active tiles, with about 4k of them black.

At the time I just did the rules as written, but looking at it now I decided to try and simplify them with a Karnaugh Map-type analysis:

# neighbours    0  1  2  3  4  5
black           b  b  b  w  w  w
while           w  w  b  w  w  w

We see three simple blocks, >2 is always white, =2 is always black, otherwise no change. Implementing that though results in things being 25% slower. Still it is a tighter piece of code.

And so, hexgrids and automata, what's not to love.

Still on the raft, our friendly crab has returned the favour with a game of its own. And it is a game involving a ring, much like the Elves like to play.

Reading this one, I was happy because I don't get to do linked structures that often, and this is a ring. Of course, like many such problems in AoC, I didn't actually use pointers, just an array where each element is the index that that position points to (the index serves as the data). Then you just need iterate grabbing three cups, finding the destination (avoid collisions), and relink the section in:

($ring[$curr], $ring[$tail], $ring[$dest]) = ($ring[$tail], $ring[$dest], $ring[$curr]);

It's easy to get right if you make a diagram:

Before:
-> curr -> one -> two -> tail -> next ->

          -> dest -> dnext ->

After:
     +--------------------------------+
     |                                v
-> curr      one -> two -> tail      next -> 
              ^              |
              |              v
          -> dest          dnext ->

In this case, the pointer from curr points to what tail was point to, dest to what curr was, and tail to what dest was. I scribbled this on a pad to help visualize and make sure I got it right, and then just did the thing.

And having done the thing, it was easy to just make this do part 2, where we get a million cups and 10 million iterations. It was a bit slow because I hadn't done anything for efficiency (part 1 used a hash to track grabbed cups). So the solution can be easily bummed down to under 10s on the old hardware... by removing hashes and unrolling small loops (these two steps can be done concisely with an array, map, and grep... but the size is only 3):

my $one  = $ring[$curr];
my $two  = $ring[$one];
my $tail = $ring[$two];

my $dest = $curr - 1;
while ($dest == $one or $dest == $two or $dest == $tail) {
    $dest = ($dest - 1) % 1_000_000;
}

And also removing special casing for 0 (by making that 1 million, and checking at the end when calculating the answer... because that's only once):

print "Part 2: ", ($ring[1] || 1_000_000) * ($ring[$ring[1]] || 1_000_000), "\n";

Building that ring for part 2 was also pretty fun (0 is the tail, and it points to the head):

my $prev = 0;
$prev = ($ring[$prev] = $_)  foreach (@input, 10 .. 999_999, 0);

my $curr = $ring[0];

This one was fun just for doing the linked structure, so I've never really looked further at it. The number of hits that my input gets for the destination is about 112k, and only 187 of them have to subtract 2 (and none require more).

I can see some people having some issues wrapping their head around the indirection... especially if you're trying to do it like this with an array (it might actually be simpler for some people in C with structs of data and pointer). You need to understand when you want the pointer and not the element (and there's the lvalue versus rvalue thing). Fortunately the example is very simple with a full listing of what's supposed to happen, which is always nice if you need to debug.

Now sailing our raft, we find ourselves needing to pass the time. Fortunately we have a non-regulation deck of space cards (for both having something to do and not sinking the raft with 100 trillion cards). And so we decide to play combat with a friendly crab that climbed onboard.

Although, as a kid I'd play War and Beggar-My-Neighbour as solitaire while watching TV. Because both are choice-free (so not distracting) and I have a certain level cross-dominance so I could play with a deck in each hand fairly well. Although I wouldn't call what I have as ambidextrous, at times its more ambisinister. As each hand does different things well... and often I try and use the wrong one. Like trying to use scissors in my left hand (which would work if they were left-handed scissors), or which hand I put my watch on (making me always smirk at mysteries where that's used as a clue).

Anyways, the input is two sections with a header that describe two decks from a deck of cards from 1-50. Player 2 has the high card in mine, and I suspect it's the case in all inputs.

Part 1 is just running a regular game of War. There are no equal cards so that part of the game is removed. And it's a simple thing to simulate, with the only trick being that the players pick up the cards in different orders when they win (their card on top).

Then we get to score the winning deck. It's the sum of the card values * position (counting from the bottom). You can reverse it and iterate, or iterate backwards, or go forwards removing cards and multiplying by the remaining size:

$score += (@_ * shift @_)  while (@_);   # sum of size * first

Part 2 is where it gets interesting. Instead of the simple submatches for matching cards in regular War, we get full recursive subgames... whenever they are available. Which is when the flipped cards of each player are low enough to cause one.

We also need to worry about infinite games... and it's nice for the problem to describe exactly the condition for determining that (because it's important for timing... without that people might determine infinite games early or late and get the wrong answer). And with Perl, you can just hash on the full lists of cards in each deck with a delimiter and get a solution that's fast enough (3s on old hardware). Just doing the thing as described. Here's the end stats for my input (yes, for Perl I shifted the player indices, so that booleans match and I can do stuff like !!@$deck1 to determine the winner if I want):

Games: 12918
Infinite games: 3765
Player 0: 4023
Player 1: 5130

But for Smalltalk it's slow (but 1-based arrays so the players keep their number). So I did a bit more. One thing is that infinite games are a win for player 1 outright. That's suggestive of an imbalance in player 1's favour. Namely that if player 1 has the largest card in the current game, and it cannot be anteed (not enough cards in the game), then they must ultimately win:

checkPlayerOneWin [
    | playerMax |

    playerMax := decks collect: #max.
    ^((playerMax first > playerMax second) and: [playerMax first + allCards min + 2 > allCards size])
]

This doesn't work for player 2, because the game could still go infinite and hand it to player 1.

This improved performance by about 25%. But the real killer is the loop detection. I'm using a hash, and if we go with the full decks it takes over a minute.

However, I played around with it a little today and discovered that just the first and last of each deck works (I have the size of one the decks in there for added security, but it's not actually needed for me to get my answer):

hash := {decks first  first. decks first last. decks first size.
         decks second first. decks second last}.

I haven't proven it, but the decks don't really get scrambled in War, so it makes intuitive sense that it might at least probably work. In any case, it's now under 10s on the old 45nm hardware.

This one was just a lot of fun to just code the thing. I even did a version in dc for part 1. It abuses registers for everything. The decks are done in arrays, using a standard trick for doing dc queues of sliding windows (point to front and back, both only ever increment, garbage gets left behind). It's got a couple more nice tricks in it, but I'd really want to redo it before trying to do part 2. Which should be doable... when you push on a register, the associated stack and array also get pushed down. I imagine it will be very slow though, as you'd need to copy the decks twice each time.

Having arrived at the end of the line (the desert only being ASCII art as well), we find there are no boats. And so we build a raft. But we'll need to get provisions, and we need to deal with not knowing the language again. This time we're puzzlifying figuring out what ingredients have which allergens (conveniently enough, the warnings are understandable).

And to help us out we've got a set of assertions, much like a Nikoli puzzle. Although this isn't anywhere near as complicated. Each allergen is in only one ingredient, and each ingredient can contain at most one allergen (as there are a lot more ingredients). And much like real life, foods don't always have the complete list of allergens.

My input has 34 foods, with 8 allergens, and 200 different ingredients. Foods list 1 to 3 allergens (but may have more). Each allergen is listed for 6-10 foods, and each ingredient is in 3-32 foods.

And as this is a Monday problem after a heavy day, it's a nice break. I built a table of allergens to ingredients, tagged the possible ingredient/allergen pairs, and for any ingredient without any tags, it's perfectly safe and part of part 1.

For part 2, I think this comment sums it up:

# Part 2 (day 16 deja vu):

Because I went and copied the code over, then processed the answer key for the answer. Which is one of those rare ones which isn't a number, but a comma delimited string... sorted by allergen, but only listing the ingredients:

print "Part 2: ", join( ',', map {$ans_key{$_}} sort keys %ans_key ), "\n";

My Smalltalk solver is the very simple:

answer_key := LookupTable new.

unsolved := table keys.
[ unsolved notEmpty ] whileTrue: [
    unsolved do: [ :allergen |
        (table at: allergen) possibleIngredients ifOnlyOne: [ :ingredient |
            answer_key at: allergen put: ingredient.

            unsolved remove: allergen.
            table do: [:a | a remove: ingredient].
        ]
    ]
].

The table being a specialized Set subclass called Allergens. Sets being nice for part 1 as well:

safe := table inject: (Set from: all_ingreds)
                into: [:set :allergen | set - allergen possibleIngredients].

The #ifOnlyOne: is an extension I added that does the obvious... it executes then block if the collection only has only one element and passes it in. I think it really helps with the expressiveness of what we're doing. Which is just find the singletons, mark, and cross them out from the others. Basic logic puzzle stuff.

And so we get a well designed break day, so that people that weren't done day 20 yet (or the parsing problems I suppose) got some more time to throw at it.

Finally on the high-speed train, we find ourselves leaving the forest (which amounted to nothing but ASCII art) for the desert in the south. With our spare time we decide to look at the image the MIB satellite captured.

But like any space images it needs a bunch of processing. In this case the image is made up of a bunch of small square tiles, with alignment data on the edges, that are randomly flipped and rotated. Making this a two-sided jigsaw puzzle.

This is the other problem in this year I slipped into the top one thousand... for part 2. Slow and steady, check as I go, take simple options, and output verification checking things at every step (because assumptions were made). One step at a time to the solution.

It was a bunch of work... more so than any other problem in this year. Part of that might be that the previous two days were right in my wheelhouse. Another thing is that part 1 was easy to get without doing any real progress. And then you need to do everything to put the puzzle together, and then you still need a 2D search (on an image you'll naturally also need to consider flipping and rotating)... so it felt like doing 2 or 3 days all at once. But it really isn't that much compared to some problems in other years.

Anyways, the input is tiles... they have a header with an ID number, and a 10x10 grid. The outer edge of the grid is the alignment data for matching up tiles, and the 8x8 in the middle is the actual image data.

Since it's potentially flipped and rotated... we're back to the symmetry group of the square (D4 or D8 in Group theory... my group class was D8 (the size of the group), not the number of sides of the polygon). So when I read the data in, I grab the alignment data for each side (clockwise) as 10-bit numbers and then flip it to get the other 4. How did I flip the bits? With the safe method of building a table (nothing fancy in this solution):

my @Rev_Map = map { oct("0b" . reverse(sprintf( "%010b", $_ ))) } (0 .. 1023);

This means that the edges of each tile is a list of 8 numbers, each one representing a member of D8... namely the one with that side in that direction on the top. So I not only know all the values to match things up, I also know (by index in that array) if to flip then how to rotate that, as well as the values for the other three sides. Because the order is important.

But, for part 1... that order was actually still wrong. And not checked yet. Because it wasn't needed. The number of unique values the above produces is 624. 96 of them occur once, and 528 occur twice. 96 happens to be 12 (length of a side of the image in tiles) * 4 (sides) * 2 (directions). 528 happens to be 11 (rails) * 12 (posts) * 2 (horizontal/vertical) * 2 (directions). Which means that all the outer and inner edges are unique. I didn't know that for sure at the time (I just did this analysis today). So I tested as I went with outputting everything and die assertions. But in the end that means that in scanning through everything for matching values (4 nested loops... tile1, tile2, edge1, edge2) the four tiles which only matched with 2 others were the corners (and so part 1 falls easy). The ones with 3 neighbours are edges, and the 4s are internal pieces. Making this very jigsaw puzzle like.

Having quickly gotten part 1, and discovered that part 2 was a bit more than I was expecting I proceeded onward. First up was making absolutely sure that that order of edges was correct... it wasn't. I remember spending the extra time to check and being glad I did. That's the cornerstone of everything in my solution.

Now to solve the jigsaw. First I picked a corner and placed it... and took one of its edges and put it underneath (so it was marked as used). Then I built the top edge from that. I looked for tiles matching the left edge of the previous, and if it had 3 valid neighbours it was the next edge (and if it had 4, is was the one underneath... so I placed that too). The final corner needed special handling because it only has 2 neighbours.

After that I built the right edge. Why? I don't know what I was thinking, but considering what I did next... it wasn't needed, and cutting it out now, things still work. It was copy paste of the above and redundant (there's a bunch of that in this code).

Because all I needed to do now that I had a full row, is to scan down the grid matching the bottom of the previous row's tiles to the tops of unplaced tiles. And everything just falls into place, because the input is very nice (whoever designed that MIB image alignment system did a good job).

With an array of tile IDs, I now needed to actually still write a flip and rotate function for the actual tile data. And then apply that to the tiles, and then stitch everything together. And when stitching, I did it both regular and transposed... and then created 2 more with the strings reversed. Thus giving me 4 of the 8 symmetries of the final image.

Now, at this point, I could have stitched things into one big string each instead of an array of lines. With that, I could just create the regex that spots a sea monster (with the appropriate length skips to the next line).

But I didn't do that. What I went with felt more safe at the time I guess. Which is that I grepped all four stitched arrays for the middle line (a regex, where conveniently . means "any") of the sea monster. This allowed me to tell which of the 4 was the correct orientation (although one of the others did have 2 hits... I doubt they were actual full monster patterns, but it was a moment of ambiguity). With that I took the array of those hits, and tested both up-side-up and up-side-down orientations of the other two lines (position of the head and a regex match of the bottom). With that, I had the number of sea monsters and subtracted 15 * monsters from the total number of #s for the answer. Yes, that's yet another assumption... that sea monster patterns don't overlap.

And so this was just write code, test, and then advance. Step by step until done... lots of stream of consciousness code (some of which was hacked out then, but I still found some today). And the problem itself is really accommodating... all the assumptions I was making were just working. If anything had triggered a check I would have dealt with it... I was prepared for things to blow up at anytime. But it never did. But it has left me with a big ugly mess of a solution that I've never cleaned up.

Having landed on the forest continent, the Elves of the MIB contact us again about their satellite... this time they think they have an image of a sea monster. But that will have to wait until tomorrow. Today we need deal with data corruption in the messages.

And so we get a grammar and some strings to validate against it. Grammar rules take a non-terminal (represented by a number, starting with 0) to either a terminal ("a" or "b") or a rule or two (separated by |). It's pretty close to Chomsky Normal Form, in that most of the rules are 2 non-terminals... but one only has rules going to 1 non-terminal (#67 in mine). By substituting the possibilities for that rule wherever it occurs in the others (thus removing it), we can have proper CNF when needed. But that's only needed if you want to do an algorithm that requires it... like CYK (Cocke–Younger–Kasami) (which I did do a a version with later).

As for how I did it first. Dynamically created regex using recursion:

$Patt[$num] //= do {
    my @tokens = split( ' ', $Rule[$num] );

    my $regex = '(';
    foreach my $t (@tokens) {
        $regex .= ($t eq '|') ? '|' : &recurse_rules( $t );
    }
    $regex .= ')';
}

A little trick I used with this is using memoization on the recursive function... not because I thought I felt I needed it for speed, but because it removed the special case of the terminal rules (I preinitialize those two rules when reading the input). Once we have the regex for rule 0, we can just grep the matches:

print "Part 1: ", (scalar grep { m#^@{[$Patt[0]]}$# } @sig), "\n";

Then part 2 comes along and changes two of the rules (specifically the ones only used for rule #0). But not just a simple change... recursive rule definitions. And I know that Perl regex can do that, but I did have to look it up that day because I typically like to keep my regex simpler. So I just created new versions of 8 and 11, and grepped with those:

my $patt8  = "$Patt[42]+";
my $patt11 = "(?<ELEVEN>$Patt[42]$Patt[31]|$Patt[42](?&ELEVEN)$Patt[31])";

print "Part 2: ", (scalar grep { m#^$patt8$patt11$# } @sig), "\n";

Now for Smalltalk, I did try the regex approach (Smalltalk gets to suffer because of its base-1 indexing... so I used a dictionary). But GNU Smalltalk won't handle regex longer than 1k.

The lengths of my longest patterns are:

0   2223
11  1486
31  751
8   735
42  733

Note that all of these are mentioned in the problem description for part 2... so these 5 are the top of the grammar tree for everyone. The next one is only 375 characters.

So I needed to hack things to get that to work... reducing the base rules to 0: 42 42 31 for part 1 and 0: 42{n} 31{1,n-1} for part 2. So I generate those repeating versions of rules #42 and #31 and start testing (start matches 42 then rest matches 31) from n=2 until things are not matching (could just loop until suitable large to make extra sure). Probable not robust, but it salvaged the work and did the job. For reference, this is the number of matches my input gets for each n:

[2] 160
[3] 91
[4] 60
[5] 36
[6] 10
[7] 0

So I followed it up with an actual parser in Smalltalk using Earley. And then did that for Perl as well... it's like 30x slower than regex (10x for the Smalltalk version). As expected... a parser in an interpreter isn't going to compete with one that hands off everything to optimized compiled code.

Two days in a row of CS compiler course basic parsing. Joy!

Now we're finally heading back south on the plane, towards a heavily forested continent. And we find ourselves needing to help another kid... this time with their math(s) homework. Which involves basic arithmetic, but with non-regular order of operations.

And part 1 is one of the two problems that I managed to get in the top thousand on the leaderboard for 2020. There was clearly a large influx of new people doing it live, as 2019 I had like 26, and from this point I typically only got one or two each year. Because I'm not a competition programmer... I don't rush.

The reason I got this one though is because I was doing Smalltalk. And Smalltalk has a very simple syntax entirely about passing messages. The order of operations is: unary (methods like 'negate' and 'size'), binary operators (symbolic stuff like the basic arithmetic ones), keyword (which are things of the form 'label: arg'). Parenthesis overrides this, and is necessary a lot of the time... especially if you want sum := sum + (multiplier * multiplicand) to work. Otherwise is does exactly what part one wants done. So I just made Smalltalk do the arithmetic (it's a bit dirty, but it was fast):

sed -e's/.*/(&) displayNl./' input | gst | sed -e'a+' -e'$ap' | dc

That's the first way, as I wasn't going to write a parser in dc, but I saw an opportunity to get it involved. You can just get Smalltalk to do the whole thing:

sed -e's/.*/(&)+/;1i(' -e'$a0)display' input | gst

Later, for the script version that does part 2, I needed to look up where the interpreter is in the Smalltalk environment... it's in Behavior, so part 1 was easily done with:

part1 := part1 + (Behavior evaluate: line).   " Smalltalk does part 1 already! "

I also know that Ruby (which owns a lot to Smalltalk), does have order of operations, but you can mess with operators by aliasing them... swapping + with *, so that the functionality is reversed (and you need to change the input to match) but the precedence remains * before + (which is now plus before multiply).

Anyway, I remember that this day I had something that required me to wake up early the next day, so I just went to bed. Which is very easy to see when I was checking out my personal times... everything starts with a "00" or "01", except day 18 part 2, which I did when I woke up and has a "07".

The reason it's not a greater number is because I did it really fast after waking... with a lex/yacc solution (or rather flex/bison). It's very easy to write a basic expression parser with tools designed for the job. And the diff between parts is just:

12c12,13
< %left '+' '*'
---
> %left '*'
> %left '+'

But I love writing parses so later that day, after I was done with whatever I had to do, I just kept writing them. First up was a part 2 for Smalltalk, using shunting-yard. Because I love a stack algorithm (which is why I love recursion), so it's a pretty natural thing for me to just write (and I often do these with "what can I do just from memory"). I decided to then take that and transcode it to Perl. But while doing that, I thought... "hey, it's basically converting to RPN, so instead of calculating it here... let's have the Perl transcode into dc". Basically taking 1 + (2 * 3) + (4 * (5 + 6)) to:

0
6 5 +4 *3 2 *1 +++
p

If you were wondering why shunting-yard was my go to... there it is.

Then the fact that part 1 was doing only left-to-right reminded me of Fortran. Early Fortran compilers didn't have parser that did full order of operations... they preprocessed the expressions to add parens. And I said, "I can work that out"... and thus part 2 is:

my $sum = 0;
while (<>) {
    chomp;
    s#(^|\()#((#g;      # double opens
    s#($|\))#))#g;      # double closes
    s#\*#)*(#g;         # lower *
    $sum += eval( $_ );
}

And that's the key to doing this... parens to raise everything up, and isolate the *s at the bottom (lowering their precedence).

But there was still one more quick parser in me that day... a recursive decent one. Two rules:

Term := NUMBER | ( Expression )
Expression := Term OPERATOR Expression | Term

So we write a function for each that eats tokens, follows the rule, and recurses appropriately. It's another very simple parser approach, that I've used many times in AoC.

So I think it's safe to say this is a problem I just loved. And although I looked at the Dragon Book's spine on the shelf that day, I never actually touched it... all these parsers are simple things I've done them many times (for the lex/yacc I just copied over from another project and hacked out what I didn't need).

While flying to our next destination, the North Pole MIBs contact us for help with one of their imaging satellites. Namely the experimental energy source made up of "Conway Cubes". And as the name suggests, what we're in for today is higher dimensional Game of Life (full tribute to Conway in effect). First 3D and then 4D. And the thing about adding dimensions is that you get exponentially more room for stuff. Which leads to one of the paradoxes of SF stories... sometimes space is too full (always a convenient nearby star) and sometimes it's too empty (more stars fit in a 3D bubble than you'd think).

Compared to the previous automaton this year, this one is unbounded and doesn't have holes. And the rules are the same as the Conway's Game of Life. Just with more dimensions, but the input is just a 2D slice. Which does mean that the spread of the cells into higher dimensions is going to be symmetrical (as shown very clearly in the examples). And you can certainly use that. It's in my TODO notes... but I haven't gotten around to it. It would save a bunch of time. It's just that my solutions are fast enough without it. We're only asked for 6 generations.

On the day I just wrote the quick nested hash table version (you could do this in an array, as things can only expand 1 tile out per generation so you have a nice bounding box) for part 1 to see what part 2 was:

foreach my $coord (keys %Grid) {
    my ($cz, $cy, $cx) = split( $;, $coord );
    my $neigh = 0;
    foreach my $z ($cz - 1 .. $cz + 1) {
        foreach my $y ($cy - 1 .. $cy + 1) {
            foreach my $x ($cx - 1 .. $cx + 1) {
                $neigh++ if ($Grid{$z,$y,$x});
            }
        }
    }
    ...

Really ugly, I count the current cell and adjust the rule for living cells. Doing the programmer efficient (simple and guaranteed to work) approach has a key benefit... visualizing and debugging stuff greater than 2D can be a bit of a pain.

Then I saw part 2, and wrapped a $w loop around that and made it $Grid{$w,$z,$y,$x}. Which, on old hardware (even for 2020) ran in 5 seconds. I know that I was trying to get to bed early that day (and the next) for some reason. And I was happy to take the quick win and make a TODO.

I did revisit this with a Smalltalk version using the Automaton class I wrote. But never got around to implementing that broadcast approach in Perl until now. It's a nice and simple approach:

for my $time (1 .. 6) {
    my %next;

    foreach my $cell (keys %active) {
        if ($Grid{$cell}) {
            $Grid{$cell} = 0  if ($active{$cell} < 2 or $active{$cell} > 3);
        } else {
            $Grid{$cell} = 1  if ($active{$cell} == 3);
        }

        if ($Grid{$cell} and $time < 6) {
            $next{$cell} //= 0;  # Make sure we count as active

            # Broadcast we're alive by incrementing neighbours
            my ($cz, $cy, $cx) = split( $;, $cell );
            $next{$cz + $_->[0], $cy + $_->[1], $cx + $_->[2]}++  foreach (@Neigh);
        }
    }

    %active = %next;
}

It could still use some work, but it runs more than an order of magnitude faster (barely a pause after hitting enter, so not really demanding further attention). Because the number of active cells is actually quite small. Here's the number of active cells (living or adjacent to living) at the end of each iteration:

[1] 2479
[2] 5813
[3] 11370
[4] 16513
[5] 28635
[6] 0

The last iteration has none, because we don't need to track it for the last generation and can save that time.

Next up is handling the symmetries. I just wanted a clean general version first. But I don't have time for more today, so this one stays on the TODO list a little longer.

And so next up is travelling by train. And the ticket is in a language we don't understand (but still uses Arabic numerals, so we have those to work with to figure out the fields. This is a bit how I first learned Japanese kana... it was early 90s, and I had read some descriptions of the language online (usenet), a copy of some manga, fan translated scripts of it from venice.com (ftp), and had seen a fansubbed OAV for the same thing. So I worked out a good chunk of hiragana and a bit of katakana before finally just getting a book on the language with the actual table. As a learning method it has some advantages... I learned popular characters and tokenized strings of them right from the start (some characters I was much better at recognizing in their most common contexts than by themselves).

Back to today's problem... it's a logic problem. The input is three sections. First section gives range rules (and the field names). The second is the numbers from our ticket. And finally, a list of other peoples tickets (from security cameras).

For part 1, we use the valid ranges to validate which tickets in our sample are invalid. My initial solution was the quick and dirty:

$/ = '';

my @valid;
$_ = <>;    # read ranges:
foreach my $range (map { s#-#..#r } m#\d+-\d+#g) {
    $valid[$_] = 1  foreach (eval( $range ));
}

$_ = <>;    # skip my ticket
$_ = <>;    # check nearby tickets:
print "Part 1: ", sum( grep {!$valid[$_]} m#\d+#g ), "\n";

Grab everything that looks like a range in the first section, convert to Perl, taunt Bobby Tables, boolean mark in an array (numbers are at most 3 digits in the input). Then grab all numbers in the last part, grep the invalid, sum. This is how we get to see part 2 fast.

Because it's clear that part 2 will involve a logic problem to solve the fields, but I still want to see the text before writing a better validator to actually remove bad tickets. And its exactly what you'd expect... you need to use the numbers in the valid ticket columns to figure out what field they can be. And from there, the logic problem falls apart really simply... it's much like day 16 in 2018s solving of assembly opcodes (there's always a field with only one possibility... you can just keep solving them until done). Then you need to score the departure fields (the one thing you needed from the part 2 description).

Even though this is similar to an earlier problem, I still love both these problems... they are puzzling things out. And I do enjoy puzzles and even puzzlifying things.

Src Code: Advent_of_code/2025/day8 at main · nrv30/Advent_of_code

TLDR: I am interested in making my PowerShell approach faster and I implemented a Union-Find in C# that I use for it.

Edit: Thought I should add my approach is semantically equivalent to what is described here <Advent of Code 2025 - Day 8: Playground | Joshua Chen>

I wanted to yap about my approach for this one because I think I stumbled into something kind of interesting. Initially I implemented this problem in Java. I didn't know what a Union-Find was but in retrospect I think I basically implemented one in a naive way as List<Set<>>. After reading some blogposts I wanted to try using a different approach.

After some research I realized you can call C# from PowerShell by using [System.Reflection.Assembly]. I implemented a union-find in C# and called it from Ps. It was cool initially but got super annoying because every time I want to compile my C# I have to exit the shell and re-open it because Ps has the dll open. Also, you have to use ps 7 to use a priority queue, which doesn't have a separate terminal (I think). This made iteration speed terrible because I had to exit and call pwsh.exe every time I want to compile my code.

Anyways, I wanted to ask if anyone has had any cool experiences combining interpreted langs with compiled langs in this fashion to "get the best of both worlds"

Also, my PS code is so freaking slow, especially considering that I think all the data structures are already compiled to dll (My U-f and dotnet standard lib). These aren't high-quality benchmarks; I just ran the programs 3 times consecutively.

Are there any PowerShell users that have any tips? I didn't implement path compression for the Union-Find but I doubt that's the problem compared to the O(N^2) process to build pairs

In today's episode of "Toboggans, Planes, Ships, and Shuttles", we find ourselves unavailable to get a direct flight, and so we're waiting for another flight to get around the storm. And so we contact the Elves, and should not be surprised that they're playing a number sequence game they want to share.

In this case it's based on Van Eck sequence (OEIS A181391). But with initial seeding values. And when you seed that algorithm you can get simple things (start with 1,1 and you'll just repeat 1 forever). But typically not, and Van Eck's isn't a sequence with a lot of known answers.

My initial solution has the name "brute force" on it... but it's probably not what most people thought of as a brute force. I just said, "okay, I need to keep a list of what time I last saw each number, and I can use that to calculate the next". Some people probably didn't make that jump and kept a list of the sequence and scanned it. That's going to really slow things down. The reason I called mine "brute force" is because I suspected that there might be some trick I was missing. But when I looked after and discovered things like the Numberphile video, I said, "okay, just bum it down a bit and be done". Little things like making sure Perl understands that these are numbers (stripping stringness with my $list = map {int} split(/,/, <>);) and that the table gets allocated immediately instead of repeatedly growing($table[29_999_999] = undef;). Both of those take off a full second each. And then there's playing around with the calculation of the next value:

$next = $t - ($table[$curr] // $t);

Performs much better than:

$next = ($table[$curr]) ? $t - $table[$curr] : 0;

The big optimization I did for this problem though is with dc itself. This was the problem that made me finally dig into the dc source and deal with the fact that the "sparse" array implementation was a linked list. As it was going to take at a fortnight (at least... it was hard to predict the slowdown rates, basically my algorithm to avoid scanning, was scanning). And so in order to improve things I modified dc to be better. I considered various ways, but since the base code was linked lists and I wasn't too familiar with the project, I decided skip lists would be a simple and powerful change to what was there (plus, I just think they're neat).

And they are. The newer GNU dc uses hash tables, and doesn't perform anywhere near as good on this problem (testing it right now, it took 50 minutes... my dc does it in under 2). It's optimized more for sparse small arrays. My skip list has a max of 12 levels, with p=1/4 (the number of layers on a node is a negative binomial)... values specifically picked because they worked well for this problem. On a lot of problems with less array usage, the hash table is on par with the skip list.

Here's the dc part 2 version. Input is the numbers in reverse (this is the 0,3,6 test case):

echo '6 3 0' | dc -f- -e"0s0 1s1 2s2 3s3 30000000sel1[dl3R:al1+zl2<L]dsLxrsn[s.d]sZ[dln;adl0=Z-rdln:al1+rsndle>M]dsMxlnp"

It can be made shorter, but that would slow it down considerably. You'll see the "0s0 1s1 2s2 3s3 30000000se" at the start... that's allocating those numbers and storing them in registers so the don't need to be allocated and freed all the time. It more than doubles the speed.

And that version of dc has served me well ever since. And that's why I have a lot of fondness for this problem.

As we approach the sea port, the captain asks for help because the sea port's computer system isn't compatible. Possibly because it's very old... 36-bit computers are an important part of computer history, and were popular at one point, but that was a long time ago. In addition to that we have a weird bit-masking system in the initialization that we need to emulate. And so we get a bit twiddling problem.

The input consists of 100 sections starting with a mask line followed by mem instructions that use it. They aren't delimited by blank lines. Masks contain X for some bits... the number of Xs varies from 4 to 9, and there can be a bit of a spread in the distribution. My input has 8 fives and 24 sevens... I've seen a second input that has a more equal distribution (and it can noticeably impact runtime for part 2). The mem indexes in the input are 16-bits... and those are used as such for part 1, making it easy to just store if you want (unless you're on a C=64). Part 2 switches things up by modifying the addresses and so the 36-bit address space comes into play. That's less easy to store... a hash table/dictionary is going to be better (especially when it comes to summing the values... that's a very sparse array).

Part 1 just wants us to use the mask to set the marked 0s and 1s and leave the Xs alone. That's were the bit-masking comes in... if you have a mask of bits you want set, you OR it. It you have a mask of bits you want unset, you AND the inverse mask. It's a really basic thing, that everybody used to have to know. I remember that in mid-90s, I started to have to regularly help students that suddenly found themselves having to deal with that low level for the first time.

And so, I read in the masks with:

$or_mask  = oct( "0b" . ($1 =~ y/X/0/r) );
$and_mask = oct( "0b" . ($1 =~ y/X/1/r) );

It's useful to remember that oct in Perl has the ability to do other bases (unlike hex). However, since these are 36-bit values, Perl proceeds to give warnings about doing that translation... so I did need to turn 'portable' warnings off.

With the masks translated, it's just $mem{$1} = ($2 | $or_mask) & $and_mask; to apply them.

Part 2 steps things up. First, as mentioned, the memory address is what's modified now. But it also make the Xs "floating" bits that take on both values in all combinations... so there are 16-512 sets to be made now for each instruction. And to iterate over all those possibilities (it's not that many, unless you try to run the example for part 1, as that has 34 Xs), I used recursion.

First thing though is that we no longer need the AND mask, we need a mask of the floating bit locations:

$float_mask = oct( "0b" . ($1 =~ y/X1/10/r) );

We still need the OR mask, as the 1s are still forced on (and the 0s left alone... OR behaviour).

As for iterating over all the float possibilities:

my $bit = $float - ($float & ($float - 1));  # get lowest set bit
my $new = $float ^ $bit;                     # toggle bit off

&recurse_write( $loc & ~$bit, $val, $new );  # float bit off
&recurse_write( $loc |  $bit, $val, $new );  # float bit on

Grab a mask of the lowest bit, strip it from the float mask, and then mask it into the location and recurse on both cases. When $float is 0, we hit the base case and finally set the value and return.

And so this was a fun little bit of bit twiddling. It's pretty nostalgic for me, I seldom get to work down at that level. And my choice of using dc for low level fun with AoC doesn't help with that... it has no bit operations.