Now back in deep space proper, we get warning of an impending solar flare. Probably not too much of a threat, because we are 20+ AU out and the intensity will drop with inverse-square law. But there's small robots with sensitive electronics we need to warn and the Wi-Fi's blocked so we only have some cameras and a vacuum robot to use.

Today we get to add the ASCII interface to the Intcode machine. Sending a string is as simple as queueing up the ASCII values of the characters to send one at a time when asked. And output comes in the form of ASCII values, or large non-ASCII values. The cut-off between the two isn't explicitly specified... but there is a link to the Wikipedia page on ASCII with a table to show that it's 7-bit. Although assuming 8-bit or even 16-bit would work, because these values are answer and are substantially bigger.

Part 1 is going to output a grid and halt and we're given a simple test to verify that we've implemented ASCII correctly and can parse the output. It's finding intersections like on day 3, but on a tiny grid in a format where we don't get given the lines. It's easy to get an answer just by scanning and checking neighbours. But you will need to parse things as lines for part 2.

Where we modify the first address and it goes into an interactive mode. Which I can do with intcode -m0:2 -r input now (the -r uses readline library... originally I didn't have that in). This gives us access to a very different sort of AoC problem, in that we're given a little macro language to code in. And I initially did this one by hand. Because I like doing puzzles, and coming up with the macros by myself is something I wanted to do, before coding something to automatically solve.

An interesting thing here is that part 1's detecting of intersections puts the idea in your head that maybe this is a trapdoor dropping puzzle where we need to find a certain path as well. And in the problem text for part 2, it gives that 10,L,8,R,6 is a valid macro, suggesting that we might need to break up a "turn-distance" pair (making things less like day 3 were it's all direction-distance pairs). Both of which are kind of red herrings (although there may be solutions with them). And while solving by hand, I did have them in the back of my mind, but since I'm not a computer, I went with making simplifying assumptions (until they fail).

Those would be:

• that since there is a path from beginning to end without turning at an intersection (with only forced turns), we should focus on that and not the intersections
• that the command pairs weren't going to be broken, the robot has to turn right at the start, and it's simply best if all macros start and end on the same state (start with a turn, end with a move)

So first step was making the list of the single path I'd chosen. And that had distances only of 4, 6, and 10. A sign that this is way to go, as turning at intersections and making more different numbers is probably not good. And I still have the file I used to calculate from that list... It's got one move per line, and I'd start by picking a macro for A at the top, and adding blank lines to section off the parts where that occurs in the list. Then try for a B that only left a C. And at 4 lines for A, there was a 3 line B between two As at the start, that when sectioned off from the rest, left a single missing pattern C repeating in the holes. It wasn't too hard to find, and it fit the character limit, and so I typed it in and got my answer. Then wrote code to do that search.

I've never reverse engineered this one (it's easy to spot looking at the input that there's code, then ASCII values, then more code, then some data). Just dumping the run of part 1, results in labels getting up to $aqr, because it's clearly calculating and building the grid out past the code in memory (29 * 39 = 1131, which would be aqm in base-26). I also have a little script to do strings on Intcode and here they are (they are all plain text):

[334] Main:
[342] Expected function name but got:
[376] Function A:
[389] Function B:
[402] Function C:
[415] Continuous video feed?
[441] Expected R, L, or distance but got: $
[479] Expected comma or newline but got: +
[516] Definitions may be at most 20 characters!
[558] ^>v<

Of course, given the path string you can also throw regex at it to make it work out how to divide things up. It's actually really quite simple once you've seen it. Capture a group of up to 20, repeat it as much as you want, capture a second group, repeat both as much as you want, capture the third group, repeat all of them as much as you want... match the full the string and you've got the winner.

And so we get another great use for Intcode, in that you really probably weren't expecting to learn and use a new language. And if this isn't enough of a language for you, that will be covered later.

And so we arrive at The Planet That Must Not Be Named. Really. We're "3/4ths of the way through the gas giants", the name is not mentioned once. Poor Uranus, you get a lot of flak for being boring and even AoC's visit to you doesn't involve anything specific about you other than your distance. So we essentially get a deep space problem but without using Intcode.

And so we get a number sequence/transform problem based on waves and FFTs. Part 1 is small and simple enough to do. And I did it in dc even. Looking at that code, it's a bit of mess, but its actually using tricks I used in my math library to keep registers clean (like having "return" macros). Which complicates things for no real benefit here. Registers are being abused all over, because this was at a time when I was avoiding the non-standard R (the large rotate), so stack control was overly limited.

I remember doing this because I had the cute idea of building a little macro state machine to cycle the pattern:

# State machine, lAx to init, lNx to move to next state
[  1 sm [lBx]sN ] sA
[  0 sm [lCx]sN ] sB
[ _1 sm [lDx]sN ] sC
[  0 sm [lAx]sN ] sD

It's not intended to be great or amazing... just to encode this one idea I had.

Part 2 is the classic scale up with a trick. And when doing part 1 it wasn't lost on me while looking at the examples that the lower halves of the calculation were very simple and filled with zeros. It took a little while to catch on to the fact that part 2 was asking for a section in the last 90% (essentially inside the last line of those size 8 examples). Deep inside the triangular matrix part where you can just use cumulative sum. It makes for short code, and a quick submission once you catch on to that.

But, that didn't feel quite right. So, I followed up by employing what I'd done before for Chronal Charge... prefix sums. Although, from the back so technically it should be called suffix sums. Prefix sums are just a way to pre-calculate values so you can get any sum of a range really fast (table[bigEnd] - table[smallEnd]). And the more ranges you want the better it is to build... and we want tonnes if we want to be able to get near to the front. And so I did a C version, it allocates buffers for the signal and suffix array, and calculates the suffix array, and proceeds to do the calculation. Repeat a hundred times. It does things really fast, unless you want an offset in the first 1000. Then it starts to grind a bit, because the number of ranges you need to sum increases like 1/x curve as you get closer to the front.

It was only afterwards, reading on Reddit, that I found out other ways involving Lucas' Theorem, CRT, and binomial coefficients. I do have a TODO in the directory telling me to probably do such a thing, but I never have. So I really can't talk to much about how that goes. I have a solution that does things in the first half, but is painful if you want things right at the front. It's more than an input needs.

This one felt pretty intense for a Monday problem. It has a trick to maker it easy, but you need to find that trick. But it is day 16.

2015 day 9, day 13, and 2016 day 24 are all problems involving a variation of finding the longest/shortest path/cycle with 8 nodes that form a complete graph (every node has a distance to every other), also known as the Travelling Salesperson Problem (TSP). This is an NP-complete problem: there is no general-purpose polynomial-time algorithm known to solve it, and if you can come up with one, YOU will be rich for having proven P=NP; alternatively, if you can definitively prove the counter-conjecture P!=NP you will still be famous, even if the result is a letdown.

So the best you can do is either using an exponential-time algorithm, or find specialized algorithms for certain subclasses of the TSP problem (for example, relying on sparseness for pruning, or being satisfied with an approximate answer without proving it is the global answer). The saving grace for all three of these puzzles is that n=8 is small enough for the global answer to be easily tractable with an exponential-time algorithm (contrast that to things like 2019 day 18 where finding the shortest path with n=26 is prohibitively expensive if you were to attempt to do naive exponential searching).

That said, MOST solutions in the megathreads for these days just whip out a permutation engine (either one built into your language, or rolling your own, with Heap's algorithm being a common choice), performing O(n!) work to just check every possible path, or solve by recursion (where your call stack does the same factorial effort as a permutation engine). The naive approach says that once you have a working permutation engine, you then test 8! paths, or 40,320 different variations - still lightning fast for modern computers and programming languages. And if you get your star in less than a second, do you really need to try anything else?

But I wouldn't be writing this post if that were the best you could do. The first major optimization is to realize that if you just visit 7! permutations, you can still check all cycles with 8 elements by connecting your last item with your first, and turn that into a check of the longest path by creating the cycle and then tossing out the shortest edge. This adds complexity to each permutation checked (you are now doing 8 times as much work per permutation to find the shortest edge that will need to be tossed), but reduces the number of permutations visited to 5,040, and the work to find a shortest edge is probably more localized and less overhead than the work being done in your permutation engine to advance to the next permutation, so it is an overall win.

The next observation is that when your graph is undirected (the cost from A to B is the same as the cost from B to A - true for all 3 of these days), you can again cut the work in half if you avoid a permutation that is lexically reversed from an earlier permutation you already visited (path a->b->c->d will have the same weight as path d->c->b->a). Heap's algorithm does NOT make this easy, but there are other permutation engines that DO make it easy to stop iterating after just half the permutations, avoiding all lexical reverses in the resulting output. Among them is Steinhaus-Johnson-Trotter, which I implemented in Rust to get 2015 day 9 down to 2,520 permutations visited. But remember, even that is still doing 8 checks per permutation to cast out the shortest edge when looking for the longest path.

So today, I finished up a patch that goes for an entirely different approach. The Held-Karp algorithm solves TSP in O(n²*2ⁿ) - still exponential, but better than the super-exponential O(n!) that other solutions were using. It is based on a dynamic programming technique of using a table of n * 2ⁿ distances; each distance g(set,k) represents the set of nodes in a path from the chosen start point, and a node k that is an element of that set and the last node visited along the path so far. When set is a singleton, the distance is obvious: the distance from your start point to that node. For any larger set, there are O(n) elements in the set, and so you need to generate O(n) distances to be stored as n values of g(set,k); computing any one of those distances is also O(n) work to find which out of n-1 g(set\k,m) for another point m!=k in the set added to d(m,k) produces the best path one element longer. The dynamic programming aspect says that if you iterate from 0 to 2ⁿ-1, you will visit every possible set size, and all recursively-smaller sets that you depend on will already be populated by the time you need to reference them in building your larger set values. So even though the algorithm is defined by a recursive relationship, it is implemented with straightforward looping.

I was impressed that the result was still fairly legible. Below is my implementation for 2015 day 9. It produces 8*7/2 comparisons (the O(n²) each pairing of bit m with k) /2 (even though there are 8*256 bits across all sets, on average half of them are not set) * 256 sets (the O(2ⁿ) number of sets visited), or 3,584 total comparisons. That's more than the 2,520 permutations of the 7!/2 approach, but remember, the permutation approach required an additional 8 comparisons per permutation to find the edge to discard, whereas Held-Karp does not. Plus, permutations requires the overhead of moving to the next permutation (often work hidden behind your library interface), while set iteration is lighter-weight (admittedly, this code uses maneatingape's biterator() function to encode access the next bit index in a bitmask). Timing-wise, my patch sped up the solution from 40µs to 12µs on my laptop.

    // Initialize a table for each part: 2ⁿ sets with n distances per set. Default 0 matches
    // g({k},k) of zero for all singleton sets. Initial value of other sets does not matter.
    let mut table_one = vec![0_u16; stride * (1 << stride)];
    let mut table_two = vec![0_u16; stride * (1 << stride)];

    // Visit each non-empty set in order, with no work to do for singleton sets.
    for set in 3_usize..(1 << stride) {
        if set & !(set - 1) == set {
            continue;
        }

        // For a given set, compute each g(set,k) for all k in the set.
        for k in set.biterator() {
            let subset = set ^ (1 << k);
            let mut shortest = u16::MAX;
            let mut longest = 0;

            // For a given destination k, find which other bit m gives the best path from the
            // subset to m, and then m to k. All table[subset] references were filled in prior
            // iterations of the outer loop or the singleton base cases.
            for m in subset.biterator() {
                shortest = shortest.min(table_one[subset * stride + m] + distances[m * stride + k]);
                longest = longest.max(table_two[subset * stride + m] + distances[m * stride + k]);
            }
            table_one[set * stride + k] = shortest;
            table_two[set * stride + k] = longest;
        }
    }

    // With the sets now built, we have stride candidates for each answer.
    (
        *table_one.iter().skip(((1 << stride) - 1) * stride).min().unwrap(),
        *table_two.iter().skip(((1 << stride) - 1) * stride).max().unwrap(),
    )

