Advent of Code Day 15 to 24, with some gaps

A few more days of Advent of Code...

Day 15 - Chiton

Another path finder, this time with different costs for different paths. This screams for Dijkstra, but for part 1 I still did a more stupid brute force solution using code similar to Day 12 (but using a stack instead of recursion).

For part two my brute force solution was too slow, so I actually had to understand / implement Dijkstra, which took a bit of time, the Wikipedia article and this nice page. It was still rather slow, because I used a plain Perl sort to sort the todo list. Then I thought that I could just group the nodes by cost, thinking (in error) that there would by only 9 buckets, but as each node stores the cumulative cost there are way more buckets. Then I looked into this thing called Heap that was all hot on reddit, and sped up my code a lot by using Heap::Simple. Abigail has a very nice and detailed explanation of "Heap" on his post about the 15th.

Day 16 - Packet Decoder

Yay, decoding a binary protocol!

First, I decode the input into a binary string:

my $bits = join( '', map { sprintf( "%.4b", hex( '0x' . $_ ) ) } split( //, $ARGV[0] || <> ) );

Reading that from right to left, we first either read in a file or take the input directly from the command line, and split it into single characters (split //), the interpret that char as a hex value (hex('0x'.$_)) and convert it into a four bit 0/1 string (sprintf( "%.4b", ..)).

Then we "just" need to take a few bits of that string (I use substr to bite of the correct sizes) to get the version and type_id, and handle the next bits based on the type. As we're dealing with packets that can contain subpackets, I implemented all of this in a recursive function, where the most fiddly stuff was to make sure that the correct number of bits stay on the input stream.

I liked it!

Day 17 - Trick Shot

I spend some time thinking about math-y ways to solve the problem, but only figured out a way to calc the bounds for x. For part 1, I looped through all y between shooting straight down and double the max depths, and got my result. For part 2 the same interval also worked, so I just needed to adjust the calculation of the winning shot.

I liked how I parsed the input, using the return values of the regex:

my ($xfrom, $xto, $yto, $yfrom) = $in =~ /x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/;

Day 18 & 19

I skipped those two days (for now), because they seemed quite complex, and I had family stuff to do on the weekend.

Day 20 - Trench Map

This was a bit too tricky for me. I got part 1 working quite easily for the test data, but it did not work for the live data (which was the actual tricky bit here). After working through some solutions on reddit I finally figured out how to handle the blinking background, solving both parts with the same code:

Day 21 - Dirac Dice

Here I found the first part quite easy, though I still have problems implementing a modulo that works from 1 to 10 instead of 0 to 9:

 my $pos = ( $board{$player}->{pos} + $roll ) % 10;
 $pos = 10 if $pos == 0;

I did not try the second part, because I was busy with Christmas preparations (in my case, producing my mixtape)

Day 22 - Reactor Reboot

I did a quick brute force for part 1, knowing very well that this approach will not work for the second part (where I assumed (correctly) we cannot just ignore the values outside -50:50). I thought a bit about how to intersect cubes, but again had other things to do, and not enough math-power.. So part 2 will have to be solved later

Day 24 - Arithmetic Logic Unit

I skipped day 23 and 24 (again because of Christmas..), but spend some time on the 25th to solve day 24.

Of course I fell for the trap and implemented the ALU (so much simpler than Intcode!) and could output 4 bit numbers easily. But using my virtual machine to brute-force the model number would take ages.

So after some reading reddit I found this solution which very nicely explained how to reverse-engineer the input code to figure out which lines in the code where actually relevant. I then used this as my actual task and wrote some code to extract the relevant lines from my input, do the correct stack manipulations and just output the rules for the different numbers (the 5th number has to be 3 larger then the 11th number, etc):

 my @stack;
 my %rules;
 for my $i (1..14) {
     my $prog = $progs[$i];
     my $check = $prog->[5]->[2];
     my $offset = $prog->[15]->[2];
     if ($check > 0) {
         push(@stack,[$i,$offset]);
     }
     else {
         my $old = pop(@stack);
         my $calc = $old->[1] + $check;
         $rules{$i} = [$old->[0],$calc];
     }
 }

And then calculated the biggest/smallest serial number by hand.

But because I had some more appetite for coding, I also implemented an automatic solver:

 my @high=' ';
 my @low= ' ';
 while (my ($pos, $rule) = each %rules) {
     if ($rule->[1] <= 0) {
         $high[$rule->[0]] = 9;
         $high[$pos] = 9 + $rule->[1];
         $low[$pos]=1;
         $low[$rule->[0]]= 1 - $rule->[1] ;
     }
     else {
         $high[$pos] = 9;
         $high[$rule->[0]] = 9 - $rule->[1];
         $low[$rule->[0]] = 1;
         $low[$pos] = 1 + $rule->[1];
     }
 }
 
 say "high: ".join('',@high);
 say "low:  ".join('',@low);

Very nice, but I could have never come up with the actual solution on my own.

The rest...

I do plan to try to tackle the remaining tasks, but it might take some time, as we have a rather big roll-out of a project that has been in the work the last 1.5 years in the next week...

But it was another very nice Advent of Code. Thanks, Eric, and all the other people who helped make this work, and who posted their solutions and explanations!