Advent of Code Day 9 to 14

Five more days of coding adventures!

Day 9 - Smoke Basin

We need to find "low points" in a two-dimensional map of integers ranging from 0 to 9.

For part 1 I used a hash to store the map (with keys like "3_2" for row 3/col 2), and looked in the 4 bordering fields to find lower values (adjusting for corners/borders), I use the classic method (learned in previous years) of looping through a list of offsets to look for the neighbouring values:

for my $move ([-1,0],[1,0],[0,-1],[0,1]) {
     my $look = ($r + $move->[0] ).':'.($c + $move->[1]);
     my $val = $map{ $look };
     ...
 }

If the value I'm looking at is lower than all the four neighbours, count it. I needed to implement some special cases for the rows at the edges of the map, which could have been avoided if I had remembered another class trick: Pad the map with some values (in this case, 9 is perfect, because it's the highest values, thus ensuring that all other values are lower). See for example Abigail's solution.

For part 2 I found the joining/splitting of row/cols too annoying so rewrote to a two-dim array. Used a recursive function to walk the map, starting from the low points. After visiting a location, I set it to -1, and stopped when hitting a 9 (or a previously visited -1).

The solutions is quite long because it builds on the solution for part 1 to find the low points. I guess it could be shortened quite bit...

• Part 1
• Part 2

Day 10 - Syntax Scoring

I found this day quite easy (definitely easier than some earlier days), and it took me longer to get the points calculation right than to figure out the closing parens (using a simple stack onto which I push open chars, and then check if we have a matching closing one).

While these solutions could be heavily golfed, I leave then at their current very readable state - if not only to fight certain prejudices against Perl :-)

• Part 1
• Part 2

Day 11 - Dumbo Octopus

Finally, a Game-of-Life-y task. And not too hard. But I wasted some time on the first part because I did the general increment of the octopus in the same step as the flashing, which worked for the first few rows and generations, but later broke down.

This time we need to look at all the 8 neighbours in a grid, so the list of "movement" (in fact, look-instructions) was a bit longer than on day 9:

[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]

Oh, and also I find it much easier to work with rows $r and columns $c instead of x and y.

On this day I started to think about creating something like Acme::AdventOfCode containing a grab-bag of helpful functions (parse a map, draw a map, etc). Maybe I'll prepare something later / next year...

For part 2 I just needed to replace the for loop with a while (1) and stop when all octopus flash.

Here's a very nice visualisation using an arduino

• Part 1
• Part 2

Day 12 - Passage Pathing

I had a family event on Sunday, so only got to work on the tasks in the evening, and was not very motivated. Also, this was a rather standard path solving / graph traversal. So here is my boring code (which was cheated^winsipired by reading a few of the solutions on reddit)

• Part 1
• Part 2

Day 13 - Transparent Origami

Again a very nice task! We need to "fold" a very big piece of transparent paper that's marked with some dots. After a physically impossible number of folds a code will appear (that was part 2, part 1 just tested the basic folding algorithm).

Here you can watch somebody solving it on a folding phone.

For the first part (not cleaned up) I tried to be smart and only implement one folding dimension, and just rotate the map for the other dimension. But unfortunately I'm too stupid to come up with a working matrix rotation in 10 minutes, so I just copied the folding algorithm and adapted it for the other dimension.

I also got a wrong result first, because when the instructions said we should "count the dots", I counted the actual dots ., but those represent emptiness, and we need to count # which represent the dots. I wonder if this was worded like that on purpose..

For the second part (after submitting it..) I replaced the # with █, which makes for much easier to read output. Oh, and I had to adapt the folding algorithm a bit to align the folded parts on the fold, and not on the top row:

splice( @map, $at, 1 );                       # remove the fold
 my @low = splice( @map, $at, @map - $at );    # fold it
 my $r   = @map - @low;                        # make sure the fold aligns
 for my $folded ( reverse @low ) {
     my $c = 0;
     for my $mark (@$folded) {
         $map[$r][$c] = $mark if $mark eq '█';    # rub through
         $c++;
     }
     $r++;
 }

Notice the line with the comment "make sure the fold aligns", where I adjust the starting row to the difference between the two parts of the fold. This was only needed for one fold (for my input), but I still added to both cases.

Here's the output without the fold-alignment-fix:

   █  ████  ███ █ ██ █    ████ █ ██ █  █ 
   ██ ██ █ █  █ ████ █    █ ██ ████ ████ 
    █ ████  ███ ████ █    █ █  ███  ████ 
 █  █ ████ ███  ████ █    █ ██ █ █  ████ 
 █  █ ███  ████ █ ██ █ ██ █ ██ █ █  █  █ 
  ██  █ ██ ████ ███  ███  ████ █ ██ █  █ 

One could try to guess, but fixing it was easier and yields"

   ██ ███  ████ ███  █     ██  █  █ █  █ 
    █ █  █    █ █  █ █    █  █ █ █  █  █ 
    █ █  █   █  ███  █    █    ██   ████ 
    █ ███   █   █  █ █    █ ██ █ █  █  █ 
 █  █ █ █  █    █  █ █    █  █ █ █  █  █ 
  ██  █  █ ████ ███  ████  ███ █  █ █  █ 

• Part 1
• Part 2

This was the first time I got a 4-digit rank (8532 / 9122), but not because I was especially fast / smart, but because I woke up very early and couldn't get back to sleep, and thus started at ~6:30 (local time)

Day 14 - Extended Polymerization

I had 20 minutes time until a meeting started, so I ignored the "This polymer grows quickly" warning for the first part, and implemented an array based solution:

for my $step (1 .. 10) {
    my @new;
    for (my $i=0; $i<@poly-1; $i++) {
        push( @new, $rules{$poly[$i].$poly[$i+1]}->@* );
    }
    push( @new, $poly[-1] );
    @poly = @new;
 }

This looks up the current pair ($poly[$i].$poly[$i+1]) in the list of rules, where for example 'NH' will return 'NC','CH' and push the two new pairs onto the new version of the polymer.

Worked like a charm for part 1. But died after ~22 steps (far from the 40 steps required for part 2) for lack of RAM (and I have loads!).

During my meeting (ahem..) I fiddled a bit with the output to check if there is some regularity I could use to just forecast the result. There wasn't. Linked lists also did not seem reasonable, because we didn't need to insert stuff somewhere into an array. (Linked lists where used in previous years when plain arrays where to slow)

So I couldn't resist to check reddit (the meeting was still ongoing..) where I was greeted by a lot of Lanternfish memes. Then it made click.

I was again fooled by the array-heavy problem description, when in fact all we had to do was count the pairs (of which there where only a few), and increment the pairs based on the rules: So if I see NH (and we already have 10 of them), I just need to increment the counter of NC and CH by 10:

for my $step (1 .. 40) {
     my %new;
     while (my ($pair,$count) = each %pairs) {
         $new{ $rules{$pair}[0] } += $count;
         $new{ $rules{$pair}[1] } += $count;
     }
     %pairs = %new;
 }

The rest was a bit of fiddling with the resulting pair counts to count each letter, not forgetting that the last letter in the original input has to be added once by hand:

my %count = ($poly[-1] => 1);
 while (my ($pair,$count) = each %pairs) {
     my ($f,$s)=split(//,$pair);
     $count{$f}+=$count;
 }

Sort and subtract, and done!

• Part 1
• Part 2