2022/37.pl

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