42.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4 use bigint;
   5
   6 my %state_count = (
   7         3 => 1,
   8         4 => 3,
   9         5 => 6,
  10         6 => 7,
  11         7 => 6,
  12         8 => 3,
  13         9 => 1,
  14 );
  15
  16 use Array::Heap;
  17 my @queue = [ 0, 0, $ARGV[0], $ARGV[1], 0, 0 ];
  18
  19 my %states = ( join(',', @{ $queue[0] }) => 1 );
  20
  21 my @wins = (0, 0);
  22
  23 while (my $q = pop_heap @queue) {
  24         my $count = $states{join(',', @$q)};
  25         for my $dice (3 .. 9) {
  26                 my $player = $q->[1];
  27                 my $pos    = $q->[2+$player];
  28                 my $score  = $q->[4+$player];
  29                 $pos += $dice;
  30                 $pos -= 10 while $pos > 10;
  31                 $score += $pos;
  32                 my $ncount = $count * $state_count{$dice};
  33                 if ($score >= 21) {
  34                         $wins[$player] += $ncount;
  35                         next;
  36                 }
  37
  38                 my @nq = @$q;
  39                 $nq[0] += $pos;
  40                 $nq[1] = 1-$player;
  41                 $nq[2+$player] = $pos;
  42                 $nq[4+$player] = $score;
  43                 my $key = join(',', @nq);
  44                 if ($states{$key}) {
  45                         $states{$key} += $ncount;
  46                 } else {
  47                         $states{$key} = $ncount;
  48                         push_heap @queue, \@nq;
  49                 }
  50         }
  51 }
  52
  53 say $wins[0], ' vs ', $wins[1], " winner is ",
  54         $wins[0] > $wins[1] ? 'first' : 'second';