Advent of Code Day 10 - trillion jolts

While the first part was ridiculously easy (after stripping away the overly complex "explanation"), I was not in the mood for doing the second part (recursion, memoization, ..) in the morning.

https://adventofcode.com/2020/day/10

Part 1

We first need to sort the adapters by int value (hence the spaceship op <=>). We start with a jolt of 0, and prefill the result hash with a jolt-count for 3 (because the last adapter has a 3 jolt higher rating).

my @adapters = sort { $a <=> $b } map { chomp; $_ } <>;

my $jolt  = 0;
my %jolts = ( 3 => 1 );
for my $a (@adapters) {
    $jolts{ $a - $jolt }++;
    $jolt = $a;
}

say $jolts{1} * $jolts{3};

Then we just need to go through the sorted adapters, get the joltage difference between the current and the previous adapter ($a - $jolt) and count the result. When we're done, we multiply the counts.

Part 2

Hm, "more than a trillion" you say. Seems like a brute force combinatoric attack will not work out. Using some memoization would obviously help. But as I said, I had no time (and no motivation (and no meeting...)), so I stopped thinking about the problem.

In the evening (I was still to lazy to actually think) I found this excellent hint

Which lead me to this solution:

The main point here is that the input is coming in sets separated by the value 3. So we can break the input down into a bunch of subsets (which will always be consecutive numbers, which the first part showed by only containing jolts of 1 and 3). We now only need to figure out how many combination are possible for each subset, and then multiply these numbers. A quick run through the input revealed a max set size of 5. This seems doable!

I'm not very good at combinatoric, so I used pen & paper to figure out the number of combinations for various set sizes:

size  combinations
  1      1
  2      1
  3      2
  4      4
  5      7

Hm, these numbers look a tiny bit familiar. But before I further investigated them, I implemented the solution (original code):

my @lu     = ( undef, 1, 1, 2, 4, 7 );
my @adapters = sort { $a <=> $b } 0, map { chomp; $_ } <>;
push( @adapters, $adapters[-1] + 3 );
my @set = 0;
my $res = 1;
my $i   = 1;
for (@adapters) {
    push( @set, $_ );
    if ( ( $adapters[ $i++ ] - $set[-1] ) == 3 ) {
        $res *= $lu[ @set - 1 ];
        @set = $set[-1];
    }
}
say $res;

We again sort the input, adding 0 at the beginning and adding the last adapter (+3) to the end. We add the first adapter to the first set (@set = 0), and init a counter and the result.

Then we walk the adapters and push the current one onto the current set. If the next adapter ($adapters[$i++]) has a joltage that's 3 bigger then the current adapter (which is the last element of the current set, $set[-1]), we get the number of combinations for the current set by looking it up in my handcrafted list (using set size minus 1, because we already pushed the current element onto the set) and multiply them with the result. Then we reset the current set to only contain the current adapter. (If this is a bit unclean, take a look at the original code linked above).

After finishing the task, I googled the number and first found something called the lazy caterer's sequence, but this is the wrong sequence. In fact we're looking at the tribonacci numbers, i.e. Tn = T(n-1) + T(n-2) + T(n-3)

That was fun!

No Space

my@t=(0,1,1,2,4,7);my@a=sort{$a<=>$b}0,map{chomp;$_}<>;push(@a,$a[-1]+3);my@s=0;my$r
=1;my$i=1;for(@a){push(@s,$_);if(($a[$i++]-$s[-1])==3){$r*=$t[@s-1];@s=$s[-1]}}say$r

Stats & Links