sol2.pl (872B) [raw]
1 #!/usr/bin/env perl 2 # idea: 3 # this is a weighted DAG. This time, we go container->containee 4 use strict; 5 use warnings; 6 7 8 # build the graph 9 my %h; 10 open(my $fh, '<', 'input') or die "$!"; 11 for my $rule (<$fh>) { 12 my ($container, $containees) = $rule =~ /^(.*) bags contain (.*)\.$/; 13 if ($containees eq 'no other bags') { 14 next; 15 } 16 my @subs = split(', ', $containees); 17 for my $s (@subs) { 18 my ($count, $name) = $s =~ m/(\d+) (.*) bag(?:s)?/; 19 push(@{$h{$container}}, [$count, $name]); 20 } 21 } 22 23 # walk the walk 24 printf "%d\n", num_bags('shiny gold'); 25 26 sub num_bags { 27 my ($b) = @_; 28 if (!exists $h{$b}) { 29 # no other bags needed 30 return 0; 31 } 32 my $n = 0; 33 for my $s (@{$h{$b}}) { 34 # Don't forget to add yourself! 35 $n += ($s->[0] * num_bags($s->[1])) + $s->[0]; 36 } 37 return $n; 38 } 39 40 exit(0); 41