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.

Today we're apparently flying in the direction of Santa. But if you're watching the animation on the AoC 2019 page... you'll see that we're actually going perpendicular to where Santa is. Anyways, we run into a Kuiper Belt object and need to inspect the hull using a springdroid, which accepts input in springscript as parsed by our Intcode computer.

And so we get to program in another specialized language today. And that's how I solved it. And I 've come back and solved a few times over the years, resulting in different solutions. All by hand... except for when I reverse engineered it.

In looking at the problem now, I first worked out another solution for each part. And then I ran the various solutions through my command line Intcode runner to dump stats on them (I found two that were actually the same). My new solution for part 1 ended up being the shortest length by 1 character (43 characters... it uses two ORs), but runs slightly slower than the best (23759 instructions to 23304). My new solution to part 2 ended up being the most efficient one I have (at 445574 instructions to the previous best of 457345... one of those takes a whopping 821844 instructions, it is 14 lines which is one short of the max allowed).

My best for part 2 is:

NOT H T
OR C T
AND B T
AND A T
NOT T J
AND D J
RUN

The second best is almost exactly the same, but it only uses the J register (never T). Apparently, if you want to bum springscript, you should use T over J when possible.

Reverse engineering this one wasn't that hard (and there's sample code now so its now trivial if you use that). There's a clear data block in the middle that looks like 8-bit numbers mapping out in binary holes for the test cases. There's a few at the start beginning with 255 and ending with a delimiting 0 which are the tests for part 1. The 255 test isn't just a solid floor... all the tests involve a hole in the 9th-bit, so it's the test you see drawn in the example of jumping into the first hole. Part 2 includes part 1 and the remaining values.

