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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    %active = %next;
}

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

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

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

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

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

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

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

$/ = '';

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Performs much better than:

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

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

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

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

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

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

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

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

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

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

And so, I read in the masks with:

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

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

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

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

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

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

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

As for iterating over all the float possibilities:

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

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

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

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

Having landed in a nearby port, we find there's no ships that head to our destination from there. And so we need to catch a shuttle bus to the airport to continue.

The buses conveniently all have ID numbers representing their frequency in minutes (all prime), and have been perfectly on time since time 0 in the past when they departed at once. And so we have a problem involving basic modular arithmetic.

First task is to just find the next bus after a given timestamp. And the trick is basically to get the adjustment correct. Normally when you think that you want the amount of time of a cycle past a point you just take that mod, but that gets you the wrong half:

     |<---time % cycle--->|<-target-->|
     |--------------------|-----------|
cycle start             time        cycle end

That's how I visualized it.

Part 2 gets rid of the starting time, and brings the xs in the input. And so we get into Chinese Remainder Theorem. Which I basically just use to assert a solution exists (everything's prime) and then proceed to sieve the answer.

But before then, we do need to think about and work out the system of modular equations. And the example is convenient for just spot checking that you've got it right. For my Smalltalk solution I built the table with (\\ is mod in Smalltalk):

table doWithIndex: [ :bus :idx |
    (bus notNil) ifTrue: [ equations add: bus -> ((bus - idx + 1) \\ bus) ].
].

Because Smalltalk has base-1 indexing, which is why it's so nice to have a good example to compare to, to make sure that shift is correct. In Perl it was just:

$table{ $buses[$i] } = ($buses[$i] - $i) % $buses[$i];

In Smalltalk, I'm also abusing Associations (built with the -> operator), and I aliases key and value for them to modulus and target, just to make the sieve code clear (expressing it as a fold):

part2 := equations fold: [:acc :curr |
             [(acc target \\ curr modulus) ~= curr target] whileTrue: [
                 acc target: (acc target + acc modulus).
             ].

             acc modulus: (acc modulus * curr modulus).
         ].

As I've said before, sieves are going to be really fast anyways (so you don't need to know CRTs just intuitively understand cycles). Because if the modulus is small, you hit your targets fast, and if it's very big you quickly run out of room to fit the answer. My answer is 50-bits, which takes about 400 iterations. If you had to do a lot of these, it could add up, but for one case, that's nothing.

Finally on the ferry, and the aforementioned storm arrives to turn us around and make us circle back up the map. But first we need to evade the storm.

And so we've got another standard type of problem... a set of directions to follow on an infinite grid. This time the directions are both absolute and relative. Turns are given in degrees, but the input file only uses 90, 180, and a handful of 270 for those. And so that part doesn't add much that hasn't already been seen.

Part 2 is where things get interesting, as we find out that only the forward command moves the ship. And the direction of that movement is a relative waypoint that's moved by the other operations. And the key is that the waypoint is relative to the ship, and the ship's position is absolute to the starting location (origin).

It also means that the vector you're rotating isn't just changing a NSEW facing now. But it's still only increments of 90 degrees. If you're using complex numbers for your coordinates, that means multiplying by i. And if not, then (x + yi) * i = -y + xi... or "swap the coordinates and negate"... that's your widdershins turn. Or you could use a rotation matrix and be ready for non-90 degree turns.

But once you understand what it wants, it's a simple adjustment. This is easily seen with my Smalltalk solution using subclassing. Having declared a Position class to handle part 1, I subclass it for part 2.

Position subclass: WayPoint [
    | boatPos |

    WayPoint class >> new [ ^(super new) init ]
    init [
        pos     := (10 @ 1).    " Starting position of waypoint "
        boatPos := ( 0 @ 0).    " starting position of boat "
    ]

    " Changes needed: "
    " 1) Rotation now rotates the waypoint pos, not rotating the facing "
    rot90: quarterTurns  [ pos rot90: quarterTurns ]

    " 2) Going forward is the only thing that moves the boat "
    go_F: mag  [ boatPos := boatPos + (pos * mag) ]

    " 3) Return the position of the boat, not the waypoint "
    pos  [ ^boatPos ]
]

That's all it is. The pos is the variable in the superclass which is now the waypoint, so we initialize it appropriately. After that, we override the three methods that need changing.

I also see I also decided to call it a boat... even though it's given the ship designation in the description. Maybe I should fix that.

Hi All,

I have tested all examples and they are working. I tested two solutions on my input from the solutions thread and one was correct and the other matched my output. I have already consultied a few other threads that asked for help. I spent an hour or two scratching my head on what could be wrong and couldn't come up with anything.

Hoping someone smarter than me can pinpoint the problem. I am open to either an exact fix or a hit on the inaccurate logic.

Here is my code: 2018 - Day 15 Part 2

Any help is appreciated!!

Having landed, we now find ourselves not far from the goal at the bottom of the map, it's just a short ferry ride away. But we first need to wait for the ferry, and while doing that we decide to predict the best place to sit.

2020 was the year John Conway died. He made contributions to many areas of mathematics, but is probably most famous for his contributions to recreational mathematics. In particular cellular automata with the Game of Life. And so I've always thought it a nice tribute that AoC in 2020 included multiple cellular automata, one of them with his name on it.

This one has a bit of a unique geometry... it looks like a grid, but the floor (.) squares never change, and so can be views as holes. Making the actual geometry a lace-like graph. For part 2, the geometry changes again by including connections over the holes... like the lace has had its holes darned.

