# 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 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-> * count_bag(\$c->);
}
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

``````my%a;for(<>){(\$a,\$b)=\$_=~/^(.*?).ba.*ain.(.*)\.\$/;\$a{\$a}=[grep{\$_->=~/\d+/
Oh, and I used one fun newish Perl feature: an anonymous recursive function via `__SUB__`.