]> www.fi.muni.cz Git - aoc2021.git/blob - 42.pl
520496d02b01abcfdd1f7136e04be64acd9c2861
[aoc2021.git] / 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';