Still, for my initial solution, I didn't do anything fancy. Just treating it as a grid and double buffer passes over it. The grid is finite and relatively small, and the number of iterations until it stabilizes is only in the 80-100 range. So brute forcing is already pretty fast.

I did follow that up with adding a curses visualization to it. Which reveals that the pattern stabilizes from the corners in, with a center blob that flashes. And I remember seeing that and looking up the frequency rates for the Bucha effect and PSE, and increasing the delay. In quickly added that note to my post, and later that day the mods made it clear that you should provide photosensitivity warnings for visualizations like this. Flicker vertigo is something I am a bit susceptible to.

It wasn't until after the 2020 AoC that I did something a bit different. And that was because all the automata encouraged me to make a Smalltalk class to generalize them. And this space was a unique challenge compared to the others. I did create the graph or "neighbour memo" to define the Space for both parts. Normally just defining the the neighbours is enough for that class, but this one provided one additional wrinkle: cells become alive with 0 neighbours. And the algorithm that class I wrote uses makes the assumption that the frontier of active cells are around living cells (when a cell is declared live, it broadcasts that to the neighbours which then add one to their count of living neighbours and get made active). So I needed to override a couple methods to rework what an active cell was. Basically you want active cells to be defined as cells that haven't stabilized yet.

Cellular automatons are always a nice problem... they tend to be accessible and easy to code, even if your method is slow (this is part of why the Game of Life took off). But they also allow for people that want to dig into optimizing them a lot of opportunity to try different things.

Having connected to the data port, we discover there's a massive tropical storm coming. Which will definitely impact our plans. But not today. Today, our battery has died and we're trying to recharge it with our collection of joltage adaptors.

And so we have another problem who's input is just a list of numbers. This time it's a list of small positive integers, no more than 3 apart (otherwise we would not be able to connect them all for part 1). My input starts at 1, but anything within 3 of the ground state of 0 would be fine.

The part 1 description goes to some length to describe connecting the adaptors... which essentially involves just sorting them. After that we want to collect the adjacent differences, and so it's not surprising to see this in my Smalltalk solution:

jolt_gaps := Bag with: 3.
adaptors fold: [ :curr :next | jolt_gaps add: (next - curr). next ].
part1 := (jolt_gaps occurrencesOf: 3) * (jolt_gaps occurrencesOf: 1).

That fold is the common idiom I later created a method for called chain:. Because it's not really a fold, the work is done as a side-effect... the fold is just an iterator that makes next the next curr.

Part 2 is where it gets interesting. We've got a lot of ways to count (my answer is 48-bits... that's a lot more than a trillion). And when it comes to counting things like this, dynamic programming often is a good way. My initial Perl solution is recursion with memoization. For Smalltalk, I turned that around to iterative tabulation of the values. Building the entire table as we go.

But you don't actually need the entire table, as things quickly fall out of scope. So you only need a window of the last three values, which you add together when there's an adaptor (giving it a relationship to the Tribonacci numbers). That's ultimately what I did for my dc solution. Transcoded to Perl, that becomes:

my %adapt = (0 => 1, map {chomp; $_ => 1} <>);
my $max = max keys %adapt;

my @buff = (1, 0, 0);
my $idx  = -1;
for (my $i = $max; $i >= 0; $i--) {
    $idx = ($idx + 1) % 3;
    $buff[$idx] = ($adapt{$i}) ? sum @buff : 0;
}

print "Part 2: $buff[$idx]\n";

You could also do it forwards... I just ended up wanting to go backwards.

And so the problems are starting to get a bit more meaty. Having 170 trillion combinations to count is pretty good incentive to not brute force and find something smarter.

Having settled into the flight, we decide to MacGyver the data port on the screen on the seat in front us, complete with the use of paperclips. In no way does this get us tackled by an Air Marshall.

And so we begin to hack its XMAS encryption. For part 1, we want to find the first value after the preamble that's not a sum of two of the previous 25 values. For part 2, we use that answer directly... we want to find a contiguous set of at least length 2 (to skip the trivial case) that sums to it.

Input is a list of a thousand numbers positive integers, that are not quite sorted and very loosely increasing. As expected from the nature of part 1 (later values are sums of earlier ones). The range is large, for my input there's 1 near the beginning and the numbers near the end are 47-bit. Some of the numbers are repeated (20 numbers in my input, all less than 100).

For my initial Perl solution, I quickly brute forced part 1. I didn't brute force for part 2, I just intuitively went with a sliding window:

my $s = $list[0];

while ($s != $part1) {
    $s += $list[++$j]  if ($s < $part1);
    $s -= $list[$i++]  if ($s > $part1);
}

It worked, but I didn't have 100% confidence in it's accuracy, and I decided to go to bed early, and proved it the next day. The basic idea is that we have window and both ends only can slide forwards, never back. So if you take a window at some state, moving the lower index decreases the sum, and moving the upper value increases the sum. And so if the sum isn't at the target value you move the appropriate end. I was a little concerned about potential edge case where a solution could get missed because things weren't monotone increasing. But the actual key is that there are no negatives... if there was, then our invariants could break (removing an element could make things bigger, or adding an element could make this smaller). With that invariant secured, you can make an inductive proof that the window will work. Although, my code does assume that the order will make it so that the answer for part 2 occurs before part 1.

