/ domm

I hack Perl for fun and profit

Follow me on twitter!
Atom Icom ... on Atom!
03.01.2021: Bulk downloading all episodes of a podcast
12.12.2020: Advent of Code Day 12 - sailing to a pause
11.12.2020: Advent of Code Day 11 - slow SeatGoL
10.12.2020: Advent of Code Day 10 - trillion jolts
09.12.2020: Advent of Code Day 9 - while learning
08.12.2020: Advent of Code Day 8 - running code
07.12.2020: Advent of Code Day 7 - baggy recursion

I found this task quite similar to day 6 of last year, but I still wrote my code from scratch. And it's the first time we need recursion!

Part 1

First we need to parse the input, which I do via a combination of regex (to get to container and the content), followed by a split/map combination to get the content. As we don't need the numbers in the first part (and I was not sure what we'll need the numbers for later), I decided to ignore them for now.

And as we're tasked to count the parents of an item (i.e look up a tree), it is easier to just store the parents of each node instead of the whole tree structure (something I remembered from last year - so I did learn something...)

my %contained;
for (<>) {
    my ($container, $content) = $_ =~ /^(.*?) bags contain (.*)\.$/;
    my @content = map {/^\d+ (.*?) bags?/} split(/, /,$content);
    foreach (@content) {
        push($contained{$_}->@*,$container);
    }
}

say count_bag('shiny gold', {});

sub count_bag {
    my ($bag, $agg) = @_;
    foreach my $p ($contained{$bag}->@*) {
        $agg->{$p}++;
        count_bag($p, $agg);
    }
    scalar keys $agg->%*;
}

To actually count the number of bags, we use a small recursive function, which takes the bag we are looking for, loops through all it's parents, stores the parents name in a hash (so we can later get the unique number of elements), and then recuses to get the grandparents. etc.

Part 2

Now we need the number of bags, so we have to adapt the parsing a bit. We store the bag-name and bag-count in an anon array ([$2, $1]) and skip bags containing no other bags.

This time we need to get the count of children, so I adapt my storage hash for easy look-down.

my %bags;
for (<>) {
    my ($container, $content) = $_ =~ /^(.*?) bags contain (.*)\.$/;
    my @content = map {/^(\d+) (.*?) bags?/; [ $2,$1 ] } split(/, /,$content);
    next if $content[0][0] eq 'no other bags';

    $bags{$container} = \@content;
}

say count_bag('shiny gold') - 1;

sub count_bag {
    my $bag = shift;
    my $count = 1;
    foreach my $c ($bags{$bag}->@*) {
        $count += $c->[1] * count_bag($c->[0]);
    }
    return $count;
}

Again a recursive count_bag function, only this time we need to loop through the children. Oh, and of course we need to multiply the result collected by the recursion with the number of times the current bag is bagged in the parent bag. I subtract 1 at the end, because the "shiny gold" starting bag does not count.

No spaces

Line breaks added for "better readability" :-)

my%a;for(<>){($a,$b)=$_=~/^(.*?).ba.*ain.(.*)\.$/;$a{$a}=[grep{$_->[1]=~/\d+/
}map{/(\d+).(.*?).bags?/;[$2,$1]}split/,./,$b]}$a=sub{my($a,$b)=($_[0],1);map
{$b+=$_->[1]*__SUB__->($_->[0])}$a{$a}->@*;$b};say&$a("shiny$\"gold")-1

Oh, and I used one fun newish Perl feature: an anonymous recursive function via __SUB__.

Stats & Links

Comments (via senph)

06.12.2020: Advent of Code Day 6 - simple counting
05.12.2020: Advent of Code Day 5 - hard fail
04.12.2020: Advent of Code Day 4 - validating regex
>>>>>>>>>>
<