2022/31.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5
   6 my %flow;
   7 my %tun;
   8
   9 while (<>) {
  10         chomp;
  11         my ($v, $f, $n) = /Valve (..) has flow rate=(\d+);.* to valves? (.*)/;
  12         $flow{$v} = $f if $f;
  13         $tun{$v} = [ split /, /, $n ];
  14         say $n;
  15 }
  16
  17 sub bfs($start) {
  18         my %seen;
  19         my @q = [ $start, 0 ];
  20         while (@q) {
  21                 my $st = shift @q;
  22                 my ($node, $len, @path) = @$st;
  23                 next if $seen{$node};
  24                 $seen{$node} = [ $len, @path ];
  25
  26                 for my $neigh (@{ $tun{$node} }) {
  27                         push @q, [ $neigh, $len+1, @path, $node ];
  28                 }
  29         }
  30         return \%seen;
  31 }
  32
  33 my %paths;
  34 for my $node ('AA', keys %flow) {
  35         $paths{$node} = bfs($node);
  36 }
  37
  38 my @q = [ 'AA', 30, 0, { }, [ ] ];
  39
  40 my $max = 0;
  41 while (@q) {
  42         my $st = shift @q;
  43         my ($node, $mins, $total, $opened, $path) = @$st;
  44         say "At $node $total $mins ", join(',', @$path);
  45         if ($total > $max) {
  46                 $max = $total;
  47         }
  48         for my $n1 (keys %{ $paths{$node} }) {
  49                 next if !$flow{$n1};
  50                 my $dist = $paths{$node}{$n1}[0];
  51                 next if $opened->{$n1};
  52
  53                 my $m1 = $mins - $dist - 1;
  54                 next if $m1 < 0;
  55                 my %o1 = (%$opened, $n1 => 1);
  56                 say " opening $n1 at $m1 ", $flow{$n1}*($m1);
  57                 push @q, [ $n1, $m1, $total + $flow{$n1}*($m1),
  58                         \%o1, [ @$path, $n1 ] ];
  59         }
  60 }
  61
  62 say $max;