Raku: Advent of Code 2020 - Day Seven

Raku solution for Day 7 of Advent of Code. Commentary follows the code... If you enjoy it or can offer improvements, please leave a comment.

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

grammar Baggage {
    rule TOP      { <rule>+ }
    rule rule     { <color> 'bags contain' <contents> '.' }
    rule contents { 'no other bags' | [ <quantity> <color> <.bag> ]+ % ',' }
    token color       { \w+ \W+ \w+ }
    token quantity    { \d+ }
    token bag         { 'bag' | 'bags' }
}

class BaggageActions {
    has $.inside = {};
    has $.outside = {};

    method rule($/) {
        return  if 'no other bags' eq ~$<contents>;
        my $outer = ~$<color>;
        my $inner = %( $<contents>.<color>.map({~$_}).List Z=> $<contents>.<quantity>.map({+$_}).List );
        $!inside{$outer} = $inner;
        for $inner.pairs {
            $!outside{.key}.push($outer);
        }
    }
}

sub MAIN (
    IO() :$input where *.f     = $?FILE.IO.sibling('input'),
    Int  :$part where * == 1|2 = 1, # Solve Part One or Part Two?
    --> Nil
) {
    my $a = BaggageActions.new();
    Baggage.parse($input.slurp, :actions($a));
    given $part {
        when 1 { can_contain('shiny gold').elems.say }
        when 2 { bags_required('shiny gold').say }
    }

    sub can_contain (Str $color) {
        $a.outside{$color}.map({ $_ ?? ($_, can_contain($_)) !! () }).flat.Slip.unique;
    }

    sub bags_required (Str $color) {
        $a.inside{$color}.pairs.map({ .value + .value * bags_required(.key) }).sum;
    }
}

Today's puzzle looked like it would lend itself to a solution using grammars. Day Four's solution with grammars required me to bite off a bit more of Raku at one time than I was ready for. By leaning heavily on examples from meinaikage's solution I was eventually able to get something that worked. But I didn't always understand why.

Over the last few days, I've been working through the grammar tutorial and reference grammars documentation on docs.raku.org. Another great resource has been Andrew Shitov's series on Creating a Compiler with Raku and video presentation on grammars to the Amsterdam Perl Mongers.

Grammar::Debugger and Grammar::Tracer were very helpful in helping me visualize the match and figuring out my mistakes.

In Day 4's solution I pulled what I needed out of the match object. Today's solution uses the grammar's action class to build up two hashes as the rules are parsed. One to allow looking up the bags $.inside{$color} and the other to perform a reverse lookup of the bags enclosing $.outside{$color}.  The reverse lookup enables the solution for Part One to perform well by avoiding looping or iterating through all the bag rules multiple times.

The Z zip metaoperator came in handy when creating $inner hash of color => qty key value pairs. Perhaps there is a better way to build the match object that would avoid needing it. But this effectively allowed me to:

('bright white', 'muted yellow') Z=> (1, 2) 
# OUTPUT «{'bright white' => 1, 'muted yellow' => 2}»

The only other significant surprise was dealing with the difference between:

perl5: print( join(",", (1,2,()) ), "\n");   # OUTPUT: «1,2»
raku:  (1,2,()).join(",").say;               # OUTPUT: «1,2,»

Raku likes to preserve empty lists. I spent a good bit of time trying to figure out where the (Any) values in my returned list values were coming from. Eventually with the help of lizmat and codesections on the raku irc channel, I found that I could remove empty lists by using .flat and .Slip:

raku:  (1,2,()).flat.Slip.join(",").say;     # OUTPUT: «1,2»

With this... if can_contain($color) is called on a bag color that isn't contained by any other bags, then the return value does not append an empty list to the results. Which somehow showed up as an (Any) value in the flattened list.

There Is More Than One Way To Do It (TIMTOWTDI) is both a blessing and a curse. Raku is incredibly expressive. But when reading other people's code, there is a learning curve associated with being able to recognize and understand all the nuanced ways of saying the same thing...

raku:  ((1,2,()).map: *.Slip).join(",").say; # OUTPUT: «1,2»
raku:  (1,2,()).grep(|*).join(",").say;      # OUTPUT: «1,2»

All in all, I'm glad I chose to use Raku with this year's Advent of Code. It really does seem to be designed to be -Ofun.

Thank you for reading! If you've found this interesting or useful, of if you've found an error, typo, mistake or suggestion for improvements, then please leave a comment below.