From 63e56c0098eaac6b730f32a9c67ef30c52855c6f Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Tue, 21 Dec 2021 07:20:14 +0100
Subject: [PATCH] Day 21: interesting

---
 41.pl | 28 +++++++++++++++++++++++++
 42.pl | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 95 insertions(+)
 create mode 100755 41.pl
 create mode 100755 42.pl

diff --git a/41.pl b/41.pl
new file mode 100755
index 0000000..ac2e4e0
--- /dev/null
+++ b/41.pl
@@ -0,0 +1,28 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+my (@p) = @ARGV;
+my @s = (0, 0);
+my $d = 1;
+my $dc = 0;
+
+sub roll() {
+	$dc++;
+	my $rv = $d++;
+	$d = 1 if $d > 100;
+	return $rv;
+}
+
+while (1) {
+	for (0 .. 1) {
+		$p[$_] += roll()+roll()+roll();
+		$p[$_] -= 10 while $p[$_] > 10;
+		$s[$_] += $p[$_];
+		# say "$dc: $d, $_, $p[$_]";
+		if ($s[$_] >= 1000) {	
+			say $s[1-$_]*$dc;
+			exit 0;
+		}
+	}
+}
diff --git a/42.pl b/42.pl
new file mode 100755
index 0000000..520496d
--- /dev/null
+++ b/42.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use bigint;
+
+my (@p) = @ARGV;
+my @s = (0, 0);
+my $d = 1;
+my $dc = 0;
+
+my %state_count = (
+	3 => 1,
+	4 => 3,
+	5 => 6,
+	6 => 7,
+	7 => 6,
+	8 => 3,
+	9 => 1,
+);
+	
+use Array::Heap;
+my @queue = [ 0, $p[0], $p[1], 0, 0 ];
+
+$; = ',';
+my %states = ( "$p[0],$p[1],0,0" => 1 );
+
+my @wins = (0, 0);
+
+while (my $q = pop_heap @queue) {
+	my @p1add;
+	my $count = $states{$q->[1],$q->[2],$q->[3],$q->[4]};
+	# say "pop: ", join(',', @$q);
+	for my $d1 (3 .. 9) {
+		my ($sum, $p1, $p2, $s1, $s2) = @$q;
+		$p1 += $d1;
+		$p1 -= 10 while $p1 > 10;
+		$s1 += $p1;
+		my $c1 = $count * $state_count{$d1};
+		if ($s1 >= 21) {
+			$wins[0] += $c1;
+			next;
+		}
+
+		for my $d2 (3 .. 9) {
+			my ($np2, $ns2, $c2) = ($p2, $s2, $c1);
+			$np2 += $d2;
+			$np2 -= 10 while $np2 > 10;
+			$ns2 += $np2;
+			$c2 *= $state_count{$d2};
+			if ($ns2 >= 21) {
+				$wins[1] += $c2;
+				next;
+			}
+			my $key = "$p1,$np2,$s1,$ns2";
+			# say "key=$key";
+			if ($states{$key}) {
+				$states{$key} += $c2;
+			} else {
+				$states{$key} = $c2;
+				push_heap @queue, [ $s1+$ns2, $p1, $np2, $s1, $ns2 ];
+			}
+		}
+	}
+	# say "queue: ", scalar @queue, " states ", scalar keys %states;
+}
+
+say $wins[0], ' vs ', $wins[1], " winner is ", $wins[0] > $wins[1] ? 'first' : 'second';
-- 
2.43.0