Moved 2021 to a subdir

[aoc.git] / 2021 / 42.pl

diff --git a/2021/42.pl b/2021/42.pl
new file mode 100755 (executable)
index 0000000..c8af64b
--- /dev/null
+++ b/2021/42.pl
@@ -0,0 +1,54 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use bigint;
+
+my %state_count = (
+       3 => 1,
+       4 => 3,
+       5 => 6,
+       6 => 7,
+       7 => 6,
+       8 => 3,
+       9 => 1,
+);
+       
+use Array::Heap;
+my @queue = [ 0, 0, $ARGV[0], $ARGV[1], 0, 0 ];
+
+my %states = ( join(',', @{ $queue[0] }) => 1 );
+
+my @wins = (0, 0);
+
+while (my $q = pop_heap @queue) {
+       my $count = $states{join(',', @$q)};
+       for my $dice (3 .. 9) {
+               my $player = $q->[1];
+               my $pos    = $q->[2+$player];
+               my $score  = $q->[4+$player];
+               $pos += $dice;
+               $pos -= 10 while $pos > 10;
+               $score += $pos;
+               my $ncount = $count * $state_count{$dice};
+               if ($score >= 21) {
+                       $wins[$player] += $ncount;
+                       next;
+               }
+
+               my @nq = @$q;
+               $nq[0] += $pos;
+               $nq[1] = 1-$player;
+               $nq[2+$player] = $pos;
+               $nq[4+$player] = $score;
+               my $key = join(',', @nq);
+               if ($states{$key}) {
+                       $states{$key} += $ncount;
+               } else {
+                       $states{$key} = $ncount;
+                       push_heap @queue, \@nq;
+               }
+       }
+}
+
+say $wins[0], ' vs ', $wins[1], " winner is ",
+       $wins[0] > $wins[1] ? 'first' : 'second';