Raku: Advent of Code 2020 - Day Ten

Today's Advent of Code 2020 puzzle involves getting power (measured in jolts) to Santa's computing device from an outlet that provides 0 jolts. Santa's has some very special joltage adapters which act as step-up transformers. Each adapter can increase the joltage by up to 3 jolts. The input for the puzzle is a list of numbers representing the maximum joltage of each of Santa's adapters. And Santa's computing device has its own final adapter which is 3 jolts higher than the highest adapter in the bag.

Below are Raku solutions to Day Ten's puzzle.

I had a lot of fun getting Part One down to a minimal (obfuscated) 66 character short form solution:

say lines».Int.sort.&{((|@$_,.max+3) Z-(0,|@$_)).Bag.&{.{1}*.{3}}}

Other than some typical boilerplate, the full length solution which follows isn't much longer. Though it is formatted a bit better for comprehension.

Part Two and its challenge to calculate the count of all possible permutations based on consecutive ±3 jolt joltages threw me for a loop. I have no formal education in computer science. And my math stopped at single variable calculus. Most of which I have forgotten. The CS majors on Reddit credited their Combinatorics classes for being able to come up with a generalized solution. I eventually gave up on the generalized solution and went with a "good enough" solution. I.e. I figured out the number of variations for the first four permutations and made a look up table.

Commentary follows the code.

#!/usr/bin/env raku
use v6.d;

unit sub MAIN (
        IO() :$input where *.f     = $?FILE.IO.sibling('input'),
        Int  :$part where * == 1|2 = 1, # Solve Part One or Part Two?
        --> Nil
);

# valid permutations (p) per length of consecutive (c) numbers
# ( no more than 4 consecutive numbers found in input )
my @p = (1,1,2,4,7);

given $part {
    when 1 {
        say $input.lines».Int.sort.&{
            ( (|@$_,.tail+3) Z-(0,|@$_) ).Bag.&{
                .{1}×.{3}
            }
        }
    }
    when 2 {
        my @c = 0;
        say $input.lines».Int.sort.&{ 0, |@$_, .tail+3 }.&{
            .rotor(2 => -1)
            .map({ .[1]-.[0]==1 ?? @c[*-1]++ !! @c.push(0) });
            @c;
        }.map({ @p[$_] }).reduce(&infix:<×>);
    }
}

Part One

The puzzle for part one requires you to sort the adapters by joltage, separately count the number of 1 jolt steps and 3 jolt steps, and calculate the product of those counts.

Skipping over the CLI boilerplate, the solution to part one is:

say $input.lines».Int.sort.&{
    ( (|@$_,.tail+3) Z-(0,|@$_) ).Bag.&{
        .{1}×.{3}
    }
}

Let's start by unpacking the first line:

say $input.lines».Int.sort.&{

say will print the result of the chained method calls which follow it.

». is the hyper method call operator. It will take a list on the left hand side, then call the method on the right hand side once for each item in the list and return the results (to the next chained method). The difference between ». and map is that the hyper method does not guarantee the order in which the elements are processed. This can be significant if processing an element has side effects.

$input.lines».Int.sort

This splits the contents of the $input file into lines, converting the string on each line into an integer, and sorting the results.

.&{...} is an anonymous code block masquerading as a method. The first parameter of a method is the invocant. So in:

say $input.lines».Int.sort.&{ ... }

The sorted integer list is passed as the invocant to the code block. This topicalizes the list so that it can be referenced explicitly as $_ or as the implicit invocant of any method calls within the block.

The next line of code needs to be unpacked in steps. Let's start with:

(|@$_,.tail+3) Z-(0,|@$_)

Here we're going to create a result list containing the difference between consecutive items in the list. There are a couple ways this could be done. I chose to use the Z- zip meta-operator. Using a simple example for the list (0, 2, 3, 5) we would do:

(2, 3, 5) Z- (0, 2, 3)  # RESULT: (2 1 2)

However in our case the list of differences needs to include the the 0 jolt "outlet" and Santa's computing device with its build in +3 above maximum adapter jolts. Because the list of integers was the invocant to this code block, it can be referenced using the topical variable $_. We use the @ list contextualizer and | to make a slip which flattens the list into its outer context.  .tail returns the last item in the sorted topicalized integer array. Which happens to be the maximum jolt adapter value.

So if for example our $_ bag of jolt adapters contained (1, 2, 3, 5)... 

(|@$_,.tail+3) Z-(0,|@$_)

In this instance would be equivalent to: 

( ((1, 2, 3, 5), (1, 2, 3, 5).tail+3)).flat Z- (0, (1, 2, 3, 5)).flat

Now that we have our list of differences let's look at the rest of that line:

( (|@$_,.tail+3) Z-(0,|@$_) ).Bag.&{

.Bag converts our list of differences into a bag of differences. A bag is like a set. Except where a set does not keep track of multiple instances of the same value within it... a bag does.

.&{...} takes the bag as the invocant of the code block setting the bag as the topical variable $_ . In the next line:

.{1}×.{3} 

We treat the bag as a hash and look up the number (key weight) of 1's and 3's stored in the bag... and multiply them together to find their product. I.e. the answer to Part One of the puzzle.

Part Two

I'm going to gloss over the syntax which was explained in Part One. Let's look at the code relevant to Part Two:

# valid permutations (p) per length of consecutive (c) numbers
# ( no more than 4 consecutive numbers found in input )
my @p = (1,1,2,4,7);

...

my @c = 0;
say $input.lines».Int.sort.&{ 0, |@$_, .tail+3 }.&{
    .rotor(2 => -1)
    .map({ .[1]-.[0]==1 ?? @c[*-1]++ !! @c.push(0) });
    @c;
}.map({ @p[$_] }).reduce(&infix:<×>);

@p holds the lookup table which I mentioned earlier in the introduction.

@c is going to hold a list of consecutive number counts. 

say $input.lines».Int.sort.&{ 0, |@$_, .tail+3 }.&{

Gets us our list of (zero outlet jolts, adapters jolts, and Santa's computing devices built in max adapter +3 jolts) and passes it into the anonymous code block as the invocant.

.rotor(2 => -1)

rotor is very cool.  It regroups the elements of the invocant list into batches. In this case batches of 2 elements. The next batch starts the same (2) number of steps forward and -1 steps back. So for example:

(1, 2, 3, 4).rotor(2 => -1)  # RESULTS: ((1 2) (2 3) (3 4))

This gives us a list of list of consecutive adapter joltages as the invocant to:

.map({ .[1]-.[0]==1 ?? @c[*-1]++ !! @c.push(0) });

Where .[1]-.[0] tests if the consecutive adapters' joltages are consecutive numbers. If so, it increments the current consecutive number count (which is the last item in @c. ...Or it pushes a new consecutive number count onto the end of @c with the starting value of zero.

... .&{
    ... 
    @c;
}.map({ @p[$_] }).reduce(&infix:<×>);

Before exiting the anonymous code block we lastly mention @c; In the absence of an explicit return statement, the last value in the code block is what gets returned. So the list of consecutive number counts becomes the invocant to:

.map({ @p[$_] }).reduce(&infix:<×>);

Here .map translates each count using our permutation @p lookup table.

And .reduce multiplies each of those together to give us the answer to Part Two. I.e., The total number of adapter variations which could be used to power Santa's computing device.

Thank you for reading. I hope you've enjoyed it. If you have, or if you have suggestions, please leave a comment below.