AoC Day 7 – Handy Haversacks

This is a solution to Advent of Code 2020 day 7, written in Raku.

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

Part One

How many bag colors can eventually contain at least one shiny gold bag?

Raku

I used a fairly hairy regular expression to parse the input lines into a set of containment rules. In hindsight this would have been more elegant if I had written a grammar.

Given the containment rules, a recursive containment check finds all 'top level' bags that can contain a shiny gold bag.

  my @lines = '7-input.txt'.IO.lines;

  my %rules = @lines.map(
      -> $l {
          my ($colour, $contains) =  $l.match(/^
                       $<outer> = (<[\w\s]>+)
                       \s 'bags contain'
                       [ [ \s ~ '.' $<inner> = ( (\d+) \s (<[\w\s]>+) ' bag' 's'? )+ % ', ' ]
                         || ' no other bags.'
                       ] $/)<outer inner>;
          $colour => $contains.map(~*[1]).Array
      });

  sub can-contain($outer, $what) {
      my @names = flat %rules{$outer};
      @names.grep( -> $n { $n eq $what or can-contain($n, $what) }).elems > 0;
  }

  say 'Part One';
  say +%rules.keys.grep(-> $n { can-contain($n, 'shiny gold') })
Part One
289

Part Two

How many individual bags are required inside your single shiny gold bag?

Raku

For part two I added an Item class to model how many of each bag colour a given bag can contain. A recursive reduce gives the total number of bags required.

  my @lines = '7-input.txt'.IO.lines;

  class Item { has $.name; has $.many; }

  my %rules = @lines.map(
      -> $l {
          my ($colour, $contains) =  $l.match(/^
                       $<outer> = (<[\w\s]>+)
                       \s 'bags contain'
                       [ [ \s ~ '.' $<inner> = ( (\d+) \s (<[\w\s]>+) ' bag' 's'? )+ % ', ' ]
                         || ' no other bags.'
                       ] $/)<outer inner>;
          $colour => $contains.map(-> $c { Item.new(name => ~$c[1], many => +$c[0]) }).Array
      });

  sub contains(@items) {
      [+] @items.map(
          -> $i {
              $i.many + $i.many * contains(%rules{$i.name})
          })
  }

  say 'Part Two';
  say contains(%rules{'shiny gold'})
Part Two
30055
raku 
comments powered by Disqus