42.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4 use bigint;
   5
   6 my (@p) = @ARGV;
   7 my @s = (0, 0);
   8 my $d = 1;
   9 my $dc = 0;
  10
  11 my %state_count = (
  12         3 => 1,
  13         4 => 3,
  14         5 => 6,
  15         6 => 7,
  16         7 => 6,
  17         8 => 3,
  18         9 => 1,
  19 );
  20
  21 use Array::Heap;
  22 my @queue = [ 0, $p[0], $p[1], 0, 0 ];
  23
  24 $; = ',';
  25 my %states = ( "$p[0],$p[1],0,0" => 1 );
  26
  27 my @wins = (0, 0);
  28
  29 while (my $q = pop_heap @queue) {
  30         my @p1add;
  31         my $count = $states{$q->[1],$q->[2],$q->[3],$q->[4]};
  32         # say "pop: ", join(',', @$q);
  33         for my $d1 (3 .. 9) {
  34                 my ($sum, $p1, $p2, $s1, $s2) = @$q;
  35                 $p1 += $d1;
  36                 $p1 -= 10 while $p1 > 10;
  37                 $s1 += $p1;
  38                 my $c1 = $count * $state_count{$d1};
  39                 if ($s1 >= 21) {
  40                         $wins[0] += $c1;
  41                         next;
  42                 }
  43
  44                 for my $d2 (3 .. 9) {
  45                         my ($np2, $ns2, $c2) = ($p2, $s2, $c1);
  46                         $np2 += $d2;
  47                         $np2 -= 10 while $np2 > 10;
  48                         $ns2 += $np2;
  49                         $c2 *= $state_count{$d2};
  50                         if ($ns2 >= 21) {
  51                                 $wins[1] += $c2;
  52                                 next;
  53                         }
  54                         my $key = "$p1,$np2,$s1,$ns2";
  55                         # say "key=$key";
  56                         if ($states{$key}) {
  57                                 $states{$key} += $c2;
  58                         } else {
  59                                 $states{$key} = $c2;
  60                                 push_heap @queue, [ $s1+$ns2, $p1, $np2, $s1, $ns2 ];
  61                         }
  62                 }
  63         }
  64         # say "queue: ", scalar @queue, " states ", scalar keys %states;
  65 }
  66
  67 say $wins[0], ' vs ', $wins[1], " winner is ", $wins[0] > $wins[1] ? 'first' : 'second';