#!/usr/bin/env perl
# idea:
#   this is a weighted DAG. The natural way the rules flow, I _want_ to make it
#   so that the edges go from container->containee BUT, for the problem we want
#   to solve, it makes much more sense to build the graph containee->[container]
#   so that we can then do a quick walk of all possible containers
use strict;
use warnings;


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

# walk the walk
my @q = @{$h{'shiny gold'}}; # direct containers
my %seen;
while (my $i = shift @q) {
    next if $seen{$i};
    $seen{$i} = 1;
    if (exists $h{$i}) {
        # I suppose there might be some outer-only bags
        push (@q, @{$h{$i}});
    }
}
printf "%d out of %d\n", scalar keys %seen, scalar keys %all;

exit(0);