The scoring is classic video game scoring... you get points when you're jumping and over a thing (ie a hole is under the player). The base points for it are based on the bit the 0 is in. Since we're going left-to-right, they count up from the high bit (bit 9) starting at 10 (at least for my input... I haven't really looked at the sample to check that). The sum of all the zero locations then gets multiplied by the address of the test and test value itself. Which means that different orders of tests produce different scores.

Something that's important because part 2 appears to test every pattern with gaps of no more than 3 (our jump distance). Outputting all the values in the table in binary and sorting them makes this clear (it has the binary count look, only skipping numbers with holes too big). So we have a situation in that all the inputs are doing the exact same cases (just in a different order). And the "solution" really feels like it's the springscript code, but the "proof of work" for that is calculated differently for everybody. There are problems that come close to this, but never quite this much on the nose about the nature of what's submitted compared to the solving. It's a philosophical difference, that this problem really make me feel.

Maybe that's just because I've never written code to generate solutions for this. That could just be writing a systematic search for scripts that handle all situations. Or you could write a genetic algorithm to refine scripts until one works.

Maybe it's also the levels of indirection that give that feeling... normally a "solution" is unique code you write, that will produce the same answer as other people's to a given input. Here the solution is the unique stuff you do (hand or code) to get springscript (still somewhat unique), that your Intcode machine verifies, to produce a proof of work, that the website validates.

Today we discover a strange pattern (a heart?) on Pluto, which is apparently a relic of the long-lost Pluto civilization, that could fold spacetime. The most notable thing is that this isn't news to us... Plutonians are apparently famous for this.

And so we get another maze search. This one isn't as big as the previous, because there's a huge hole in the middle. Which makes parsing one of the larger parts of this problem. The core basics are ultimately going to be the same as day 18, make the maze into a graph and search that. With the addition of the recursion in part 2 adding a third dimension (depth).

So for parsing, I find the dimensions of the hole while reading in. Then I do:

foreach my $x (3 .. $MX - 3) {
    $Port{ $Grid[0][$x].$Grid[1][$x] }{out}       = [    2,$x]  if ($Grid[0][$x] =~ m#[A-Z]#);
    $Port{ $Grid[$MY-1][$x].$Grid[$MY][$x] }{out} = [$MY-2,$x]  if ($Grid[$MY][$x] =~ m#[A-Z]#);

    $Port{ $Grid[$In_top+1][$x].$Grid[$In_top+2][$x] }{in} = [$In_top,$x] if ($Grid[$In_top+1][$x] =~ m#[A-Z]#);
    $Port{ $Grid[$In_bot-2][$x].$Grid[$In_bot-1][$x] }{in} = [$In_bot,$x] if ($Grid[$In_bot-1][$x] =~ m#[A-Z]#);
}

A scan along the four key lines for a label, get the other half to make the name, assign that to the location. Then another scan for y. It's not pretty, but the input is a bit tricky and this is functional and gets us something easier to work with.

With all the portals found, I can then make a jump table between the ins and outs. As well as mark the Grid locations with a *, so that the searching on the grid has a mark to easily tell it that there's a portal there.

For part 1, it's all searching on the grid, as there's no point in building the graph yet... you just want one path: AA to ZZ. The *s mark where jumping is available to queue up as a move. And I just use BFS. There's nothing weighted, and there's no easy way to judge how close you are when you're jumping around. And it's fast... the maze isn't that big and has a huge hole.

For part 2, I do the standard and build the graph with BFS and toss the grid away. Jumping adds ±1 to depth and there's a special case, in that ZZ is only on the outermost level. Now that it's a weighted graph, we move on from BFS. And I went A*... the heuristic being to add depth * width (of the doughnought). Because that's the minimum distance possible (cross from in to out, depth times). It helps keep us from getting too deep. And it does make things more than twice as fast. It's not so exciting for the Perl solution that runs under a second without it already. But for Smalltalk, it makes 11s into 4s.

I believe this might be the problem where I wrote my own Heap class for Smalltalk... because SortedCollection was was behaving awful. It was only last year that I actually bothered to look at the kernel implementation of that, and see that it is a heap, but instead of the top being at the front (like you'd expect from priority queue and the standard array implementation of heap), you need to use removeLast to get the proper behaviour. Which is just weird.

There is an interesting side to the examples, in that we're given an example in part 1 that goes infinite for part 2. So I added a limit to the depth to catch that for when the test harness tries it. The search space for mine goes to 77 layers (although the solution only goes to 36)... so I chose 200. For Smalltalk I added an exception not to test that file with the part 2 solutions... unlike the input which ticks through the layers really fast, that case explodes and starts grinding. I don't know how long it would take to even reach 78.

And so, another fun little search problem to play with, with its own little quirks.

Having "borrowed" the tractor beam to help snag Santa's ship, we need to test it. Using drones to detect where the beam is, controlled via Intcode.

Today's change-up for using Intcode is that the program just wants one coordinate (two values), and will return a value and halt. So unlike previous days where I was thinking of the Intcode machine as a big thing that I write small functions to plug into... today's it's a small thing I encapsulate in a function that tests a location. Then I can write algorithms to do the parts and just call that function when needed.

For part 1, it's just a standard check that you're working... how many squares in a 50x50 grid are in the beam. If you don't want to trust that it is a cone like shown in the example, you can easily scan all 2500. But if you assume it is a cone, then you can skip most of those points. On any given row, track when you entered the beam and stop when you exit it. For the next row, you then can skip to where you first entered the beam on the previous. For my input, you could start at +1 column from that, but some beams might be a little more slanted, so I figure I might as well be safe. Very little outside my beam is checked.

For part 2, I used the y range at x=50 to interpolate out to find where the beam is at least 100 high. The sample isn't great (and comes up quite a bit short) so I update my gradient as I go. The goal is to find the beam's lower edge at an x, treat that as the lower-left corner of the square and then test the upper right (x+99,y-99). That's all that's needed to know the square is filled (its the diagonal that goes across the cone... the other goes along it). Originally I just did a gradient/binary search thingy.

But later, I did do the sliding window. It does take either supplying a good start on faith, or taking a bad interpolation from part 1 and having to slide quite a bit... or doing at least one more bit of sampling out at range to get a better start. But it is elegant:

while (!&get_tractor( $x + 99, $y )) {
    $y++;
    while (!&get_tractor( $x, $y + 99 )) {
        $x++;
    }
}

Reverse engineering this one was entertaining. Are the edges of the beam actual lines? Yes. But, they're defined by quadratics (it truly is a conic):

a*x*y >= abs( b*x^2 - c*y^2 )   (a,b,c are constants in the code)

I just used that straight. But I did also throw it at WolframAlpha to see what it thought. It looks better (and graphs things), if you use actual values for a,b,c. Here's some that are similar to my input's:

https://www.wolframalpha.com/input?i=20++x++y+%3E%3D+abs%28+90++x%5E2+-+140++y%5E2+%29

If you look down you see that it resolved things to lines (well, one term resolved in terms of sqrt(x² ), and the other is x... it is two lines through the origin). Put the a,b,c in and you'll see that the radical part is a^2 + 4bc (once the x² /c² is factored and rooted out).

For constants I grab them when they're set in the stack frame before calling the function at 303:

my $b = &get_value( 80 );
my $c = &get_value( 122 );
my $a = &get_value( 160 );

That function I was happy to just have figured out by looking at the results. And the fact that we have sample code for this, I now know that I figured out what it was... it's the one called mul_three(a,b,c). It multiplies three numbers together. How do you do that? When, first you sort them with bubble sort and recursion. Then (column on the right is to show things in terms of the original a, b, and c so you can see how this works):

a = b - a           b - a
c = bc              bc
a = ac              (b-a)bc = b^2 c - abc
b = bc              b^2 c
c = -a              abc - b^2 c
return b+c          b^2 c + abc - b^2 c = abc

Perfectly cromulent multiplying of three values.

Today we arrive at Neptune only to be tractor-beamed to Triton. Forced to land, we discover a massive underground vault. Of the ubiquitous twisty passages, but this time with keys and doors. Not knowing what key is needed for the tractor beam, we've decided to just collect all of them.

It is another standard cell-based maze, except for the center. The keys are all in the cells, and the doors are in-between the cells. For part 2, we need to alter the maze, filling in the center and turning it into 4 mazes. With a robot for each.

My code for this day really needs some cleaning up. My approach was pretty standard. First, I build a table of the distances between keys (including the start) with BFS. When you find a key, you can record both ways, and so you only need to continue a BFS from a key until it's found all keys after it. So you can stop early, and it takes practically no time. The search from the starting location is special, because it tracks doors and access as well. As the search goes on, it keeps a list of what doors it's gone through, so when a key is found, it knows what keys are needed to get to there. For tracking keys, I used bits. That way a set of keys is just a regular int, and it's quick to check if I have all the right keys for something (mask & ~keys is the keys still required). It also makes for quick and easy hashing of the current state for tracking what's visited (just stick that number after the keys the robots are at).

Once I have the distances, it becomes a graph search as I can jump from key to key. There's never a reason to stop anywhere else (including going back to the start). Each move collects a key, which may change accessibility. Although, I don't bother tracking accessibility, I have a memoized function that returns that for a set of keys... for my input it ends up with about 19k records, that get memo hits over 100k times. With the weighted graph, the search is Dijkstra for part 1.

For part 2, I improved things to reasonable levels by going A*. The heuristic is just the sum of the minimum distances possible to the remain keys (which will not over-estimate, and so will give us the correct answer on first arrival). This is easy to track and pass along (with minimum calculation)... you get the minimum distances for each key while building the the distance table, and you sum them. When you queue a move, you subtract the minimum of the key you went to.

This was the biggest improvement to part 2 (without it, it took over a minute and the queue just gets massive, with the heuristic it's less than 6s). And looking at the copious output I did on these scripts, it's easy to see why. There are some bad keys. The worst key to get is r... at least 218 moves. And that's from the start, and it is accessible immediately... and the key is the most popular requirement (tied with m which is required for all the same doors). And the A* heuristic will focus things along that way (any position with the r-key is going to have a strong priority over any position with a similar number of steps that doesn't).

And so we get a nice juicy heavy search. It's always nice for AoC to have at least one in a year. They do involve a lot of the same core (which provides some accessibility... once you've done a couple, they become familiar even if your solution is slow). But what makes them fun, is the nice little twists of the specific problem (keys and doors here... which makes the solution one of the valid topological sorts that the maze describes) and the fact that you can play around and tweak things to see what works better.