Day 19: pruning by remaining time (credits: Honza Obdrzalek)

diff --git a/2022/38.pl b/2022/38.pl
index f72f5c4d3d8734816208df26d7888a6e3e6f20e0..91bc477178b112ced7c9e2daf56294aa81221f33 100755 (executable)
--- a/2022/38.pl
+++ b/2022/38.pl
@@ -25,7 +25,7 @@ while (<>) {
 say $prod;
 
 sub dfs($g) {
-       my @q = ([ 0, [ 1, 0, 0, 0 ], [ 0, 0, 0, 0 ], 0, 0 ]);
+       my @q = ([ 32, [ 1, 0, 0, 0 ], [ 0, 0, 0, 0 ], 0, 0 ]);
        my @needed;
        for my $rob (0 .. 3) {
                for my $comp (0 .. 2) {
@@ -39,13 +39,15 @@ sub dfs($g) {
        while (@q) {
                my ($t, $robs, $inv, $cantbuy, $didntbuy) = @{ shift @q };
 
-               if ($t++ == 32) {
+               if (!$t) {
                        if ($inv->[3] > $mx) {
                                $mx = $inv->[3];
                                say "   $mx";
                        }
                        next;
                }
+               next if $t*$robs->[3] + $inv->[3] + ($t*($t-1)/2) <= $mx;
+               $t--;
 
                my @ni = @$inv;
                for (0 .. 3) {
@@ -57,12 +59,11 @@ sub dfs($g) {
                        my $bp = $g->[$bpn];
                        my $mask = 1 << $bpn;
                        next if $cantbuy & $mask;
+                       next if $didntbuy & $mask;
                        if ($bpn < 3 && $robs->[$bpn] >= $needed[$bpn]) {
                                $cantbuy |= $mask;
                                next;
                        }
-
-                       next if $didntbuy & $mask;
                        for (0 .. 2) {
                                next ROBOT if $bp->[$_] > $inv->[$_];
                        }