Day 22

[aoc2020.git] / 44.pl

diff --git a/44.pl b/44.pl
new file mode 100755 (executable)
index 0000000..05d941f
--- /dev/null
+++ b/44.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/perl -w
+
+use strict;
+
+local $/ = "\n\n";
+
+my @pl1 = <> =~ /^(\d+)$/gxms;
+my @pl2 = <> =~ /^(\d+)$/gxms;
+
+print "sum=", play(\@pl1, \@pl2), "\n";
+
+sub play {
+       my ($d1, $d2) = @_;
+       my @pl1 = @$d1;
+       my @pl2 = @$d2;
+
+       my %seen;
+
+       while (@pl1 && @pl2) {
+               my $conf = join('|', @pl1, "#", @pl2);
+               if ($seen{$conf}++) {
+                       return score(@pl1);
+               }
+               my $p1 = shift @pl1;
+               my $p2 = shift @pl2;
+
+               if ($p1 <= @pl1 && $p2 <= @pl2) {
+                       my @sub1 = @pl1[0 .. $p1-1];
+                       my @sub2 = @pl2[0 .. $p2-1];
+                       if (play(\@sub1, \@sub2) > 0) {
+                               push @pl1, $p1, $p2;
+                       } else {
+                               push @pl2, $p2, $p1;
+                       }
+               } else {
+                       if ($p1 > $p2) {
+                               push @pl1, $p1, $p2;
+                       } else {
+                               push @pl2, $p2, $p1;
+                       }
+               }
+       }
+       if (@pl1) {
+               return score(@pl1);
+       } else {
+               return -score(@pl2);
+       }
+}
+
+sub score {
+       my @pl1 = @_;
+       my $sum = 0;
+       while (@pl1) {
+               $sum += +$pl1[0] * @pl1;
+               shift @pl1;
+       }
+       return $sum;
+}
+