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 = ([ 0, [ 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++ == 32) {
  43                         if ($inv->[3] > $mx) {
  44                                 $mx = $inv->[3];
  45                                 say "   $mx";
  46                         }
  47                         next;
  48                 }
  49
  50                 my @ni = @$inv;
  51                 for (0 .. 3) {
  52                         $ni[$_] += $robs->[$_];
  53                 }
  54
  55                 ROBOT:
  56                 for my $bpn (reverse 0 .. 3) {
  57                         my $bp = $g->[$bpn];
  58                         my $mask = 1 << $bpn;
  59                         next if $cantbuy & $mask;
  60                         if ($bpn < 3 && $robs->[$bpn] >= $needed[$bpn]) {
  61                                 $cantbuy |= $mask;
  62                                 next;
  63                         }
  64
  65                         next if $didntbuy & $mask;
  66                         for (0 .. 2) {
  67                                 next ROBOT if $bp->[$_] > $inv->[$_];
  68                         }
  69                         my @ni1 = @ni;
  70                         for (0 .. 2) {
  71                                 $ni1[$_] -= $bp->[$_];
  72                         }
  73                         my @nr = @$robs;
  74                         $nr[$bpn]++;
  75                         $didntbuy |= $mask;
  76                         unshift @q, [ $t, \@nr, \@ni1, $cantbuy, 0 ];
  77                 }
  78
  79                 unshift @q, [ $t, $robs, \@ni, $cantbuy, $didntbuy ]
  80                         if $didntbuy != 0xf;
  81         }
  82         $mx;
  83 }
  84