2022/38.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5 use List::Util qw(max);
   6
   7 my $prod = 1;
   8 while (<>) {
   9         # my ($id, $ore, $clay, $obs_ore, $obs_clay, $geode_ore, $geod_obs)
  10         my @bp = /(\d+)/g;
  11
  12         my @g = (
  13                 # ore clay obs
  14                 [ $bp[1], 0, 0, 0 ],
  15                 [ $bp[2], 0, 0, 0 ],
  16                 [ $bp[3], $bp[4], 0, 0 ],
  17                 [ $bp[5], 0, $bp[6], 0 ],
  18         );
  19         my $res = dfs(\@g);
  20         say "$bp[0]: $res";
  21         $prod *= $res;
  22         last if $bp[0] == 3;
  23 }
  24
  25 say $prod;
  26
  27 sub dfs($g) {
  28         my @q = ([ 32, [ 1, 0, 0, 0 ], [ 0, 0, 0, 0 ], 0, 0 ]);
  29         my @needed;
  30         for my $rob (0 .. 3) {
  31                 for my $comp (0 .. 2) {
  32                         $needed[$comp] = $g->[$rob][$comp]
  33                                 if !defined $needed[$comp]
  34                                         || $g->[$rob][$comp] > $needed[$comp];
  35                 }
  36         }
  37
  38         my $mx = 0;
  39         while (@q) {
  40                 my ($t, $robs, $inv, $cantbuy, $didntbuy) = @{ shift @q };
  41
  42                 if (!$t) {
  43                         if ($inv->[3] > $mx) {
  44                                 $mx = $inv->[3];
  45                                 say "   $mx";
  46                         }
  47                         next;
  48                 }
  49                 next if $t*$robs->[3] + $inv->[3] + ($t*($t-1)/2) <= $mx;
  50                 $t--;
  51
  52                 my @ni = @$inv;
  53                 for (0 .. 3) {
  54                         $ni[$_] += $robs->[$_];
  55                 }
  56
  57                 ROBOT:
  58                 for my $bpn (reverse 0 .. 3) {
  59                         my $bp = $g->[$bpn];
  60                         my $mask = 1 << $bpn;
  61                         next if $cantbuy & $mask;
  62                         next if $didntbuy & $mask;
  63                         if ($bpn < 3 && $robs->[$bpn] >= $needed[$bpn]) {
  64                                 $cantbuy |= $mask;
  65                                 next;
  66                         }
  67                         for (0 .. 2) {
  68                                 next ROBOT if $bp->[$_] > $inv->[$_];
  69                         }
  70                         my @ni1 = @ni;
  71                         for (0 .. 2) {
  72                                 $ni1[$_] -= $bp->[$_];
  73                         }
  74                         my @nr = @$robs;
  75                         $nr[$bpn]++;
  76                         $didntbuy |= $mask;
  77                         unshift @q, [ $t, \@nr, \@ni1, $cantbuy, 0 ];
  78                 }
  79
  80                 unshift @q, [ $t, $robs, \@ni, $cantbuy, $didntbuy ]
  81                         if $didntbuy != 0xf;
  82         }
  83         $mx;
  84 }
  85