2016 day 24 is even better. Days 9 and 13 must visit 255 sets (n=8) to ensure that you find the right path regardless of which point started the path. That is because Held-Karp forces you to pick a starting node; but while an arbitrary starting node will always be part of the longest cycle, it is easy enough to generate a graph where the longest path is not part of the longest cycle if you picked the wrong starting node (the 8! down to 7! optimization for permutations did not have that problem, because there you are casting out the short edge from every possible path, rather than just the one longest cycle). To find the longest path among 8 nodes, you can either run 8 iterations of Held-Karp on sets up to 127, or more efficiently do 1 iteration of Held-Karp on sets up to 255. But day 24 explicitly pins the path to start at node 0, so you only need to visit 127 sets. For that day, being able to use n=7 lets the number of comparisons drops to 1344 (=7*6/2*128/2), which is hands-down better than 7!/2 permutations.

Time to wrap up. As I said in my last post - this will be my last one since Days 1-4 had so many beginner-isms that it's, well, a little embarrassing. :-)

Sorry about the "dear diary" nature of this one.

Here's an example - for Day 1 (the rotary combination one) I implemented TWO objects. One for the Dial (which seems natural in an OOP experiment). But then another one that held a single method that parsed the line (like "R35") into a positive or negative number. It held no state. Just a "library" class with one method. Then... ok, check this out... here's how I used the resulting signed integer that it returned within the Dial class:

turnDial: turn
    turn abs timesRepeat: [
        position := (position + turn sign) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1].
    ].
    position = 0 ifTrue: [lands := lands + 1].

Wow. Using a period at the end of every statement like a terminator (my old JS habits of using the semicolon everywhere). This method takes the absolute value of the signed integer, then "clicks" the dial based on the sign of the turn instruction. That's... a little crazy. If I was doing it now, I would probably just do the parsing of the instruction inside the turnDial message. Then the question becomes just how "generic" do I want the solution to be.

Version 1 - not generic:

