#!/usr/bin/env perl
# idea:
#   this is a weighted DAG. This time, we go container->containee
use strict;
use warnings;


# build the graph
my %h;
open(my $fh, '<', 'input') or die "$!";
for my $rule (<$fh>) {
    my ($container, $containees) = $rule =~ /^(.*) bags contain (.*)\.$/;
    if ($containees eq 'no other bags') {
        next;
    }
    my @subs = split(', ', $containees);
    for my $s (@subs) {
        my ($count, $name) = $s =~ m/(\d+) (.*) bag(?:s)?/;
        push(@{$h{$container}}, [$count, $name]);
    }
}

# walk the walk
printf "%d\n", num_bags('shiny gold');

sub num_bags {
    my ($b) = @_;
    if (!exists $h{$b}) {
        # no other bags needed
        return 0;
    }
    my $n = 0;
    for my $s (@{$h{$b}}) {
        # Don't forget to add yourself!
        $n += ($s->[0] * num_bags($s->[1])) + $s->[0];
    }
    return $n;
}

exit(0);

