sol1.pl (1173B) [raw]
1 #!/usr/bin/env perl 2 # idea: 3 # this is a weighted DAG. The natural way the rules flow, I _want_ to make it 4 # so that the edges go from container->containee BUT, for the problem we want 5 # to solve, it makes much more sense to build the graph containee->[container] 6 # so that we can then do a quick walk of all possible containers 7 use strict; 8 use warnings; 9 10 11 # build the graph 12 my %h; 13 my %all; 14 open(my $fh, '<', 'input') or die "$!"; 15 for my $rule (<$fh>) { 16 my ($container, $containees) = $rule =~ /^(.*) bags contain (.*)\.$/; 17 $all{$container} = 1; 18 if ($containees eq 'no other bags') { 19 # skip! 20 next; 21 } 22 my @subs = map { s/\d+ (.*) bag(?:s)?/$1/r } split(', ', $containees); 23 $all{$_} = 1 for @subs; 24 $all{$container} = 1; 25 for my $s (@subs) { 26 push(@{$h{$s}}, $container); 27 } 28 } 29 30 # walk the walk 31 my @q = @{$h{'shiny gold'}}; # direct containers 32 my %seen; 33 while (my $i = shift @q) { 34 next if $seen{$i}; 35 $seen{$i} = 1; 36 if (exists $h{$i}) { 37 # I suppose there might be some outer-only bags 38 push (@q, @{$h{$i}}); 39 } 40 } 41 printf "%d out of %d\n", scalar keys %seen, scalar keys %all; 42 43 exit(0);