X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc2020.git;a=blobdiff_plain;f=44.pl;fp=44.pl;h=05d941ffc4758c10f3420507511d5d14f498bb8b;hp=0000000000000000000000000000000000000000;hb=e6bc74633b91f9a03a137afd30a58198822f820c;hpb=63b534141e63cf51990d5fa2234e1d21f0bc1bbc

diff --git a/44.pl b/44.pl
new file mode 100755
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;
+}
+