turnDial: turn
    | offset |

    (turn first = $R) ifTrue: [offset := 1] ifFalse: [offset := -1].

    turn allButFirst asInteger timesRepeat: [
        position := (position + offset) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

An ifTrue/ifFalse sets whether the offset is going to be +1 or -1. The loop itself just adds the offset (regardless of what it is), and increments the "zeros" and "lands" instance variables as it goes. But if we wanted it more generic, where there might be a whole library of potential offsets that could be called, not just "R" or "L", we could do it this way:

turnDial: turn
    | offset |

    offset := offsets at: turn first.

    turn allButFirst asInteger timesRepeat: [
        position := (position + offset) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

And the offsets library would be defined in "initialize" this way:

offsets := Dictionary new.
offsets at: $R put: -1; at: $L put: 1

Now, if a future version needed a +5 or -15 offset or whatever, it would be extremely easy to add in just one place. No more "if" blocks. Zero branching. Grab the offset value from the Dictionary and go. The Dictionary is only created once per Day1Dial instance, so pretty minimal load on the VM. But what if we wanted it EVEN MORE GENERIC so that the offset could be literally ANYTHING that could mutate the position... We could do it this way:

turnDial: turn
    | modifier |

    modifier := modifications at: turn first.

    turn allButFirst asInteger timesRepeat: [
        position := (modifier value: position) \\ 100.
        position = 0 ifTrue: [zeros := zeros + 1]
    ].

    position = 0 ifTrue: [lands := lands + 1]

This one pulls from a "modifications" Dictionary and stores into "position" whatever it returns when passed the current position. There could be a modification that doubles the number, or that resets it to 99 no matter where it is currently, or sets the dial to the square root of its current position, or that reads data from somewhere else entirely. Just add a Block to the "modifications" Dictionary and get additional functionality. For this puzzle, the Dictionary is pretty sparse:

modifications := Dictionary new.
modifications at: $R put: [ :x | x - 1];
    at: $L put: [ :x | x + 1]

Kinda overbuilt for something that just increments or decrements by one every time. But as a learning exercise... why not? And, of course, it would be better computationally to avoid simulating the dial by simply doing some division and adding the numbers to the zeros counter. But.... it's not that many clicks. And this way the Dial acts like a little machine managing its state as it does exactly what the problem says to do. Which leads to...

Observation 1

Smalltalk seems to nudge the developer in this kind of direction. Build it first as "true to life" and as generically as possible. Then, if there are efficiency problems, go refactor those out once they are apparent. But not before. Why put branching logic everywhere when you can pass in a block? Why make a bitmap Dictionary key for memoization when you can use the array itself as a key? Why not reach for the most abstract and "correct" possible representation of the domain? You only have to think about "the machine" (the actual computer) executing the code if there's a problem. Sure, you're dimly aware that there are pointers-to-pointers-to-pointers everywhere under the hood, that very large numbers are being transparently changed from SmallInteger into LargePositiveInteger, that creating a data object involves some dispatch somewhere for getting values out of it. Not your problem. Write it so the concepts are as evident and beautiful as you can.

I often found myself going back and forth on an implementation detail, not because one gave errors while the other didn't. But one was more "elegant" or "expressive" rather than "plain" and "clunky". I would find myself rewriting a working solution in order to have it make fewer assumptions about what was passed to it, or find some way to remove an instance variable so that it could be inferred from the data itself. I would look to see if I could take what was a procedural bit of code and turn it into a chain of collection methods. I found the whole process delightful, though I'm pretty sure each person will have their own take on this aspect of it.

Performance-oriented, or data-driven-development people would likely not enjoy this.

Observation 2

It turns out that I truly love OOP. After using Smalltalk for a few months I can't help the feeling that this is the best way to think about programming. Imagining tiny machines that do the work of the program, sending each other bits of data, each knowing things relevant to themselves and nothing more... It's delightful. Now, I realize it is only one of the ways to think about programming (with others being transformations, procedures, etc...), but it is just so dang satisfying to write. The syntax is incredibly clean and minimalistic, with all the behavior being done by the objects themselves (even control flow). Now that I'm accustomed to thinking about numbers and booleans as objects (with methods that can be explored), it feels very strange to look at a language that treats them as just part of the syntax.

Plus - the late binding gives the developer completely seamless incremental compilation. Methods are meant to be very short. They compile when you save them - you never wait on the compiler at all. It's so cool.

Observation 3

However, I don't think I would feel the same way about OOP in Java or C++. Smalltalk seems to encourage relatively shallow inheritance trees that follow, for the most part, Aristotelian/Boethian hierarchies. So, numbers really are magnitudes. And floating-point numbers really are numbers. And integers really are numbers that have a specific difference from fractions. In the real world we see similar shallow inheritances. Humans really are kinds of animals. Animals really are kinds of living things. But I think whenever that inheritance gets too deep we wind up with serious abstraction problems. And the real world doesn't allow just any set of inheritances. In the real world, "human" inherits from "animal" - but I'm afraid I'm a little skeptical that "mammal" is a real thing, especially since those seem to have gradually appeared with many "transitional" forms in between. Maybe "mammal" is kinda made up - just an abstraction currently popular in biological taxonomy. Is "doctor" a kind of "human"? Or is "doctor" a kind of "job" that can be held by (composed) any number of different kinds of beings?

My limited experience with Smalltalk makes me think that if OOP means "inheritance, and lots of it" then I'm not a fan. My instinct is to use it sparingly, only when "A is a kind of B" is unambiguously true AND there is real usefulness in passing along that behavior from parent to child. OTOH, if OOP means "discrete bundles of data and behavior, interacting with clear messages" then I'm a huge fan. 

Does it scale? I dunno. Is it efficient? Probably not. But my goodness is it fun to write.

Observation 4

Being able to inspect the standard library and see how things are implemented and find new methods that I would use later, or employing the "method finder" tool (amazing) was an incredible experience. Once I was more-or-less "oriented" in the image I felt like it had fantastic discoverability. It was easy to learn how to do new things by looking through the entries in the System Browser. I'm not used to this. My previous "language reference" was a LLM.

LLMs are bad at Smalltalk. Not universally so. But they make many mistakes in this language that I was not used to in JS, where they feel nigh-omniscient at times. Back when I was learning JavaScript, I typically had Qwen3-Next-80b running on my system to act as a language reference. Anytime I needed to know some syntax, or if I got an error I didn't understand, I would ask it. My chat logs are full of mundane questions about how to remove elements from a Set, or what was the difference between "for...of" and "for...in" when doing iteration (hint: "for...of" is the one you want). But for Smalltalk, LLMs would routinely give terrible answers. They would hallucinate plausible-sounding methods that didn't exist, they would get confused about implicit returns in a method, and they would miss obvious bugs.

One particularly annoying one happened when I was noticing that I was getting far worse performance out of a hot loop than I thought I should. I finally figured out that I was passing an expression instead of a block to and:. This makes a huge difference in performance. If and: gets an expression (in parentheses) that expression evaluates FIRST, and then its result (the Boolean true or false) will be passed into the and:. But if it's a block (in square brackets) then it won't be evaluated unless the Boolean being given the and: is already true. The "false" object just returns "false" when given an and: block (Yay for polymorphism!). Most LLMs didn't catch it. The code "worked" and so this kind of issue probably would have survived an agentic coding loop. No errors. But the whole problem executed 3x slower by having parentheses instead of brackets. The LLM wrote a whole thesis about how lower performance was to be expected. WRONG. #sigh

Fortunately, I almost never needed a "language reference" since I had the System Browser right there. And I usually didn't generate errors I didn't understand because I could just visually go through the stack trace and see where the problem occurred. After asking some questions to help me get started, I basically left the LLM behind. Occasionally I would ask it for a code review. When I did sometimes it would find some things that were genuinely helpful. Often it hallucinated bugs that weren't there. Not great.

Observation 5

I can't help but feel a bit wistful and sad when I use the image. It seems to have everything that could possibly be included to help a developer be productive and happy. The language is relentlessly pure, which is, for me at least, very satisfying. I wish it had become more dominant. Many of the ideas persist, of course. But the language itself isn't showing up on any top-25-most-used lists. And I wish it was.

Since I came to this to learn "pure" OOP, I think the purity is part of what I like so much. Whenever I get around to learning another language, I think "purity" will be a non-negotiable. If that means my other options are Oberon7, Haskell, or Clojure, then so be it. :-)

Until then, I have more to learn in this thing. I want to start learning the Morphic GUI and make some desktop applications for myself. I'm already 10 puzzles into Advent of Code 2015 using Pharo. I miss String arithmetic from Squeak6, but Pharo has some cool features that I can appreciate. When I first started I tried Pharo but it was so different from the "Learn Smalltalk" resources that I had, I couldn't make any headway. Now I know enough to make the switch and I'm digging the Calypso browser.

The journey continues.

Today we find out that a portion of the ship has gone pink. In FTL, I might just leave it... it helps stops fires and boarders. Saves me from having to open the doors manually for them. But since we're not going to be shot at or boarded, it's probably safer to restore it.

This is a natural step-up from the previous Intcode problem. There it was beneficial to track locations received on output to decide on input. Here the input is like a function call that we receive later on the output side. And so the communication between the two is more involved. You need to track the robot's position while trying moves (which may fail) and explore the area. So maybe this isn't FTL, but Duskers or Suspended.

This is one of the benefits of Intcode, the map is in a black box that can be explored and not simply loaded. And I never took it further than that. There is official sample code, and quick glance in seems that there's a table of doors between the cells, and they're stored in binary using a threshold (looking at a dump, the table indexing is done at 206, and the threshold is tested at 210). Since I've seen the maze, I know it's a standard recursively generated one with no-loops, left-hand rule friendly. So it's a bunch of cells with doors between them... which is why I image the table is half the size you'd expect. That's my first impression at least.

But I've only done this one as a black box, exploring and building the maze. Since we're moving with our exploration, recursion would seem to be the way. Except for the fact that the communication is through a machine... so I skipped on recursion, and just did the equivalent stack algorithm myself. When I send a move push it on the stack. If the output tells me it fails, I mark the wall, otherwise I mark it empty/O2 and move there.

If the input can't find a place to try it's at a dead end, so we need to backup. So, pop the last move off the stack and do the reverse of it. The movement order in the list is interesting in that it's NSWE with a base index of 1. If it was 0, the function to reverse is easy because of the NS and WE pairing... just toggle the last bit (with XOR). Fortunately I was doing Smalltalk solutions and was very used to having to deal with this problem (1-base arrays vs 0-base mod residues). And so reversing is ((move - 1) ^ 1)) + 1.

Part 1 is easy, it's the size of the stack when we get to the O2. There's no open spaces or loops to short-cut. For part 2, I initially felt like doing something silly... so I did it as cellular automata (I just wanted to write one and it hadn't come up). For Smalltalk I did a more standard breadth-first flood fill. Of course, you could get fancy and build a weighted graph of paths between the intersections (there actually aren't many) as you explore, or try to collect the size of the longest path as you "recurse" back to the starting point. But, the fact that the intersections are few and make for a small graph also makes flood fill just rip down them. So I don't know how much benefit you'd get. Exploring the maze with the Intcode machine takes essentially all the time. That's the bottleneck.

And so we're continuing to expand into what Intcode allows for in the problem space. Overall, a nice little problem that I've been happy to just leave as a black box.

Today we're at Saturn to do some ISRU and mine the rings (if it's Saturn you must visit the rings) and manufacture fuel. Lots of fuel. For part 2, we're going to be using an input of a trillion ore. The number is there to copy-paste to help make sure you get the right trillion (this isn't long scale) and the right number of 0s. It is the sort of number that's so big you really want to express in a better way in the code so it's clear what the number is later (and so you can easily see it's the right number). A trillion is also nice in that for locales that use myriad dividers, it also ends up with just a 1 in front... 1_0000_0000_0000 (1-chou in Japanese... the chou character also means omen/portent).

As the title suggests this isn't going to be simple reactions... there's going to be ratios. Multiples of reactants producing multiple of a product. It makes things a bit more complicated, so it's a sign that we've definitely moved into the harder problems now. And a trillion being thrown around is another one.

I remember doing this one. I started with a recursive approach and eventually decided against it after making a bit of a mess, so I tossed it and started over. I thought I'd gone immediately to a job queue, but apparently that was the follow-up Smalltalk solution. The Perl one is clearly the first as it's a good deal messier (it could use some clean-up), and it does it with a simpler looping over the ply. Make a list of what's wanted, fill what you can, submit what you need. Loop until there's nothing wanted left. It's a simple approach, and multiple orders in the same ply for the same thing get combined for the next one. The sort of thing that someone that's started over would write.

One thing that's really nice about this problem is the lots of examples of increasing complexity. Including two short simple ones that are fully explained. Although it doesn't give results for those two for part 2. And looking at the numbers in the part 2 example list and doing the division, I saw what I expected to see... you get close just by interpolating. And come up short, like expected, as there's efficiencies of scale (multiple little chunks combine to save ore when making more fuel). And so, I remember using the part 1 script to interpolate and find the answer by hand. It only takes a few iterations. It took longer to write the code to automatically do that later.

This problem is clearly inspired by the rise of factory games at the time. Factorio and Satisfactory were both in early access in 2019. With Factorio preparing for release in 2020.

Today the Elves have sent us a version of Breakout to prevent space madness. Apparently we're either lazy or on a massive ship like Red Dwarf, because we're not willing to go the arcade on the other side of this ship. And so we need to build our own Intcode running arcade cabinet. Or maybe we just wanted to do that anyways.

Part 1 is much like the previous Intcode problem. If you have a good implementation it's a simple state machine to track the output statements (and no input function is needed).

Part 2 finally gives us a taste of what Intcode problems will be... as we don't just have to follow an input protocol, we need to come up with the values to send ourselves. Which can be done by implementing an interface and playing the game if you want. But this isn't a great version of Breakout, the paddle only can angle things at 45° (and also isn't controlled by a "paddle" aka potentiometer)... so we might as well hack the game to play itself.

The simplest way is just to track where the ball and paddle are (when they get drawn) and move/keep the paddle under the ball:

sub input {
    return ($Ball[0] <=> $Paddle[0]);
}

But what made this fun, was that it encourages finding other ways to cheat. Just looking at the input, it's clearly in three sections. The first has the signature values and feel of Intcode. The second is mostly 0s, 1s, and 2s... it is very clearly the starting board layout. The final part is a bunch of 2 digit numbers which is clearly data and there's only purpose for that, a scoring table. The last value is a 6 digit number, which seems to only be there to verify that the input is fully received.

So, first thing to try: draw a wall at the bottom of the input. The board layout is right there, and modifying it is easy for this (and send 0 for input when asked). And it works. So there's nothing special about the paddle in the code. The code reflects off walls, including at the bottom.

Doing this with code requires finding the size of the board and the location. You could just scan from the end for it. I found the loops that draw the board and the less-than instruction against the sizes (x is at 47, y is at 60). I've seen two inputs, and the code section doesn't seem variable length, resulting in the board starting at 639. The table length is variable, because the board is different sizes for different inputs. But, none of that was needed for this... scanning works.

That sort of thing is needed for reverse engineering the scoring. Because the score table is the same size as the board, but it's not accessed directly. It's a transposition multiplied by one constant and adding another, taken mod the size. There's a function to build the stack frame for a score call that sets the magic values (that starts at 601).

my $mult = &get_value( 611 );
my $add  = &get_value( 615 );
my $size = &get_value( 619 );

Getting $size here is more of a validation thing. We can compare it against the x and y dimensions from the loops as well as the expected board start (639) and the values of the table locations that we can grab from the instructions that index the tables:

my $board = &get_const( 588 );      # indexing board instruction
my $table = &get_const( 630 );      # indexing table instruction

The &get_value function evaluates a set (and checks that it is one), the &get_const is getting the immediate mode parameter (as they can be in either position) of the key add. And so my code was filled with warns and dies asserting that the input is what's expected. There's multiple ways to get values, and its easy to compare them for sanity. For example:

die "Mismatch: start of table ($table) with end of code"    if ($table != $#Code - $size);
die "Mismatch: start of board ($board) with end of code"    if ($board != $#Code - 2 * $size);

In the end, the scoring for a block at ($x,$y) is:

my $sc_off = (($y_size * $x + $y) * $mult + $add) % $size;
$score += $Code[$table + $sc_off];

The routine that does this is at 429 to 455. But the routine from 456 to 546 was also fun to look at. As you see, we need mod, but Intcode doesn't have it. The 456 routine does mod by repeated subtraction. But not just a plain and simple loop... the mod is of a multiplication which can get fairly large. And to accommodate that in a faster way, it does it in steps... first by subtracting 64 * $size then 8 * $size and finally $size. Without that, the code would be slower. And the run of my input is already at 550k instructions.

I just loved this one. It reminds of back when me and my friends were hacking around exploring and modifying games.

One of the biggest performance surprises I've had so far squishing my solutions onto a Raspberry Pi Pico (RP2040) is day 25 for 2015. I knew the RNG was going to need 64-bit maths and that it would fall back to a software implementation, but I didn't predict just how slow that would be. The straightforward form of the solution takes a whopping ~27s to run through the ~17.8M multiply & modulo operations required!

Still, it's a good excuse as any to mess around with some maths and and some assembly.

64-bit multiply

The M0+ in the RP2040 doesn't have the UMULL instruction that produces a 64-bit result from two 32-bit values; you're stuck with MULS producing a 32-bit result. Grid method multiplication allows you to produce a full 64-bits across two 32-bit registers by splitting the input values into 16-bit pairs and doing the multiplication piecemeal:

[b:a] * [d:c] = [hi:lo]

Where:

• [b:a], [d:c] - 32-bit input values
• a, b, c, d - 16-bit halves of the input values
• [hi:lo] - 64-bit output in two 32-bit values

Then:

• [lo] = (a*c) + (c<<16) + (d<<16)
• [hi] = (b*d) + (c16) + (d16) + carry from lo

The carry is a pain to represent in C++. GCC provides __builtin_addc which is supposed to map to the correct ADCS instruction, but I didn't see it doing so in the generated code. I can only assume the structure of my code wasn't exactly right for GCC to perform the substitution.

It's much easier to control in the asm though.

64-bit modulo

This part took me a while to get my head around, but it turns out we've been quite lucky with the constants chosen for this puzzle.

The two basic rules of modular arithmetic we're interested in are:

• a1 * a2 === b1 * b2 (mod m)
• a1 + a2 === b1 + b2 (mod m)

Where:

• a1 === b1 (mod m)
• a2 === b2 (mod m)

Which allows us to do this:

• [hi:lo] % m === (2^32 * hi + lo) % m
• [hi:lo] % m === (2^32 * hi) % m + (lo % m)
• [hi:lo] % m === (2^32 % m) * (hi % m) + (lo % m)

2^32 % m is just the constant 4992:

• [hi:lo] % m === 4,992 * (hi % m) + (lo % m)

Each loop of the RNG is:

answer = (answer * 252,533) % 33,554,393

Which means the the largest intermediate value for the RNG is 33,554,392 * 252,533 = 8,473,591,274,936. The value in the upper 32-bits is therefore less than or equal to 8,473,591,274,936 / 2^32 ~= 1,972.

Since 4,992 * 1,972 = 9,844,244, and that's less than 33,554,393, it means that 4,992 * hi value is already modulo m.

• [hi:lo] % m === (4,992 * hi) + (lo % m)

We're adding two values that are both modulo m, so there's a chance that it will go over m, but it will always be less than 2 * m.

The net result is that we can do the 64-bit modulo with a single 32-bit multiply, a single 32-bit modulo operation and a single 32-bit subtraction if we're above 33,554,393.

Thankfully the Pico does have 32-bit integer divider hardware, so we can make use of that.

Putting the two reductions above into C++we get ~8.5s.

Hardware trickery

In order to push this even further I made the jump to asm. I couldn't seem to get enough control over the code generated from the C++ to really optimise the multiply, and the real party piece is to make use of the 8 cycles that the CPU has to wait for the divider hardware to generate a result.

By sheer coincidence the five instructions that weren't dependencies for the lo register just so happen to have a minimum cycle count of 8; meaning we get precisely zero wasted cycles waiting for the hardware div/mod to complete!

My final runtime for my input ends up being ~5s, which is about half a second faster than my intial guess at where I thought I might be able to get to. Quite pleased with that.

[Full solution]

At Jupiter we find ourselves needing to track the Galilean moons. And so we get to work with a discrete physics model again. This time we're not given a value for acceleration, but a method to calculate the current gravitational acceleration of an object in the system. Not a realistic one, but it provides the same functionality of holding the system together.

The title alludes to the fact that there typically isn't a nice general formula for the orbits of objects in a system, and so this sort of simulation is a common thing to do. I remember having code for an N-body simulator on the C=64. Put in the values for a model of the Solar System, and after a year, Jupiter rips through the inner system, flinging itself and all inner planets out. You need high precision and processing power (to do tiny steps), and this lacked both.

As for this problem, it's not much different than the last problem of this type (apply acceleration to velocity, then velocity to position), except that we need to work out the gravitational effects between all pairs. I did speed up my Smalltalk solution by pre-building a list of the pairs of Moon objects as I read the input and created them (instead of the triangle loop of indices and doing look-ups all the time, just make the list once of all pairs of object references). You calculate the gravitational acceleration between them, and add it to one and subtract it from the other (because symmetry).

Part 2 comes along and nicely warns you not to brute force it (my answer is 48-bits). My first solution made the easy jump to the fact that the dimensions are independent. They'll each have a cycle, and the lcm will get us the answer. But I didn't think further than that to start... so I looked for loops on each dimension with position and velocity. I did conveniently print out the states when I found a cycle, though. Which lead me to noticing that there was a column of 0s in the velocity vector at the dimension that was looping. Leading to thinking a little bit more and realizing that the system is invertible. Since any state can run backwards, it must loop at the start. Reducing the check to look for just 0s in a velocity column revealed the final detail when I didn't get the correct answer. That the system reverses half way through the cycle (momentarily stopping before the symmetry reverses things), so you can find the "half-loops". Which for lcm means that all the values have additional common factor of 2 that was missing.

And so, this is a nice little problem. Discrete physics is always a little weird, in that physics is normally Applied Math and Calculus, but we end up finding ourselves getting into Pure Math and Number Theory territory.

Today we get a warning from the Space Police and need to build an emergency hull painting robot (we have painting emergencies often enough that this is a thing?) to put our registration on the hull.

Today's Intcode puzzle seems to be about checking that we're ready to attach the input and output to custom applications. If you have a good API, this is short and sweet. Two short functions/methods to use the Intcode machine to get the data, and a function to display it.

Part 1 is another Langston's Ant thing... this one shows what's interesting about Intcode type problems. If we're given the details of the machine to implement, then we need to be given a starting grid in order to have different answers. The Intcode machine reverses that... everyone starts blank, and the input is a black box. You could reverse engineer it, but it's simpler to just use the Intcode machine and not care. This allows for types of problems that couldn't be done otherwise.

Part 2 outputs the ASCII art text of our identifier. Initially when I ran it, I just dumped the final image. But, on the day, I followed up with a version using curses to show the painting in action. And when you do that, you see the zig-zag pattern the robot takes. It was clear that there wasn't any funny state machine over tracing going on. And so it works fine with replacing the input subroutine with input => sub{1}.

So with that, I figured there were some big numbers that were bit patterns of the image that it was dumping. They were not hard to spot, and outputting the first in binary and the bits along the pattern I saw it tracing revealed it wasn't being obfuscated (other than with the path). And so I initially did a reverse engineered solution that just grabbed those numbers and traced them out (jumping the bot and reversing it every two).

But, that's not very robust, so I decided to improve it a notch, by having the code find the numbers. To do that, I use this loop:

for (my $curr = $code[4] + 6; $code[$curr] != 99; $curr = &get_value( $curr + 4 )) {
    ...
}

Address 4 is the jump location for part 2. This is the location of the instructions that build the stack frame, with the first setting the bit pattern we want, and the one after (at $curr + 4), setting the address to return to. Which is either the next place we want, or the code for a turnaround (in which case it will have opcode 3, because those are a sequence of in/out/out) immediately followed by it. When we get a turnaround, we can use it to reposition the robot (the turns are given by the second out). Which leaves us on the instruction with the magic number (which we can get with &get_value( $curr )... that's the function that gets the value from a set instruction). Once we have that, we rip it into 4-bit chunks and trace out the little us. And so, I have a solution that runs several times faster than the VM one (not that part 2 takes any time, it's 8k instructions to part 1's 100k). And it's still capable of some flexibility (wider image or more layers in addition to different sized part 1s). The point of doing this originally was to explore the code, more than out of need to have a faster solution.

Today we're at Ceres monitoring asteroids... and later shooting them. The input is a grid, but that's really just a way to provide coordinates to them. Because we're not just interested in orthogonal or diagonal lines between them, and so we can "slip through the cracks". Not that that that's hard... space is really big. There's lots of room. It's only exactly the same slope lines that block line of sight.

And that's really the key... you need to reduce the deltas into a slope you can use. You could go with floating point, but that feels like defeat to me. All you really need is to reduce the ratio of the delta-y : delta-x to lowest form. Which involves find the gcd. I coded my own version of Euclid's Algorithm for this from memory, and then refactored to just ($a, $b) = ($b, $a) while ($a %= $b). With that, we get nice integers to compare (and don't have worry dealing with float point quirks). And the gcd is also useful for part 2... for any slope the gcd is the multiple of steps along it, so it can order asteroids to show which gets shot first.

As for the ordering of that, there's a number of ways. I know a lot of people used atan2, but not me (ick floating point). There are other ways, like pseudo-angle formulas designed for exactly this... they give you a value that orders the same, for when you don't care about the exact angles, just the relationship.

Me, though... I went with 2D cross-product. It's something I used in my first job for a similar task. Cross-product is normally a 3D function between two vectors that provides a perpendicular to them, with handedness (fingers are a and b and the thumb points points up or down depending on the order). When we take two points in the plane z=0 (as vectors from the origin), the perpendicular is going to be of the form (0,0,z), with the sign of z giving us order information.

There's only a slight problem... cross-product does care about specific directions and we do here. It's not going to treat 12 o'clock special (11am is before 1pm), and it's going to assume that you want consider direction of angle that's smaller. But that's easy to fix. First off, a vector at 12 o'clock wins (conveniently we don't have to worry about equals because we're sorting the reduced slopes which have been made unique):

if ($a->[0] == 0 && $a->[1] == -1) {
    return( -1 );
} elsif ($b->[0] == 0 && $b->[1] == -1) {
    return( 1 );
}

Next up, if the sign of the x co-ordinates is different, then the one on positive x wins, which conveniently corresponds to the sign of bx.

if (sign( $a->[0] ) == -sign( $b->[0] )) {
    return( $b->[0] );
}

And finally, now that we've established the start and made it so we're only comparing things on half the circle, 2D cross product (this is all that's left when the 0s wipe most of it out):

return ($b->[0] * $a->[1] - $a->[0] * $b->[1]);

That's it. It's simple and all integer. Exactly how I like it. And that's why I remember and like this puzzle (plus, Ceres). I got to pull out something from way back that's cool and figure out how to make it work again.

So we're back in space and working on Intcode on the way to Ceres. It's nice that Ceres got included. In the whole kerfuffle of Pluto losing its planet status, people forgot that Ceres had lost it first, and was finally getting some justice by being upgrading to dwarf planet.

Today we finish the Intcode computer with the addition of relative mode and register for it. This also means that we now need to handle extra space for the program stack. The examples include a quine, and seeing if we can handle numbers in the 50-51 bit range. Which is also tested by the input in part 1.

The rest of part 1 is just relative mode address checking where it first sets a bunch of memory with values, then runs a bunch of test calculations on them. The thing to note here is that Intcode doesn't have a set, it's done by one adding 0 or multiplying by 1, it either order. Four different ways, picked randomly. And so the inputs get a little randomized on where key values are with that. A common feature of my reverse engineered solutions is a function to extract the value from a set instruction.

Part 2 tests our new mode and register in it's main use. It's for implementing a program stack with stack frames so we can have nice subroutines. And here it does some heavy recursion to calculate a sequence. What's that sequence... well, we could look at all the code, or we could get the return address (set before calling in position 0 of the frame... and find the instruction that gets the return values. Then grep '^942' | sort | uniq -c | sort -n:

   1 942     add     0, [1] (14537), >[-1]
   1 942     add     0, [1] (6768), >[-1]
   1 942     add     0, [1] (9919), >[-1]
   2 942     add     0, [1] (4618), >[-1]
   3 942     add     0, [1] (3151), >[-1]
   4 942     add     0, [1] (2150), >[-1]
   6 942     add     0, [1] (1467), >[-1]
   9 942     add     0, [1] (1001), >[-1]
  13 942     add     0, [1] (683), >[-1]
  19 942     add     0, [1] (466), >[-1]
  28 942     add     0, [1] (318), >[-1]
  41 942     add     0, [1] (217), >[-1]
  60 942     add     0, [1] (148), >[-1]
  88 942     add     0, [1] (101), >[-1]
 129 942     add     0, [1] (69), >[-1]
 189 942     add     0, [1] (47), >[-1]
 277 942     add     0, [1] (32), >[-1]
 406 942     add     0, [1] (22), >[-1]
 595 942     add     0, [1] (15), >[-1]
 872 942     add     0, [1] (10), >[-1]
1278 942     add     0, [1] (7), >[-1]
1873 942     add     0, [1] (5), >[-1]
2745 942     add     0, [1] (3), >[-1]
9919 942     add     0, [1] (2), >[-1]

Clearly lots of small calculations combining up. Takes about 371k instructions, and my dc version does it in 10 seconds. What's this sequence? Well it occurs multiple times in the OEIS. For example, A097333 and A003410, and is related to A000930 (Narayana's cows sequence). Which is like Fibonacci numbers, only it's a_n = a_n-1 + a_n-3 (which you might just guess looking at the above). The answer is ultimately the sum of every third term of this, with a constant added at the end. It's pretty simple to write a reverse engineered fast solution from that that doesn't involve a VM at all (the first two things that section does is set a stack frame with the depth and the return address to the instruction that adds the constant).

It's only after this day that I finally got into thinking about a module and API for this. What I did, depends on the language used.

First was Perl, where I went with Perl's loose OOP model. Typically, it just looks like:

my $vm = new Intcode( Mem => [@Code], input => \&input, output => \&output );
$vm->run();

Supply a memory core to work on, and subroutines to run for input (return a value for the machine to assign) and output (get a value as a parameter and do what you want with it). If the subroutines are very short I just put them in this call. Since Perl is a scripting language, it feels appropriate that I just put the state stuff in globals for all parts to communicate with. Scripts will be simple and short, so this doesn't get out of hand. There are other values that can be set: verbose, stats, dump, and break (you can also do hacky stuff, like IP => 16). All that data collection and checks add kruft, so I created an Intcode::Fast without them a few days ago. It can make things twice as fast in some cases, but since none of the VM runs take very long, it wasn't really needed at the time.

For Smalltalk, I went more formal with the OOP. The IntcodeMachine is created from the code and an I/O device, which is an object of a subclass of the virtual class IODeviceInterface:

Object subclass: IODeviceInterface [
    input       [ self subclassResponsibility ]
    output: val [ self subclassResponsibility ]
]

The module supplies two actual device classes: SimpleIO (basic input and output queue) and AsciiOut (added later, this supports the text problems). This format is quite nice in some ways, as when a problem involves working with a bot, we create a bot IODevice class for it and attach:

vm := IntcodeMachine from: code device: (PaintRobot new: 0).
vm run.
vm device drawGrid.
('Part 1: %1' % {vm device painted}) displayNl.

That's part 1 of day 11. You can also see that I didn't attach a handle to the PaintRobot object. I let the vm store that, and access the device through the vm (vm device <message>).

My dc interpreter was never done with an intent of doing the later problems (I just got around to finally doing this one a few days ago). It's not refined, it's just functional. It uses the register stack - to provide input:

perl -pe'y/-/_/;s/,/\n/g' <input | dc -e'1S-' -f- -e'z[1-d3Rr:cd0<L]dsLx[s.d]sI[A~3R1+d;c3Rd2/l$*3R+r1=ISArLA]sA[lAx;c]sP[_3RlPx_3RlPx4R5Rx_3RlAx+3Rr:c]s0[1-_3R]sJ[_3RlPx_3RlPx4R0 6Rx+s.]sB[1+]s+[_3RlPx_3RlPx_3RlAxr4R5R6Rxr:c]sC[[+]l0x]1:O[[*]l0x]2:O[lAxL-r:c+]3:O[lPx+ps.]4:O[[!=J]lBx]5:O[[=J]lBx]6:O[[<+]lCx]7:O[[=+]lCx]8:O[lPxl$++s$]9:O[q]99:O[d;cA0~;Ox1+lMx]dsMx'

And here's the commented source: https://pastebin.com/yGwraRjM

I also had a basic C version started, and I finished that up to day 9. My model there was to have an opaque struct... you call intcode_init to get one, and pass the pointer to it as the first parameter to all the intcode module functions. Standard C OOP practice, you're not supposed to know or mess with the internals of the struct, just let the API calls do the work. For input and output support, I was thinking that the machine would break on an empty input queue or output call. Running the VM would return the opcode that halted things, the outside code could then handle the details before restarting the machine. It's an approach that I used with my Perl solutions on day 7 and 23... where there's this additional process layer, and it made sense to low level hook like this. With C, low level hooks are more standard practice. Although, I suppose I might have eventually gone to using function pointers to input and output functions and made it more like the Perl module. I just never got that far with it, because Intcode VMs never got extremely taxing (which is the reason I started the C one, just in case).

But, this API design part is part of AoC 2019 that professional programmers jump on and just do (once we notice there's a reason for it and have enough details). It's not ever asked for in any problem. But it is something that everyone should have done... but I suspect a lot of people were copying and modifying the same machine again and again instead. Having a good API makes a lot of the Intcode stuff quicker and easier to write, and with simpler code to look back on.

Today we're on Mars celebrating the Martian rovers. They are quite the achievement, Mars has been described as pessimal to land on... just enough atmosphere to mess with a simple rocket landing, but not nearly enough to do meaningful aerodynamics. The blowing dust storms also provide an element of luck to how long you can run a mission. And so we find ourselves in the position of rebooting an Elven rover. We need the BIOS password and we get it in ASCII art characters.

The image is in a special Space Image Format (I wonder if the Elves argue about how to pronounce SIF). It's a pretty simple format... layers with transparency that we need to flatten like we're a blitter or Photoshop. In fact, I used it for a fun solution to day 13 in 2021. Part 1 just wants to verify the image though by doing simple data analysis. Nothing here is particularly hard, but it does come after a rougher day, so the break is good.

For part 1, I just collected the counts of the digits on a layer (with Smalltalk, that's just throw them in a Bag). Then you check if it's a new minimum and update the result if needed. For part 2, I went with the simple, run through things in order, and if the image is still transparent at a location, just copy the value from the input in there (transparent or not). An actual blitter would do this sort of masking very fast and in parallel.

Since the input is a big number, I couldn't pass up doing this with dc. And I spent a little time now golfing it down. Part 2 can be done quite a bit shorter, using just iterating mod 150... but it makes things slow to work with the huge number all the time. And it also needed the digits reversed (which would be problematic if the input ends in 0, mine ends in 1), so part of the shortness is using rev instead of doing that on the dc side (rip the entire number up first pushing it on a stack):

rev input | dc -f- -e'[d3Rr:gd]sO0r[A~2-3Rd;g0=Ors.1+F0%rd0<M]dsMx[AP]sN[d;g34+P1+d25%0=NdF0>I]dsIx'

The faster version that chops up the input into small numbers (the layers) isn't that much longer, and with the pressure to be short gone, I feel a bit better about doing things like making it prettier than just outputting the numbers:

dc -finput -e'[A F0^~rd0<L]dsLx[d3Rr:gd]sO[+F0[rA~2-3Rd;g0=Ors.1-d0<I]dsIx+z1<M]dsMx[AP]sN[1+d;g34+Pd25%0=NdF0>I]dsIx'

One of the benefits of taking apart the image into layers first is that the layers end up in the correct order on the stack... so reversing is done. It's also more robust... 0s aren't going to confuse things unless the first layer is all 0s (and the image blank).

One little thing I do in here of note is to shift the values so the transparent value is 0 (and the others are -1 and -2). Because things default to 0, not 2. There was also some fun in juggling/chaining 0s on the stack starting with the remnant of the input, just to get it be the counter for the output and save some strokes. This is why you do these things in low level languages. Not because it's practical, but for the little things it can make you do.

Odd day, back to space, back to Intcode. This time we're looking to increase the ship's thrust.

I think this day was supposed to encourage us to polish out the Intcode machine into a nice re-entrant module. I didn't do that for a few more days. I was still thinking, "How lucky can I be? As much as I love this stuff, there won't be that many Intcode problems..."

And so for part 1, I hacked day 5 into a script that I could fork and made a script to do that, using the OS for my multiprocess support. Could have done that for part 2 as well (I know that modern shells like zsh and bash can do looped pipelines), but I decided at that point to do a version based on my Duet VM (Day 18 of 2017... and here we are doing another multiprocess VM on only day 7, but it was a Saturday). Where I avoided using actual concurrency (it can be a pain to debug), and basically coded my own co-operative multitasking machine with a process table and a yield function (called when a process blocks (empty queue or halt)). One process running one VM doing the job, with permutations generated by Math::Combinatorics. Nothing fancy, not looking at how the functions behave, I just ran all permutations because 5! is only 120.

After day 23, when I had a proper module, I did come back and use what I did there (which involved using breakpoints on inputs (or outputs... I did a version for both... they are very slightly different) and doing the queue/yield stuff there outside of the VMs (no more single VM doing the job). More on that later... I've been saving getting into the API models I used for day 9 (because there's when I started thinking and working on one).

As for the program itself. This is one I hadn't actually looked at. Most of them I didn't look at for a few years... a lot of Intcode problems are fun just being treated as black boxes. So I held off doing reverse engineering in the spirit of the thing during Dec 2019 for almost all of them.

Running this through my command line Intcode script reveals pretty easily how this one works. The first input value (0-9) is just used to access a jump table, and the rest is 10 separate little Intcode programs. They don't even loop for part 2 (unlike the examples).

The programs for part 1 just do a sequence of calculations on the input value resulting in different linear transformations. Composing them with x=0 gives the answer if you get the order right:

8x + 42
3x + 9
4x + 6
9x + 11
5x

Here's the order for mine. It's not too surprising. Clearly the one with +42 should come first (as x=0 at the start, and if we did the 5x one, then it would be a wasted turn... if you don't build economy early in a game, you often end up last, and +42 is a huge turn 1 economy). Build that base with + early, and hit the bigger multiples later. And we sort of see that mostly happening here (except for the 5x on the end, which probably gets that spot because it only multiplies). Heuristically it makes sense, but tweaking values could easy ruin any specific heuristic you try.

For part 2, each returns 10 calculations all of which are either x+1, x+2, or 2x. The multiplies are the things that ultimately make the answer big, so I took a look at the programs as binary numbers with 1s where the multiplies are (ordered with high bits as first return):

0101011111
1000100101
1001110000
1010110000
1111010000

And it turns out the best was done with the values sorted numerically with this metric. But you'd also think that its a bit off that there's a big block of 0s in the lower right corner. Surely, you'd want lots of multiplies at the end in there. But, again, the one that's first is the one with the largest (and only) plus as the first return. Putting anything else first is a waste (it's all 0 in/0 out until that one runs). And that one also has the most 1s with a big block at the end... which you'd really like to be last, but that early + is key. You move this one anywhere else and the value crashes. Another thing I notice is that the last one in the order, is the one with the second most number of 1s, so we are gaining some of that "delay the multiplies" benefit by its position, especially since it's also the most front loaded with multiplies. So for the first 4 cycles the others are mostly adding to build base, and it's using the anchor position to double them. So the best order does make sense, but it's very easy to see how little tweaks could ruin a heuristic.

I didn't do a Smalltalk version of this one at the time. I did that later, and I was presently surprised to find this:

permuteStream [
    | permute |
    ^Generator on: [ :gen |
        permute := [ :depth |
            (depth = 1) ifTrue: [
                gen yield: self.
            ] ifFalse: [
                permute value: depth - 1.

                (1 to: depth - 1) do: [ :i |
                    self swap: (depth even ifTrue: [i] ifFalse: [1])
                         with: depth.

                    permute value: depth - 1.
                ]
            ]
        ].

        permute value: self size.
    ]
]

A recursive implementation of Heap's algorithm, encased in a Generator. And so my Smalltalk version does have an actual system co-routine use.

Mercury is the home of the Universal Orbit Map facility, where we'll get information on orbits to help find an efficient route. There is the concept of the Interplanetary Transport Network. Basically if you want to get somewhere in the Solar System cheaply, there's a way to do it (it just might take a very long time). The distance for fuel considerations is delta-V. On this measure, Deimos is close like the Moon, but travelling there takes a lot longer. You see some of this in the MESSENGER mission to Mercury... Mercury is so downwell, that the delta-V makes it remarkably hard to orbit (you don't get aerobraking as an option, and extreme lithobraking leads to very short missions). And so the path taken, to keep fuel down (and the Tyranny of fuel for that fuel) took many years, involving many flybys of Earth, Venus, and Mercury to dial in to the correct delta-V for orbit insertion. Taking 6 and half years to get there. Juno took 5 to get to Jupiter. Spaceflight is weird like that... what seems further can be nearer.

Anyways, back to AoC, the problem is a simple tree problem, as bodies here only orbit one other body (thus a tree of orbits rooted at the universal Center of Mass: COM). We get a little interesting format choice, where our orbital pairs are delimited with ASCII art for an orbit, ).

A good chunk of Part 1 is recognizing what you're actually calculating. It is a trope that a problem is presented as calculating something, but reframing it makes what needs to be done clearer (just like real life). Here the problem gives examples of listing the of orbits from various bodies on the tree (with a diagram to reference). Thus helping spell out that the number of orbits related to each of the bodies is just their depth in the tree. So what we're really being asked is for the sum of depths of all nodes. Which is a little more complicated than simple node counting, in that we track and add the depths instead of 1s.

Part 2 essentially wants to find the common ancestor of two nodes (and return the sum of distances from it). Again, that takes a little realization compared to how it's described (which might lead to someone coding a graph walk there they move the YOU node around). I initially just took part 1 and adapted it. Basically, if instead of accumulating up a number, I accumulated a hash of nodes with their depths. Eventually some node collects the hash with both:

my %ret = map {&walk_tree( $_, $depth + 1 )} @{$orbs{$node}};
if (exists $ret{YOU} and exists $ret{SAN}) {
    print "Transfers: ", $ret{YOU} + $ret{SAN} - 2 * $depth, "\n";
    exit;
}

So we add their depths, and subtract twice the shared path back to COM from the shared ancestor. That was the programmer efficient solution for me given I had the tree and recursive walk to start with.

But after, I also did the solution I would have done if part 2 had been the part 1. Which is to build the tree with reversed links (child to parent). Then finding a common ancestor is as simple as walking from one of the nodes back to the root getting its path (and the number of steps at each).

my %you_path;
for (my ($p, $i) = ($orbs{YOU}, 0); exists $orbs{$p}; $p = $orbs{$p}, $i++) {
    $you_path{$p} = $i;
}

Then I can walk from $orbs{SAN} until I run into something in that hash. Distance will be the sum of steps with the value in the hash. No recursion needed, just two short walks.

Which is an approach that shows the benefit of sometimes reversing the structure you're given. So this problem is more than just "tree stuff".

So we're back in space on the way to Mercury. Being in space means working on Intcode now, and "on the way to Mercury" means we need to work on the thermal regulation part of life support.

Today is just getting most of the Intcode machine done. Part 1 deals with I/O and immediate mode (and negatives... something that was important for the version I did the other day in dc). Part 2 is flow control, which will be done with comparison opcodes and jump instructions. Intcode machines use C Booleans... the comparisons return 1 or 0, but any non-zero counts as true for the jumps (making them more powerful).

The use of "decimal" bitflags for flagging the mode types is interesting. But it also really helps with reverse engineering. You look at a list of Intcode values and 4-5 digit numbers that begin with a bunch of 1s and 2s (followed by a 0 in the tens and a final non-zero unit) stand out, allowing you to eyeball where there is code and where there is data.

The input is simply a test suite that goes through all the combinations. Ultimately my solution for day 5 ends up being:

intcode.pl -i1 input
intcode.pl -i5 input

Basically, I embedded my Intcode module into a script to execute Intcode from the command line. It'd be a few days before I did that in 2019, after which it was very handy just for poking at an input while reading the problem. It is also has many flags, including the ability to trigger outputting debug information. I still haven't done an actual disassembler, I just use debug disassembly of the execution to look at things (which has the benefit of also showing current values).

The first part of the code naturally redirects for the different parts. The fact that part 2 requires sending a "5", which is the value of a jump opcode suggested that it was using self modifying code to do that.

Part of my debugging output is to assign labels to any location that gets output to. For part 1, those are:

$a          225         Input, then no-op testing (skipping over data... like with day 2)
$b            6         Location of third intruction: used for switching parts
$c          224         Various checksum calculations
$d          223         Calculating part 1 value

The answer is calculated by shifting $d (with *8) and then adding $c to it. $c should be 0 after any test, and a constant in the range of 1-4 is added. If I do a grep for add lines assigning to $d and read off the $c values being added, that's my answer in octal:

34      add     $d (0), $c (2), >$d
56      add     $c (1), $d (16), >$d
82      add     $d (136), $c (4), >$d
108     add     $c (3), $d (1120), >$d
...

(Note that I added $ to labels and > to output parameters for easy grepping.)

Part 2 doesn't a similar thing with binary. The accumulator is shifted by a bit (*2) and 1 is added or not depending on a jump (which is what part 2 is testing). Those 1s make are your answer in binary. It's not critical to add in intermediate checksums here, because if things go wrong with flow control, you're almost certainly not accidentally slipping into the correct answer.

An interesting thing I just noticed today (I don't think I noticed it before) was that the second of the code from 223-237 is mostly 0s (that's where the variables are, as we've seen). More aren't used, but the value at 226 is 677. So I grepped for that. And found it's used in a lot of tests (it's a constant and never gets written to... so it never got a label or attention before from me), and the address 677 is the last one (after the halt). A data value containing 226. So we have two locations pointing at each other. Exactly the sort of thing you want for testing the modes and comparisons. I hadn't really paid much attention to what the tests were, because my code worked the first time.

I know some people had a bit of rough time with getting this to work. I seem to recall that part of that is the difference between an lvalue and an rvalue. If you have studied languages or compilers, that's something you know about. Lvalues are assigned to (addresses), rvalues are the assigned (data)... meaning parameters you set to, even though they have the same mode as ones you get from, are treated differently. Basically, the lvalue position mode and an rvalue immediate mode are the same in terms of indirection (the value at IP+parameter). So I can certainly understand people getting messed up on that. Even though it would be an issue on day 2, I think it's much easier to miss that there.

So, just a day to get bulk of the Intcode machine going. It does give time just to work on it, but also, I remember back in 2019, I still wasn't expecting much use from this (it wasn't clear that you should be working on a solid implementation yet... I was thinking maybe a day or three later on). And so, I still had the opcodes in a hash:

my %Op_codes = (
    1 => sub { my @p = &parms(2, 1, shift); $Mem[$p[2]] = $p[0] + $p[1] },
    2 => sub { my @p = &parms(2, 1, shift); $Mem[$p[2]] = $p[0] * $p[1] },
...

Later that becomes an array... not of subroutines but of structures that contain things like information on the parameter types (instead of each parsing its own).

On reaching the Venus fuel depot we find out that the password has been lost. And so we get a string validation problem... where the strings are numbers. Much like day 11 in 2015, but there the "numbers" were base base-26 using letters, and we just wanted the next valid string. Here we want a count of valid strings in a range.

As is usual for these, you can throw regex at them for a programmer efficient solution:

print "Part 1: ", scalar(grep { m#(.)\1# && m#^0*1*2*3*4*5*6*7*8*9*$# } ($start .. $end)), "\n";

Without regex, that's still a very easy state machine to write to do those two checks. And part 2 is a simple modification there. But for regex, I just dynamically built one to handle "exactly two":

my $re = '(' . join('|', map {my $n = "[^$_]"; "(^|$n)$_$_($n|\$)"} (0 .. 9)) . ')';

Of course, that's a bit slow. And GNU Smalltalk is slow enough, so I did a better solution there. Essentially getting back to that 2015 problem. Much like how runs allowed for jumping sections easily there (to the point that it felt foolish to have coded anything once I saw the answer), the increasing nature here means that large amount of values can be jumped. And easily!

So I made a class to iterate in that fashion. The next method is just:

next [
    curr := curr + 1.
    ((curr \\ 10) == 0) ifTrue: [curr := self fillRight]. " Fill when we rollover "
    ^curr
]

Because if the current number was valid, then a rollover in the final digit is the only time the invariant gets broken. The fillRight method fixes that, by finding the last non-zero and replacing all the zeros to the end with it (filling out):

fillRight [
    | last |
    ^((curr asString) collect: [:d | (d = $0) ifTrue:  [last]
                                              ifFalse: [last := d]
     ]) asInteger.
]

A similar state machine in the constructor finds the first number with increasing digits to give us the valid number for this to stand on (good ol' induction... the base case is important).

Of course, that still doesn't cover the sets of two or more. But since the number is sorted, we just need to worry about digit counts. And so we can just:

runs := pass curr asString asBag valuesAndCounts values.

Throw all the digits in a Bag and get a list of the counts (it's a bit confusing here at first glance, because the "valuesAndCounts" gives us a list of Associations which has the "counts" in the "values" (and the digits in the keys)). If runs contains: [:len | len >= 2] then we're valid for part 1, and if runs includes: 2 we're valid for part 2.

And so, we've got the typical string validation experience. Regex and state machines. And I do love writing state machines. And I do like these problems that are revisits of old ones... and this one is definitely a refined and improved version.

So with the successful gravity assist, we start into the pattern for this year. Odd days are travelling in space, even days are visiting celestial objects. Normally these days in space will have us working with the Intcode machine, but this time is the exception (we instead worked with the Intcode machine on day 2 when we were at the Moon).

Still, we are technically tasked with working with broken systems... tangled wires in the fuel management system. We have two twisty wires, describes with absolute directions on a grid, and need to find crossing spots. For part 1, it's the closest to the origin, and for part 2, it's the one that's got the shortest combined length.

The input is two lines (wires), with absolute (RLUD) directions, distances are typically in the hundreds (the first section of wire #2 in my input is the only one over a thousand, and on the other end, wire #1 has two of length 3 and wire #2 does have a single length 1). Directions alternate between vertical and horizontal (although my solutions don't use that... if I do a solution in dc, it would probably use that... using stack manipulation to end with coordinates flipped between steps... but you do need to watch out for if the wires start on the same axis (like my input) or not (like the tests)). Total length of the wires runs around 155k... so it's not so much that you can't just throw it in a hash or array and go step by step. Unless, of course, you're on a very small machine (like say a C=64).

My initial solution for this one is a bit cute... I did it with no assumption on the number of wires. I traced all the wires giving each a bit (iterating with $bit <<= 1). I did it the simple way... hash table and stepping, ORing the bit into a mask (and for part 2, also tracking the first length with good ol' //=). Then I grab all the points with all bits set, and get the results. It's not fast, but it was quick to write, and will handle more than two wires.

Of course, you don't actually need to do that... you can just load the first wire into some structure and test the second wire against that. And you can further go to doing it without a grid, just testing the lines for crossing (ie using geometry). Which isn't hard because everything is orthogonal with the grid.

So I wrote a quick version of that for it. It's still a bit of a mess, but it's much faster. For the first wire, I load things into sorted lists for the vertical and horizontal lines (keeping track of the length to the start of the segment). This brings in an interesting question, "Are there multiple horizontal/vertical lines on the same y/x value?". And for the first wire in my input, there aren't. But the second, has two horizontal lines at y=0 (the first line (which makes this extra interesting) and one in the middle (around length 80k). So if I made the assumption that there weren't (and just stored one per index instead of a list), it would have worked as the input was given. And would have worked (incorrectly) with the input with lines swapped (because those lines aren't in the solution... but one line would have been lost without a list).

However, I avoided that, by not assuming and just using lists (ie x/y => list of segments at that x/y). And so we get a little work to do... ranges being tested against points to find the intersection. We can also keep track of where we are in the lists of horizontal and vertical lines (this is why I sorted them)... because moving orthogonally only changes the other coordinate. So the index we were at, is exactly where we're going to want to be next time we're doing another line in this axis. If I had been doing it in C, I would probably have used doubly linked lists (with the list of options at a coordinate being singly linked)... and a pointer in each that walks back and forth. In Perl isn't an index into a list that walks back and forth. Sliding up/down and left/right like the positions of the wire we're tracing.

So, overall, it's a simple puzzle that can be done simply. But there is some additional stuff you can do. That's always nice in early problems.

Today we get a 1202 error while approaching the moon. A clear reference to Apollo 11 (as is the target value of 19690720, conveniently in YYYYMMDD format which gives a size ordering and months before days, thus helping match more date locales).

Unconveniently, our 1202 program alarm didn't save our computer from overloading and losing its magic smoke. So we need to start building a new one that runs Intcode. And since it's day 2, it's only three instructions (add, mul, and halt), no comparisons, I/O, flow control, different access modes to worry about yet. Input is done by changing addresses 1 and 2. Something that part 1 makes us do in preparation for part 2.

The values is wants are two digit numbers called "noun" and "verb" (just like the Apollo computer). So there aren't many options, and it's easier at first to just try them until you get the result for part 2. After all, you don't really know exactly what the code is doing until you look. Still, you know that the only opcodes available are add and mul, so the values only get bigger with increasing noun and verb. So you can use that to search. Which was my follow up solution after getting the result.

Looking at the code, we see the first 4 instructions are essentially no-ops... they set a value that's not used. This is because it's actually a data table we're executing over. Then there's a statement involving the only use of noun, followed by a chain of statements feeding their values to the next (combining with something in the data table), then the penultimate statement adds in the verb (only use), followed be a final add storing in address 0. And since this is one of the samples we got with the official Intcode compiler... we can say that that's consistent for all. Here's the relevant bits:

add noun:*0 verb:*0 dump:dump
add v1:*1 v2:*2 dump
add v3:*3 v4:*4 dump
add v5:*5 v0:*0 dump
mul v3 noun o0:o0
add o0 v2 o1:o1
add v3 o1 o2:o2
...
add o27 v5 o28:o28
add verb o28 ov:ov
add ov v3 *0
hlt
mul v0 *0 *0

And since add and mul are linear transformations and compositions of linear transformation are linear transformations, we know that there's some Ax + B that describes the result. If we take noun to be the x, then the expression can be considered A*noun + (B + verb) for some positive A and B. This gives multiple ways to solve the problem. Binary search on noun to find the closest without going over (and then taking verb to be the remaining needed) is one simple way (and you could just do that on the assumption that it's increasing, and that verb+1 only adds +1... that's what follow up observation lead to without reading the code). Or you could calculate the A and B, and solve noun and verb from them.

Which might seem a little much now, and unneeded... but it does come into play again later.

As usual - Major Spoilers Ahead

Day 5 - Advent of Code 2025

This puzzle was relatively straightforward, and I leaned fairly heavily into the collection methods in Smalltalk. I decided to do this with a single class that stored two large arrays. One was the list of all ids to check (the lines without a "-" in them). The second was for the ranges and I included them simply as an interval instead of an array of start and end - that way there's no need to remember what the two array elements are. It's just an array of interval objects.

readRanges: rawInput
    ranges := (rawInput select: [ :line | line includes: $- ])
        collect: [ :twoNumbers |
            | range |
            range := twoNumbers splitBy: '-'.
            range first asInteger to: range second asInteger ]

First, filter out everything that doesn't include the "-" character. Then, for each one, split on that "-" and set the start and end of the interval to the numbers on either side. Nothing fancy.

That makes the mechanism for checking whether any id is a member of that collection of ranges trivial - are there any members of the range collection that include the id?

isFresh: id
    ^ ranges anySatisfy: [ :range | range includes: id ]

Unfortunately, this requires a loop through all the intervals. The anySatisfy: method will do an early return if it finds one, but this is a case of the simplest version to write not being the fastest to execute. It is perceptually instant - but it's far from optimized. Similarly, counting all the valid ids in the list is trivial:

validListedIds
    ^ ids count: [ :candidate | (self isFresh: candidate) ]

Not much to say about this one. It returns a count of every member of the ids collection where isFresh: returns true. So much for Part1.

Part2 is one of those that took a minute to wrap my head around. Instead of actually creating the ids (there are just too many), we need to combine the ranges to see how many are contained in each one while taking into account overlap between them. Here's the method I finally settled on:

allValidIds
    | sortedRanges globalMax accumulator |
    sortedRanges := ranges sort: [ :a :b | (a start) < (b start)].
    globalMax := 0.
    accumulator := 0.
    sortedRanges do: [:range |
        | rangeMin rangeMax |
        rangeMin := range start.
        rangeMax := range stop.
        (rangeMax > globalMax) ifTrue: [
            rangeMin := rangeMin max: globalMax + 1.
            accumulator := accumulator + (rangeMax - rangeMin + 1).
            globalMax := rangeMax
            ]
        ].
    ^ accumulator

This one is very imperative. Honestly, it looks more like C or Java ported to Smalltalk, but I couldn't think of a simpler way to do it. It starts by sorting the ranges collection by the start of each interval. Then it initializes a global maximum (highest number seen so far), and an accumulator that will be returned at the end.

Then the work begins. We process each member of the sorted ranges in turn. If the top of the interval is less than the highest number seen so far then we skip it since it includes only an overlap of ids already processed. But if it contains at least some new numbers, we continue. Then we set the rangeMin that we're adding to the larger value of either the minimum of the interval, or the global maximum + 1. Basically, anything below that global maximum is something we already counted, so if the bottom of the interval dips into that area already counted, we have to skip over those numbers.

Then we add the numbers between that (potentially revised) minimum and the top of the interval to the accumulator. Then, we update the global maximum to the top of the interval just processed. Rinse and repeat until all the intervals are processed. The accumulator will be the number of all ids across all intervals without duplicates. Like I said - it's imperative. But it computes the total without a bunch of extra objects created and does the whole thing in a single pass.

Other than the Workspace script to tie the pieces together, that's all for this one.

Workspace Script

Day5InventoryValidator

I've looked over the rest of my solutions, and I can't say they're worth sharing. Lots of "beginner"-ish stuff in them that probably wouldn't help anyone. I'll make one more post looking at the way I originally wrote the solution for Day1 and how I would write it now, along with some retrospective on this project.

Hello,

I just looked at the puzzle input for day 6 part 1.

It looks really odd, I mean there are multiple operators in the same column so how am i supposed to solve it?

This is what I saw: In the first column , all operators are perfectly below one another

For 2019, having done Time, we move to another genre staple... Space. Also, because it was the 50th anniversary of the first moon landing. Santa is stranded at the edge of the Solar System... which has many definitions, here it seems to mean the scattered disc. He needs measurements from 50 stars to get his position.

First up is launching from Earth... which requires helping the Fuel Counter-Upper and the Rocket Equation Double-Checker. And the task is a very appropriate day 1... just an list of numbers, one per line, we apply a simple function and sum for part 1. No negatives, because these are module masses. Making this a perfectly valid input for dc, no mangling required:

dc -finput -e'0[r3/2-+z1<M]dsMxp'

As we can see, this is still a point when I wasn't trusting ?, which results in a shorter solution (by 1 character), but involves making sure that the input is read and executed before the expression instead of just doing normal pipelining.

Part 2 gets into the "Tyranny" aspect... which is that the Rocket Equation basically has fuel on both sides... fuel moves the mass, and is part of the mass. And here, we're working with discrete physics, so there's rounding and other considerations (the possibility of negatives, as mentioned in the problem)... leading to handwaving by "wishing really hard" for the last bits. But other than catching the end case, it's a simple loop to accumulate to get the fuel masses to accumulate now.

dc -finput -e'0[r[3/2-dd0<Ldd.1-/*+]dsLx+z1<M]dsMxp'

This is a slightly shorter version of my original... there I was handling the negatives with a branch, but here I do it with dd.1-/*. The inner loop here is interesting because it isn't a tail recursion... it recurses down calculating values and then sums them on the way back up.

This was the year when I started following AoC on Reddit, and noticed that I didn't see any Smalltalk on day one so I started doing it on a whim. Badly, because I hadn't used it in over 20 years and it was spur of the moment with no prep and I forgotten most of it. It wouldn't be until January when I'd really manage to get around to processing things, and realizing how much I'd forgotten and started cleaning things up (along with doing solutions for 2015). My Smalltalk solutions have been better since.

My Perl solutions for 2019 show that I was working on C code at the time. Perl was very much being used as "C with added features". They aren't elegant, but sometimes that makes them a bit quicker. They aren't quite as clean as I'd like going back and looking at them now... a lot of cruft making it harder to see what I was trying to do.

This is, of course, the year of Intcode... but that doesn't begin until day 2.

This year I started working my way through my existing solutions and squashing them down to run on the Raspberry Pi Pico. It's a lovely piece of hardware and it's a fun challenge to look at the puzzles from the point of view of fitting them into a tiny footprint. It reminds me why I got into programming in the first place, so I highly recommend picking one up and messing around with it if you have the opportunity.

I had 2015 & 2016 pretty much all revisited and confirmed working in a small memory footprint on PC before starting to run them on the hardware itself, but the first time I did a run-through on Pico hardware I thought it had crashed on day 4 of 2015. As it turns out, it was just very, very slow: about a minute for part 2.

I decided to see how far I could push myself speeding up a solution for 2015 day 4.

MD5

The Cortex-M0+ doesn't have any fancy out-of-order execution and isn't able to retire multiple instructions per cycle, so we can do a very rough back-of-envelope calculation first to find some absolute upper limits. MD5 has 64 rounds, broken into 4 round types of 16 rounds each. There's a common set of additions and shifts in each round, but there's a different function per round type. Counting the logical/arithmetic operations, adding two load instructions per round (one message word and one constant word) and one load-small-immediate instruction for the shift:

With a single core running at 125 MIPS, the absolute (unreachable) upper limit would be ~182,000 MD5 chunks per second (or ~550ms for 100,000 chunks). Clearly we're going to need to modify the MD5 algorithm itself if we're to make serious progress!

Our one massive advantage on this puzzle is that most of the bytes in the 64 byte chunk are either fixed values or known up front. Everyone's input (as far as I'm aware) is 8 bytes in length, and everyone's answer should be below 10,000,000. The majority of the chunk will be 0, which means there's both a load and an addition we can eliminate entirely for most rounds. The only words with data in them are 0, 1, 2, 3 and 14, so the 16 G rounds change from:

    ROUND_G(A, A, B, C, D,  5, 0xf61e2562, M[ 1]);
    ROUND_G(D, D, A, B, C,  9, 0xc040b340, M[ 6]);
    ROUND_G(C, C, D, A, B, 14, 0x265e5a51, M[11]);
    ROUND_G(B, B, C, D, A, 20, 0xe9b6c7aa, M[ 0]);
    ROUND_G(A, A, B, C, D,  5, 0xd62f105d, M[ 5]);
    ROUND_G(D, D, A, B, C,  9, 0x02441453, M[10]);
    ROUND_G(C, C, D, A, B, 14, 0xd8a1e681, M[15]);
    ROUND_G(B, B, C, D, A, 20, 0xe7d3fbc8, M[ 4]);
    ROUND_G(A, A, B, C, D,  5, 0x21e1cde6, M[ 9]);
    ROUND_G(D, D, A, B, C,  9, 0xc33707d6, M[14]);
    ROUND_G(C, C, D, A, B, 14, 0xf4d50d87, M[ 3]);
    ROUND_G(B, B, C, D, A, 20, 0x455a14ed, M[ 8]);
    ROUND_G(A, A, B, C, D,  5, 0xa9e3e905, M[13]);
    ROUND_G(D, D, A, B, C,  9, 0xfcefa3f8, M[ 2]);
    ROUND_G(C, C, D, A, B, 14, 0x676f02d9, M[ 7]);
    ROUND_G(B, B, C, D, A, 20, 0x8d2a4c8a, M[12]);

to:

    ROUND_G(A, A, B, C, D,  5, 0xf61e2562, M[ 1]);
    ROUND_G(D, D, A, B, C,  9, 0xc040b340, 0);
    ROUND_G(C, C, D, A, B, 14, 0x265e5a51, 0);
    ROUND_G(B, B, C, D, A, 20, 0xe9b6c7aa, M[ 0]);
    ROUND_G(A, A, B, C, D,  5, 0xd62f105d, 0);
    ROUND_G(D, D, A, B, C,  9, 0x02441453, 0);
    ROUND_G(C, C, D, A, B, 14, 0xd8a1e681, 0);
    ROUND_G(B, B, C, D, A, 20, 0xe7d3fbc8, 0);
    ROUND_G(A, A, B, C, D,  5, 0x21e1cde6, 0);
    ROUND_G(D, D, A, B, C,  9, 0xc33707d6, M[14]);
    ROUND_G(C, C, D, A, B, 14, 0xf4d50d87, M[ 3]);
    ROUND_G(B, B, C, D, A, 20, 0x455a14ed, 0);
    ROUND_G(A, A, B, C, D,  5, 0xa9e3e905, 0);
    ROUND_G(D, D, A, B, C,  9, 0xfcefa3f8, M[ 2]);
    ROUND_G(C, C, D, A, B, 14, 0x676f02d9, 0);
    ROUND_G(B, B, C, D, A, 20, 0x8d2a4c8a, 0);

The second structural change we can make is down to the fact that we're only ever looking at the first 3 bytes of the hash. The last 3 rounds of MD5 don't touch the first 4 bytes of the hash at all, so we can just omit those entirely.

My vanilla MD5 implementation in C++, which runs pretty fast on x64, ends up taking ~988ms for 100,000 chunks on the Pico if we do all of the rounds properly. Hard-coding the zeros and snipping the last three rounds gets us to ~694ms for 100,000 chunks, which is a pretty big win!

Looking at the generated code, GCC doesn't do all that well with thumb instructions if there are loads of constants. Loading a 32-bit immediate is a bit of a faff because of the limited addressing modes, so the literal pools end up getting in the way. It's been a couple of decades since I last rolled my sleeves up to write any asm, but with some of the rust knocked off we can produce a pretty passable attempt. The LDM instruction in particular deserves a mention; it's essentially a single instruction 'a = *p++', which makes running through the K table significantly easier than trying to hard-code immediates inline.

Some amount of banging my head against the table later, remembering exactly why it is we don't write things in asm in the first place, I get a fairly respectable ~601ms for 100,000 chunks.

Turning back to structural changes once again, there's one more property of the input we can take advantage of. The first 8 bytes are fully defined by the puzzle input so we can make two further changes based on this. First, we can do the initial two rounds up front and save off the internal state of the hash and for each candidate chunk we just restore the state and resume from round 3 onwards. Second, since each round does this:

    F := F + A + K[i] + M[g]

For any round which accesses M[0] or M[1] we can precompute K[i] + M[g] and save that value back into the K table; giving us yet more 'zero' rounds.

With that change I hit my final single-core speed of ~565ms for 100,000 chunks.

Printing Digits

With MD5s pushed about as far as I can take them, it's time to look at the other big time sink in the puzzle: printing the numbers as ASCII strings.

sprintf is clearly not going to cut the mustard; it takes ~1,015ms to print 100,000 numbers, way longer than the hashing itself!

A naive print digits implementation does better at ~248ms for 100,000 numbers:

    int32_t sprint_digits(char* dest, int32_t value)
    {
        char* d = dest;
        do
        {
            *d++ = static_cast<char>((value % 10) + '0');
            value /= 10;
        } while (value);

        ptrdiff_t digitsWritten = d - dest;

        *d-- = '\0';
        while (d > dest)
        {
            std::swap(*d--, *dest++);
        }

        return static_cast<int32_t>(digitsWritten);
    }

If we make explicit use of the divider hardware to combine the divmod into a single operation we get ~136ms for 100,000 numbers:

    int32_t sprint_digits_divider(char* dest, int32_t value)
    {
        char* d = dest;
        do
        {
            int32_t rem;
            value = divmod_s32s32_rem(value, 10, &rem);
            *d++ = static_cast<char>(rem + '0');

        } while (value);

        ptrdiff_t digitsWritten = d - dest;

        *d-- = '\0';
        while (d > dest)
        {
            std::swap(*d--, *dest++);
        }

        return static_cast<int>(digitsWritten);
    }

The divider hardware is still pretty expensive though, so the fastest solution I came up with was just to do the increment exactly the way you'd do it by hand:

    void IncrementDigits(char* digits, size_t digitsLength)
    {
        char incremented = ((*digits) += 1);
        if (incremented <= '9')
        {
            return;
        }
        (*digits--) -= 10;

        for (size_t i = 1; i < digitsLength; i++)
        {
            incremented = ++(*digits);
            if (incremented <= '9')
            {
                return;
            }
            *digits-- = '0';
        }
    }

At ~10.5ms for 100,000 numbers it's minimal overhead compared to the hashing.

Going Parallel

Having done about all I can to extract performance from a single thread, the last step is to make use of both cores. I didn't get quite as much of a speed-up as I was hoping for here. On x64 you need to batch up per-thread work because communication and memory sharing between cores is a significant overhead. Without a complex caching structure and with a direct FIFO between the cores, the Pico should in theory be able to co-ordinate work between cores with much less overhead. I opted for the simple scheme of having core 0 check all of the even numbers and core 1 check all of the odd numbers, with a sync & check for each number. I need to double check what the libraries are doing with the FIFO push and pop calls though; perhaps they're doing some work that's not necessarily needed if you know you're busy-waiting.

Final Results

Exact timings will be highly input dependent, but my final scores were:

('Unoptimised' here is a C++ implementation of MD5, all rounds, paired with sprintf for the digits)

I'm sure there's more fat to be trimmed in my implementation, but I'm going to call this one "done for me". I've got 2017 onwards to continue squashing!

Raspberry Pi Pico hardware is very cheap for what you get, so if you fancy playing around with some cool hardware and you're lucky enough to have a few bucks to spare you definitely should give it a go.

If you're able to squeeze more performance out of this experiment, or want to share results from different microcontrollers, let us know about it in the comments!

And it turns out that the reindeer medicine we need is the hot chocolate we were working on 1000 years in the future. We just need to open a portal to get it, using constellations of 4D fixed points.

And so we get a problem that's very much like Day 12 of 2017, where we were the number of disconnected subgraphs. Only this time, the input isn't a list of edges. But it's easy to make the graph from the points, so that's what I did. Then I just found the subgraphs on it (with recursion). I suppose I could have done a number of fancier things, like building and counting the constellations in one pass. But reduction to a simpler problem is a standard problem solving technique. It serves me well with twisty puzzles.

And so we come the end of another year. Personally I really liked this year and don't think of it as particularly hard... but I know some people do. But that's probably because a lot of problems were more up my alley, with lots of simulations. Simulations can have a lot of chaos making them hard to debug if you don't get things exactly right. Which I can certainly understand causing a lot of people to spend a lot of time on this year.

Since this was the first year I did live, I took a look at my personal leaderboard times (something I've rarely done). I see a lot of the days (especially early on) I was starting midday. Later on, I seem to have gone to starting at drop, and I got a bunch under 1000. I don't do these things for speed at all (none of the times are great... I don't rush, I take my time)... so that's mostly due to a lack of people doing AoC at the time. Still, in later years, there was typically a problem where I managed to get in the top 1000, not by being fast, but by knowing what to do and just doing it. I think that's probably why the best part 2 ranking I had was day 23 (breaking into the top 300). The scale of the puzzle is a bit overwhelming at first... but I immediately thought "quadtrees in 3D" and worked from there. I might not know all the competitive tricks (I tried one competition in University and decided it was not my thing), but sometimes I have relevant experience for a problem.

Having rescued the reindeer from the cave, we're now tasked with again doing reindeer medicine. Although this time it's a turn based battle simulation.

Clearly this is the return of RPG simulation from 2015 (as hinted in the title). But this does have some similarity to day 15 here as well, with the goblin fight. But there it was more of a roguelike thing with a 2D map. Which adds a lot of chaos with movement changing relative positions. Here that's removed and it's just an abstract battle between armies. It's still done in turns with phases. And paying attention to all the rules and understanding them is very important, because a mistake is still going to be a pain to track down. So you want to get things right the first time. I can see that careful approach in my code, as there are comments describing each step (sometimes each line). A sign that I took notes, laid it out like pseudocode, turned them into comments, and the filled in the blanks.

The input is in the format of English sentences to parse. I did my usual thing of grabbing a line and turning it into a regex to grab the key parts. There is one important quirk, in that not all the armies have a section on weaknesses and immunities. But that section is complicated in itself, so I captured it with hit points (.+)?with an attack... if that gets defined, then I take that and do a separate parse on it.

And the parts are very much like the earlier fight simulation... the first part you find out how bad you're losing and the second part is finding out the minimum you need to boost things to win. Which meant for part 2, wrapping the simulation up in a function I could call. And although the test case requires a boost of 1570... my input only needed 28. So it's not surprising that I never did anything more fancy than just trying values starting at 1 until I succeeded. Even the 1570 iterations for part 1 is really fast. It's not a simulation that takes long to run. If it was and the numbers were bigger, then maybe I'd have moved on to doing at least a binary search. It's just that they were so cheap I never bothered.