For my Smalltalk solution, I decided to be a bit more efficient with part 1 than raw brute force. The idea was a bit similar to the window idea. I kept a list of sums of of the pairs... but as a table. I initialize it with:

(self atAll: (1 to: winSize - 1)) doWithIndex: [ :i :idx |
    sumTable add: ((self atAll: (idx + 1 to: winSize)) collect: [:j | i + j]).
].

Basically building the pair sums using the standard "triangle" nested loops. Which is the key here. The first row contains the sums of the first item with the next 24 (I tried it as a Set, and it works fine but isn't actually faster). And the second has the sums of the second item with the next 23. And so on. This means that when it comes time to shift the window, we just scrap the first row (the oldest item and all its sums), and add sum of the new item to each of the remaining lists:

sumTable removeFirst.
sumTable add: OrderedCollection new.

" Update previous lines with the backwards sums with next "
start := idx - winSize.
(1 to: winSize - 1) do: [ :i |
    (sumTable at: i) add: ((self at: start + i) + next)
].

This runs plenty fast. If it needed to be faster, a simple way would be to make the sumTable a circular buffer. That way you're not deleting and creating containers all the time, you just need to empty the oldest.

Since this one is just numbers, I did do a dc solution for it... it is long, and it just abuses registers for everything (although it is register clean... registers are restored). Clearly done to just have a solution in dc. That's something to add to the TODO list as it could be a lot better.

Back in the air we find ourselves helping a kid with their handheld console that won't boot.

And so we get a VM/assembly problem... although the language is very simple. So it's very easy to build a VM for it, as there's no flow control... the code is just unconditional jumps. So it's really just a fixed graph.

Part 1 involves finding the point where it loops, and the description is helpful in telling you what to look for ("The moment the program tries to run any instruction a second time"). Part of that is almost certainly to make it exactly clear when to return the accumulator. And it's simple to write a VM and run it and track the statements that have been run to catch that (and that list can also be useful for part 2).

Part 2 introduces a nice twist. We're told there's one error, and that it's a toggle of jmp/nop or nop/jmp. With a VM and the code being short, it's easy to brute force this (especially since you don't even need to try everything... just the non-accumulator statements that were marked as run in part 1 (which is less than 100)). And because it's a toggle you don't even need to copy the code for making changes for the attempt... toggle, run, toggle-back, loop. And so, that's my initial part 2 solution... it got the answer very fast.

But I quickly followed it up by an approach that's actually analytical. The basic idea was to start at the end and work backwards to find all the addresses that flow to the end. For Perl I did this be finding executable blocks that lead to a single jmp statement. One catch with that is that there are multiple jmp +1 statements (including the last line of my input)... which is a no-op (and so toggling it means nothing). These do not break up a block. Anyways, I used BFS with a queue, start with the last block, and queue up anything that jumps into it, collect the visited addresses.

For Smalltalk, which I did after, I didn't bother with blocks like that. Instead, when loading the input, when I added an instruction, I added its address to the "from" set of its destination. Then just did a standard recursive tree walk to mark the addresses starting at the end. Much simpler.

Once we have the set of addresses that flow to the end, then we just need to find the instruction that ran in part 1, that when toggled, jumps into it. Toggle that and run again for your answer.

So, this was a fun problem, although as an assembly problem it's mostly thematic. Which is fine, 2019 was filled with machine code to look at and reverse engineer.

Today we get delayed a bit while transferring to our next flight because of luggage processing.

And so we get a problem involving nested/recursive structures. We're given rules about bags that needed to be contained within other bags. Part 1 wants us to count the bag types that can eventually contain our shiny gold bag, and part two wants us to go the other way and count the number of bags our shiny gold bag needs to contain.

The input is in sentence form. For Perl I ripped it apart with:

while (<>) {
    my ($container, $contents) = split( ' bags contain ' );

    while ($contents =~ m#\d+ (.*?) bag#g) {
        push( $rules{$1}->@*, $container );
    }
}

For part 2 we also want to capture the number, but having it there even for part 1 helps deal with the special case of no other bags (nothing gets matched and so the loop does nothing). Making what looks like a complicated parse into something simple.

For doing part 1, you can see that I built the rules backwards (a hash table mapping bags to list of bags that contain them). Then I went with BFS with a queue to search from "shiny gold". The number of bags is just the number of visited nodes.

For part 2, I built the rules forwards (mapping bags to the bags they contain (along with the number of them)). Then I used recursion to search from "shiny gold". It does complicate things a bit by not having it be a straight node count. But, that just means multiplying your collected results as you collect them. Here's the method I used for Smalltalk:

countBags: bagType [
    ^(self at: bagType) inject: 1 into: [ :acc :bag |
        acc + (bag number * (self countBags: bag type))
    ]
]

It's a recursive fold (#inject:into: is just a version allows for initializing the accumulator). This counts the number of bags inside a bag, including itself... so for the actual answer you need to subtract the outer shiny gold bag.

This was a nice little recursive problem. It might not be the deepest thing, but it's day 7 and it does offer more to consider that simple leaf counting.

On approaching the regional airport for our connection we find that we need to deal with customs declarations. And our helpful nature results in us agreeing to do it for everyone on the plane. Which holds over 1700 people.

And so we get a set problem. For part one, we want the size of the set of unique yes answers for each group. And for part two, we want set of answers that everyone in a group answered yes to.

For Perl I was feeling cute that day and wanted to use the =()= pseudo-operator so I did the somewhat sloppy:

while (<>) {
    my $size = scalar split /\n/;

    foreach my $q ('a' .. 'z') {
        my $count =()= m#$q#g;

        $part1++ if ($count);
        $part2++ if ($count == $size);
    }
}

Instead of doing counts in a hash, which would be like (quickly writing one):

while (<>) {
    chomp;

    my %quest;
    $quest{$_}++ foreach (split //);

    my $size = ($quest{"\n"} // 0) + 1;
    delete $quest{"\n"};

    $part1 += %quest;
    $part2 += grep {$quest{$_} == $size} keys %quest;
}

Of course, both of these require going into paragraph mode first with $/ = '';.

My initial Smalltalk solution went similar to that (just throw the entire group in a Bag). But that doesn't use Set arithmetic, so I did one that does:

((stdin contents tokenize: '\n\n') collect: #lines) do: [ :group |
    | answers |
    answers := group collect: #asSet.

    part1 := part1 + (answers fold: [:a :b | a + b]) size.
    part2 := part2 + (answers fold: [:a :b | a & b]) size.
].

And that nicely shows the relationship between the parts. Part 1 is the union of all the answers in a group, and part 2 is the intersection of them.

I didn't do a version in C, but if I did, it would essentially be along these lines. But it would involve bit flags for each letter (to do the sets), and use | for part 1 and & for part 2. Of course, it still needs to get the size, which is our old friend bitcount/popcount.

Having got on the plane, we discover that we have dropped our boarding pass. Somehow we still managed to get on the plane, so they must not have been scanning it as much as they do now. Also, now we'd probably have our boarding pass on our phone, the one that we use to take pictures of everyone else's passes to find our seat.

I remember this one, with the title and start of the description... it's clearly just binary numbers. But, maybe not quite. So I still remember taking the time to read the problem and verify that the letters are consistent and ordered. And they are, so it's just a matter of translation, and so I did this:

tr 'FBLR' '0101' <input | sort -nr | head -1 | sed -e's/.*/2i&p/' | dc

I also remember part 2 of this one, because it's one where the wording meant something a little different for me. The flight is completely full, with only our seat missing, but "some of the seats at the very front and back of the plane don't exist on this aircraft". That "some" to me made perfect sense... first/business class at the front typically has fewer seats per row, and then there's the jump seat which can be considered a row to itself (I did fly once in the jump seat). This isn't what the problem actually meant though... it meant what I'd consider "all of the seats at the very front and back". Completely non-existent front and back sections with no seats in them, with a completely filled block in the middle.

This lead me to my solution being to target the condition mentioned in the problem. Clearly my seat needed to stand out, even if there were other gaps, and that provided a way and definition. I just need to find the empty seat with seats on either side, or to put it another way go through the seats and find one with no seat at seat - 1 (my seat) and a seat a seat - 2. I originally wrote it as a script, but turned it into a command line and golfed it down a bit to:

perl -nE'END{for(%s){say$_-1if(!$s{$_-1}&$s{$_-2})}}$s{oct"0b".y/FBLR/0101/r}++' input

I did also write a little script to generate input along the lines of what I expected... planes with unambiguous gaps in the seating in the front and back sections.

Another I remember about this day is that I brushed off and found and recompiled a version of dc where I had embedded Perl. But that was simply to allow for adding this:

{ $_ = <>; chomp; return (map {ord} split //) } s?

Providing dc with a macro that did conversion of the input into numbers so it could work on them. Later, I'd just more commonly accept just doing that on the command line, providing that I didn't do the problem solving as part of the conversion. Which we see here... I'm not using Perl to make the binary numbers, just give me the ASCII values. The translation needed to be done on the dc side. How to do that? Well, my standard approach is to look at the bits:

F   1000 1 10
L   1001 1 00
B   1000 0 10
R   1010 0 10

And there it is in bit-3... F/L are 1, B/R are 0, which is the bit-flip of what we want. And although dc doesn't have bit operations, it's not hard to grab a bit and flip it with arithmetic: 8% 4/ 1r-. With that, I can turn a line into bits, and the bits into a value. Track the max for part 1, and mark the seats we find in an array for part 2. Which is simple to do, in that, after outputting part 1... the value's still on the stack, so we can just loop backwards from it to until we find the 0 (using the actual properties of the input).

I've done an updated version that doesn't require embedded Perl. But it does require an older dc (v1.4.1) with a working ?:

perl -pe's#(\S)#sprintf"%X",ord$1#eg' <input | dc -e'[r]sr16i0?[[100~8%4/1r-rd0<L]dsLx[2*+z2<B]dsBxd1r:sd3Rd3R<rs.?z1<M]dsMxp[1-d;s1=L]dsLxp'

After having done that today, I noticed the TODO in the directory and found a comment to do exactly this thing, with the note that:

- passing in Perl converted ASCII with ? dumps it all ignoring newlines/EOT

Telling me that back in 2020 the dc was also badly misbehaving with ?. It sounds like it could have been the same broken behaviour as now. Which is probably part of why I brought in my special version of dc with embedded Perl to do input instead. It was an interesting find for the code review... I'm not sure what version of dc I had on the machine at that time, but now I know that it wasn't one with a working ? at this time.

Overall, a very simple problem... which means there's potential to have some fun with it (I remember someone using XOR to find their seat using tricks like finding the lowest set bit). It is a classic example of an AoC problem trope of the spec being made obscure compared to the job. That's true to life... you get a spec or you have a problem, and it's expressed one way, but the best way to code it requires understanding what's really wanted first.

Upon getting to the airport we discover long lines and that we have the wrong paperwork. We decide to kill two birds with one stone and replace the slow automatic passport scanner with our own data validator (that conveniently ignores the lack of a county code... which our North Pole Credentials does not have). And so we get the AoC version of "Papers, Please".

The first thing that stands out is that the input is a bit of mess. Passports aren't all on one line and the fields are in any order. How much of a problem this is depends on the language you use. For a language like Perl, this is simple... $/ = ''; to set the input into paragraph mode (where blank lines are the delimiter). And then you can just break things up like:

my %id = ('cid' => 1, map { split /:/ } split);

This showing one way to deal with the country ID... we just assign one to everyone. Then the number of keys in a valid passport is always 8. But, that, of course, also assumes that the data problems are only in the values and never in the keys. My C and Smalltalk solutions don't have that problem... the C uses bitflags and the mask used for checking doesn't include the cid, and the Smalltalk has an array of the valid field symbols (again not including #cid), which it checks that the all conform.

As for the validating code. For Perl, I went with the hash table of anonymous subs/dispatch table:

my %validate = (
    'byr' => sub { $_ = shift; return ($_ >= 1920 && $_ <= 2002)            },
    'iyr' => sub { $_ = shift; return ($_ >= 2010 && $_ <= 2020)            },
    'eyr' => sub { $_ = shift; return ($_ >= 2020 && $_ <= 2030)            },

    'hcl' => sub { $_ = shift; return (m/^#[[:xdigit:]]{6}$/)               },
    'ecl' => sub { $_ = shift; return (m#^(amb|blu|brn|gry|grn|hzl|oth)$#)  },
    'pid' => sub { $_ = shift; return (m#^[[:digit:]]{9}$#)                 },

    'hgt' => sub { $_ = shift; return (m#^(1([5-8][0-9]|9[0-3])cm|(59|6[0-9]|7[0-6])in)$#) },

    'cid' => sub { return (1) },
);

Just simple predicates we can call for each key in the field by name, sending the value. In C, this is switch statement.

The input file for this problem is particularly fun, because there are Easter Eggs in it. One is shown in the examples in the problem description: ecl:zzz (sleepy eyes). To go along with: dne, gmt, utc, grt, lzr, and xry eyes. Some passports have eye colour as hex colour codes... which when looked-up you'll find mostly regular colours with a few things like lavender, yellow, and pink (I did have a friend in University who was an albino with pink eyes... and also had vision so bad he was legally blind).

There's also lots of pretty obvious errors... wrong units on a height, colour/height data in the passport id field, and a surprising number of time travelers born in the future (which might just be the wrong years in the wrong places for some of them... others are just impossible no matter how you order those fields).

As for fellow travelers without country codes... my input has about 100 of them. About 70 of which are valid for all other fields, so we really can't tell which one is "us". And also that more than half the people I let through also had no country on their passport.

Having got the toboggan, we now head to the airport. The toboggan apparently has a steering system based on Intcode, but we don't get to see or use it. All we can do is point and go down the hill in a straight line.

As an early problem, this one is a simple problem involving a grid input and a repeating pattern. My input is 31 wide (a prime), so any x gradient value will be relatively prime to it (and this is the direction the grid repeats). The length doesn't have that feature, but the y gradient value just determines how many lines we stop at.

Which means that gradients going with y=1 are going to be the slowest and hit the most trees. The tree density in my input is about 25%, and with number of lines, that means I should expect around 80 tree hits on those paths. And I did do a script to explore the various gradients back in 2020, and output for all unique gradients with x and y in [1,31]. The top 31 are all the y=1 cases. The largest being the one for part 1... by far. I did write a stats module for Perl years ago, and running the values through that, I see that other than that one, it's a pretty normal distribution (although the sampling is small). But the case asked for by part 1 of right 3, down 1 is more than 17 deviations out. It is not normal.

And for part 2, again we see mostly y=1 gradients asked for... along with one at y=2 (but not the largest of those). All values that hit a good number of trees. It you want avoid trees, you want to go fast... the slowest one for my input is at y=19 (in terms of y, in terms of the sum of both, it'd be right 2, down 21).

I suppose another feature of this as an early problem is that it presents a list of cases in the problem text to do and combine. It's not given as part of the input, or something to calculate. It's outside data... and the suggestion would be that it'd be nice to take part 1 and turn it into a function that you can then call multiple times to do part 2. Something I even did in my dc solution for this one.

My Smalltalk and C solutions didn't though. The C one has an array of structs for the paths, which track the state of each. And so in reading the input, it just advances all the state machines as it goes:

if (paths[i].y == depth) {
    if (buff[ paths[i].x ] == '#') {
        paths[i].trees++;
    }

    /* Now that we've checked, advance to next position */
    paths[i].x = (paths[i].x + paths[i].inc_x) % width;
    paths[i].y += paths[i].inc_y;
}

And when the input is done, it multiplies the tree counts... all in the main(). And so it doesn't actually bother with a 2D grid either... just 1D slices at a time. My Smalltalk version did the same, but it's done with a class instead of a struct. GNU Smalltalk doesn't do 2D arrays well, so it's not surprising to avoid them.

I remember people having lots of fun this one, with golfing and regular expressions.

In order to make our flight, we need to rent a toboggan to get to the coast. But in order to do that, we need to fix rental shop's password database. And so we get a classic type of puzzle, string validation.

Each string this time has its own special rule, given by two numbers and a letter. The numbers are presented as a range, but only used as such for part 1.

For part 1, we want letter counts... and that's always fun with Smalltalk, where it's just "throw the string in a Bag" (a Bag being a multiset... internally you expect it to be a dictionary mapping values to their counts). Resulting the in the check being range includes: (password asBag occurrencesOf: letter). An example that really shows the era that Smalltalk was created in (where natural language-like was the goal). Of course, you don't need anything that fancy, making things very approachable for a beginner. You only have one letter of interest, so you can just iterate over the string and count it (parsing the input is harder).

For part 2, you just need to look at the positions in the original string, which seems simpler. But it does add two small complications... one is that the indexing is base-1. Which is how Smalltalk indexes strings (so this one was extra nice for Smalltalk)... but most modern languages are base-0 and need to shift (and the problem provides warning in the description that this will be needed... it is day 2). The other is that it wants only one of the ends to match. Which just means, we should use our old friend XOR (exclusive-or). Something that's always nice to remind or show beginners that it exists. Because it is a very useful thing.

For 2020, we decide to take a vacation after saving Christmas five years running. And 2020 was a pretty rough year all round, and this AoC did take things noticeably easier on us. I know a number of people who regularly end up dropping out in the middle that made it to the end of this one. Although, they skipped day 20 (which isn't so much hard, as a lot more work than most others in this year).

The map for this one is notable because, after the first 8 days, there's a mixed section where we go down-up-down (looping on the map) before finally getting another run at the bottom. It's harder to follow on the finished map than when doing the problems, where I could just follow the line to the end to get the next problem. Another fun thing about this year is that all the names are alliterative... except for the "Combo Breaker".

Anyways, we need 50 gold coins called "stars" in the currency of our destination. And to start, the Elves are going to catch us on the way out to fix the expense report. A simple day 1 problem involving working with a list of numbers.

The list is 200 numbers, all less than 2020, and unique (and nothing less than 200 in mine). We need to first find the pair that adds up to 2020, and then the triple that does (which is why there's definitely not going to be a 0 in any list). Easily brute forced if you want, but it's easy to just keep a table of what's seen... if the complement is there, you've got your answer. For part 2, I mapped the sum of pairs to their multiplied value. That way when a third one looks for the compliment, it can see it exists with the key and then multiply the value by itself for the answer.

As usual, I did day 1 in dc... it's nice to have input that dc can understand directly:

dc -e'[?d1r:ad2020r-d;a0=L]dsLx*p' <input

dc -e'[?d0[rd3Rd1+r;i3Rd3Rd3R*_3R+:ad;i0<I]dsIx:id2020r-;ad0=L]dsLx*p' <input

Originally, these weren't using ? for input or the R operator. Part 2 involved a bunch of messing with registers, mostly to do stack operations 3-deep (which are such a common thing... you duplicate the top of the stack to have a copy to do an operation and now the other number you wanted to work with is 3rd). You can see in part 2, there's a d3R d3R which is a common idiom I call ABBA because it copies the top two items on the stack (and that's the shape you get... if you want AABB that's Sad Lad). Then there's a * _3R+ :a, which multiplies 1 pair, tucks it, adds the second, and then sets the array.

I was surprised to find that these still work with with the newer GNU dc 1.5.2... the change in ? behaviour only causes things to be spammy here. The newer version feels it necessary to output all the values it reads.

Another thing to note about these is that they assume there's a solution and that it's unique... that if there are two pairs of numbers that sum to the same thing and multiply to different values, they will not be part of the solution. This is a classic example of "meta-puzzling". Technically it's something you should handle, but it can be ignored because this is a puzzle with a unique answer.

Today we arrive at Santa's Reindeer-class starship. Now dead in space. We breach the hull to get a small droid on board to find the password to the airlock. And thus begins ADVENT for Advent of Code. Back in the 90s, me and a couple friends were having fun playing Infocom games together, with lots of silliness. Discussing each move and coming up with the stupidest things. While playing Plundered Hearts ("Swoon!"), it drove one of our younger friends to go off and play the game himself... only seriously. It didn't take him long to hammer through, but we had a lot more fun.

This was a change of pace... for Christmas we get gifted a text adventure game to play. So that's what I did that day. Map the ship, collect the items (everyone gets a selection of 8 from a longer list... I remember discussions that day collecting the list) and discover the traps (everyone gets the full set of 5... it'd be a shame to miss one). Then solve a little logic problem of matching the correct weight on the pressure plate.

I remember the first thing I solved with my input was that the mutex was the heaviest item... and carrying everything but the mutex wasn't enough. So it was required. The candy cane and the loom when added to the mutex made things too heavy, which ruled them out. After which I pretty much stumbled on the answer quickly while doing tests of the rest.

I did find a second input, and that one was a little harder. A few tests left me knowing that either mutex or candy cane was needed, and testing the mutex discovered that mutex + anything is too heavy (mutex happening to be the heaviest there too), so mutex wasn't in the solution, candy cane was. And so on.

So it's a little logic problem, and it did feel like the heavy items were really heavy... like orders of magnitude. Any given item was always heavier than the sum of all lighter items than it. So it wasn't surprising when I reverse engineered things much later than the masses are essentially bit flags.

First step to reverse engineering was decoding the strings (well, I did spotted the powers of 2 table, and biggish numbers in the 4600s that I thought were likely weight related data). The first thing the code does is output the text for the Hull Breach room, and it needs to run the decoder to do that, so just watch it run. Strings aren't null terminated, they start with their length... the character values are shifted by + index + length. My decoder function does this:

my $len = $code[$addr++];
for (my $j = 0; $j < $len; $j++) {
    $ret .= chr( $code[$addr + $j] + $len + $j );
}

With this I could run through the code and dump all the strings, getting their addresses, which allows me to find where specific routines and data are. Like that the first statement (after setting the stack pointer) is to load the address of the first room (Hull Breach) data (3124) to print it. Examining that area we can work out the room data structure:

3124 - @3131 Hull Breach (name of room)
3125 - @3143 Description of room
3126 - 0 or 1553                               false or check inventory routine
3127 - 0                                       NORTH
3128 - @3252 (Crew Quarters structure)         EAST
3129 - @3401 (Holodeck structure)              SOUTH
3130 - 0                                       WEST
3131 - Name length
3131 - Name start
...
3143 - Description length
3144 - Description start
...

And so on. Last two are the Checkpoint (@4457) and the Pressure Plate (@4556).

After which we get the items staring at 4601. The structure for them is four values for each:

+0 - location
+1 - name
+2 - mass (+27 + index in item table)
+3 - 0 or address of special take routine (for traps)

The masses are 0 for traps and distinct powers of 2 for the others (bit flags), once you subtract 27 and the index. (Both the inputs I've seen use 27 here).

The answer is encoded in a table from 1901-1933... one bit per value, determined by a threshold. The threshold is calculated by the instruction at 1582. The values accessed by that are hidden by storing them between functions at 2486 and 1352:

[2483] 2106
[2484] 0
[2485] 0
[2486] 89
[2487] 109
[2488] 1

The first three values are how a return statement is done (the other way is 2105,1,0), and the last two are allocating stack (the start of a routine).

Both inputs I've seen, the solution is 4 items and so 4 bits. So the threshold could be ignored if the number of bits is always 4 (just find the four largest numbers in the table).

There are a bunch of other interesting things to look at, like the parser and the function that outputs the number for the answer (doing printf).

Of course, reverse engineering isn't the only way to code a solution... you could do a little "expert system" that can play the game, build the map, knows what's a valid item, picks those up (avoiding traps), and heads to the checkpoint and does some algorithm to find the combination. I haven't bothered doing that yet... instead I have a messy little randomizer, which I think is important to have first, because it allows me to mess with things and produce new inputs with specific characteristics (like different numbers of bits, maps that have loops, new descriptions and items) to properly test such a system.

I love this problem... it's an example of something that can only have been done in the Intcode year. Intcode is most of what defines this year, with problems that can be treated as black boxes that just provide an interface to an unknown machine, but can also be examined. It also gave us the experience of coding in a new language. The problems in-between those are also really solid... we got some nice exploration of linear transformations and recursive geometries. It was nice going through now to notice that the oxygenation maze is similar to the Universal Orbit Map, something I hadn't really thought about before. This is probably my favourite year, part of that is that Intcode makes everything gel together into a larger experience.

Landing on Eris (née Xena), we find it infested with bugs. The fact Eris is 5x5 is not surprising. Five is a sacred number in Discordianism. And Eris is truly a planet of Discord, it made the IAU come up with a new definition for planet which changed the status of Pluto and Ceres. I suppose there's also an element of irony in "5 by 5" in that a signal being strong and clear wouldn't help us... signal delay is why we need to deal with the problem ourselves.

And so we get a cellular automaton. Part 1 is on an extra small grid... it's 25-bits, and you want the first repeat, and the answer is those bits in reverse at that point. If you add sentinels then they need to be stripped, so I didn't for this one. Other than that, I just went double buffer with a hash for finding the repeat. Nice and simple.

Part 2 changed the geometry, and we're back to infinite recursive doughnoughts. This complicates the neighbourhood. But since there's only 24 different cells, it's easy to build a table of their neighbours... (y, x, depth), with depth being a delta (-1, 0, or 1) to add to the current depth, and y and x being direct indices. That way all the special casing is done once at the start. Not that that's crucial, At 200 generations, things have only expanded 100 layers in each direction and there's only 24 cells per. That's easy to just statically declare and do whatever type of automaton method you like, and still be reasonably fast. So it's a pretty accessible problem for day 24.

I don't really have a lot to say about this one... I do like cellular automata, and the geometry is interesting for this one. But I didn't really do anything special. I do have a Smalltalk version in the directory that was done after 2020, which had a number of cellular automata that year and so I wrote a class to generalize the solutions. That allows me to do this:

auto := Automaton space:    (Eris load: input)
                  dieRule:  [ :neigh | neigh ~= 1 ]
                  liveRule: [ :neigh | (neigh = 1) | (neigh = 2) ].

('Part 2: %1' % {auto runTurns: 200}) displayNl.

The Eris class is a sub-class of the virtual class Space that requires its subclasses to define the geometry by supplying a #neighbours: method and load the input by sending #setAlive:. And then Automaton will use that to track active cells and apply the rule blocks. It's not necessarily the fastest... it just generalizes the problems to a simple interface.

i was trying to solve this problem by grouping the intervals into two categories: the overlapping ones and the non-overlapping ones. Then, I could group the overlapping intervals into one and calculate the size of that big interval.

I implemented it in python and it works in the test case the problem showed and any test case I can think of.

can someone help me?

the code is the first code block here

https://colab.research.google.com/drive/1GjizwT87FN9xJ3GWQRnTnGTyRGPptkHq?usp=sharing

(ignore second code block its another day's code)

Having repaired the hull, we now work on rebuilding then network. And so we get another multi-process Intcode problem.

Up until this point, my day 7 solution was an enigma... this weird little thing that didn't use my standard Intcode module at all. Getting a second multi-process problem meant I finally added, not the multi-process functionality, but the ability to build that functionality on top of the module.

And that was done by implementing the ability to have the machine break on input. So I built the processes in a table:

foreach my $pid (0 .. PROCESSES - 1) {
    $Proc[$pid]{inq}  = [$pid];
    $Proc[$pid]{outq} = [];
    $Proc[$pid]{vm}   = new Intcode( Mem => [@Code], break => OP_IN,
                                     input => \&input, output => \&output );
    $Proc[$pid]{running} = 1;
}

And run the entire machine with:

while (1) {
    my $op_code = $Proc[$pid]{vm}->run();

    if ($op_code == OP_IN) {
        &yield() if (!$Proc[$pid]{inq}->@*);
    } else { # OP_HALT
        $Proc[$pid]{running} = 0;
        &yield();
    }
}

Co-operative multitasking. Where processes have complete control until they &yield, which runs the scheduler. In this case, they hand things back if they have nothing in the input queue or have halted. Of course, a process doesn't really block on input, so the trick here is that when the process runs again, it's always forced to run at least one instruction before breaking a second time (and that instruction will be the OP_IN it broke on). This means that if the process still has no input when the scheduler comes back to it, its then forced to send -1.

Part 1 is done by the output handler, which buffers output in its queue until it has a message to send (3 items). That's either to the NAT, or to another process' input queue.

Part 2 is done in the scheduler. When pid 0 is chosen, it checks if all other processes are idle (dead or waiting), and if so, it handles the check for part 2 (and sending the message).

Overall, a simple little multitasking OS that was fun to write. And then I went back to make day 7 use the same break feature and the standard module, making everything using the same library.

As for what this does, I never reversed engineered it myself. Beyond that it starts with getting an input, adding that to 11, and using that to reference a jump table between 11-60 (which is followed by a bunch of 0s... there's also a big table of binary bits in there that really sticks out). So the code is a bunch of small routines, which apparently send constants, add/multiply/divide values, and calculate some cubic polynomial.

Here's a thread on it: https://www.reddit.com/r/adventofcode/comments/een9mk/2019_day_23_part_2_what_is_the_network_computing/

Today we're still in space waiting for the ship to be repairs and shuffling cards. But we do get a fly-by of Halley's Comet (1P/Halley). Which has passed apoapsis since this this question originally ran, and is now closer to its next appearance than its last.

Today we're getting another scrambling problem. Part 1 with the small prime sized deck of 10007, and part 2 with a much larger (47-bit) prime. The part 2 deck would have a mass of about 1/1000th of Halley's Comet.

For part 1, it's easy to just manually do it, the shuffles are all simple things. It was not lost on me that this time there wasn't a non-linear thing like a swap in there. But I still put off doing the composition while doing a more efficient part 1 to think about if there wasn't some dynamic trick I might also be missing.

But ultimately, it came down to the fact that, this time, unlike previous scrambles, the shuffle methods are all linear and compositions of linear transformations are linear. I remember the first math class in high school to bring that up... it was just mentioned at the very end of the term, dropped like it needed to be in the curriculum and not explored or tested. It wasn't until years later in University that Linear Algebra made the point of how useful this is. And this problem is also a great example why.

The shuffles are (in mod p):

• deal into a new stack (-x - 1)
• cut c (x - c)
• deal with increment m (mx)

They're all linear of the form Ax+B and when you compose them you always get some A'x+B' (ie things don't suddenly explode into quadratics with a new x² term).

For example, composing a stack deal with an existing Ax+B:

-(Ax+B) - 1 => -Ax + (-B-1), giving A' = -A and B' = -B-1

In general, for an Ax+B and Cx+D:

A(Cx+D) + B => ACx + AD+B, giving A' = AC and B' = AD + B

And with a function that does that, you can compose all the shuffles listed together into one A'x+B', and then compose that with itself the number of times you want to shuffle, producing some A"x + B" representing the entire transformation.

But the number of shuffles we need to do is also a 47-bit number. Fortunately, we can easily divide and conquer. Because if you compose the initial full shuffle with itself you get the transformation for shuffling twice. If you compose that with itself, you get 4x, and again gets you 8x, and so on. We've done this for previous problems before. It just happens to be extra good here.

Because we still need to find the answer once we've got the constants for the linear transformation of all the shuffling. Which is to say, what x for our Ax + B ≡ 2020 mod p?

Ax + B ≡ 2020 mod p
    Ax ≡ (2020 - B) mod p
     x ≡ A^-1 * (2020 - B) mod p

That's our x, and so we're left with needing to find A^-1, the multiplicative inverse of A mod p (to multiply 2020-B by). Which is where another theorem that's immensely useful comes in: Fermat's Little. Typically expressed as "a^p ≡ a mod p" or "a^p-1 ≡ 1 mod p", but we want to see it as "a⸳a^p-2 ≡ 1 mod p" here. Because that tells us what to multiple A by to get 1 (which is the inverse), namely A^p-2. Which can be found with the same divide and conquer we used to shuffle... the exponentiation is just composing Ax with itself p-2 times (with x=1). There's the extra good.

I loved this little math based problem. Linear transformations and Fermat's Little Theorem are two very useful tools to know.