2022/32.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 }
  15
  16 sub bfs($start) {
  17         my %seen;
  18         my @q = [ $start, 0 ];
  19         while (@q) {
  20                 my $st = shift @q;
  21                 my ($node, $len, @path) = @$st;
  22                 next if $seen{$node};
  23                 $seen{$node} = [ $len, @path ];
  24
  25                 for my $neigh (@{ $tun{$node} }) {
  26                         push @q, [ $neigh, $len+1, @path, $node ];
  27                 }
  28         }
  29         return \%seen;
  30 }
  31
  32 my %paths;
  33 for my $node ('AA', keys %flow) {
  34         $paths{$node} = bfs($node);
  35 }
  36
  37 sub walk(@nodes) {
  38         my @q = [ 'AA', 26, 0, { map { $_ => 1 } @nodes }, [ ] ];
  39
  40         my $max = 0;
  41         while (@q) {
  42                 my $st = shift @q;
  43                 my ($node, $mins, $total, $opened, $path) = @$st;
  44
  45                 if ($total > $max) {
  46                         # say "At $node $mins $total ", join(',', @$path);
  47                         $max = $total;
  48                 }
  49
  50                 for my $n1 (keys %{ $paths{$node} }) {
  51                         next if !$flow{$n1};
  52                         my $dist = $paths{$node}{$n1}[0];
  53                         next if $opened->{$n1};
  54
  55                         my $m1 = $mins - $dist - 1;
  56                         next if $m1 < 0;
  57                         my %o1 = (%$opened, $n1 => 1);
  58                         # say " opening $n1 at $m1 ", $flow{$n1}*($m1);
  59                         push @q, [ $n1, $m1, $total + $flow{$n1}*($m1),
  60                                 \%o1, [ @$path, $n1 ] ];
  61                 }
  62         }
  63         return $max;
  64 }
  65
  66 my @nodes = sort keys %flow;
  67
  68 my $mx;
  69 my $walked;
  70 sub walk1($n1, $n2, $rest) {
  71         if (!@$rest) {
  72                 my $sum = walk(@$n1) + walk(@$n2);
  73                 $walked++;
  74                 if (!defined $mx || $mx < $sum) {
  75                         say join(' ', @$n1), ' | ', join(' ', @$n2), " ($walked) = $sum";
  76                         $mx = $sum;
  77                 }
  78                 return;
  79         }
  80         my @nrest = @$rest;
  81         my $node = shift @nrest;
  82         walk1([ @$n1, $node ], $n2, \@nrest);
  83         walk1($n1, [ @$n2, $node ], \@nrest);
  84 }
  85
  86 my $first = shift @nodes;
  87 walk1([$first], [], \@nodes);
  88 say $mx;