Day 21: interesting

[aoc2021.git] / 42.pl

diff --git a/42.pl b/42.pl
new file mode 100755 (executable)
index 0000000..520496d
--- /dev/null
+++ b/42.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use bigint;
+
+my (@p) = @ARGV;
+my @s = (0, 0);
+my $d = 1;
+my $dc = 0;
+
+my %state_count = (
+       3 => 1,
+       4 => 3,
+       5 => 6,
+       6 => 7,
+       7 => 6,
+       8 => 3,
+       9 => 1,
+);
+       
+use Array::Heap;
+my @queue = [ 0, $p[0], $p[1], 0, 0 ];
+
+$; = ',';
+my %states = ( "$p[0],$p[1],0,0" => 1 );
+
+my @wins = (0, 0);
+
+while (my $q = pop_heap @queue) {
+       my @p1add;
+       my $count = $states{$q->[1],$q->[2],$q->[3],$q->[4]};
+       # say "pop: ", join(',', @$q);
+       for my $d1 (3 .. 9) {
+               my ($sum, $p1, $p2, $s1, $s2) = @$q;
+               $p1 += $d1;
+               $p1 -= 10 while $p1 > 10;
+               $s1 += $p1;
+               my $c1 = $count * $state_count{$d1};
+               if ($s1 >= 21) {
+                       $wins[0] += $c1;
+                       next;
+               }
+
+               for my $d2 (3 .. 9) {
+                       my ($np2, $ns2, $c2) = ($p2, $s2, $c1);
+                       $np2 += $d2;
+                       $np2 -= 10 while $np2 > 10;
+                       $ns2 += $np2;
+                       $c2 *= $state_count{$d2};
+                       if ($ns2 >= 21) {
+                               $wins[1] += $c2;
+                               next;
+                       }
+                       my $key = "$p1,$np2,$s1,$ns2";
+                       # say "key=$key";
+                       if ($states{$key}) {
+                               $states{$key} += $c2;
+                       } else {
+                               $states{$key} = $c2;
+                               push_heap @queue, [ $s1+$ns2, $p1, $np2, $s1, $ns2 ];
+                       }
+               }
+       }
+       # say "queue: ", scalar @queue, " states ", scalar keys %states;
+}
+
+say $wins[0], ' vs ', $wins[1], " winner is ", $wins[0] > $wins[1] ? 'first' : 'second';