From: Jan "Yenya" Kasprzak <kas@fi.muni.cz>
Date: Sat, 24 Dec 2022 06:13:17 +0000 (+0100)
Subject: Day 24: priority queue with memoization
X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc.git;a=commitdiff_plain;h=fe4d8ec08525af68241a04efd036d28d4d9ab542

Day 24: priority queue with memoization
---

diff --git a/2022/47.pl b/2022/47.pl
new file mode 100755
index 0000000..1a61d2e
--- /dev/null
+++ b/2022/47.pl
@@ -0,0 +1,82 @@
+#!/usr/bin/perl -w
+
+use v5.36;
+use strict;
+use Array::Heap;
+
+my @map = map { chomp; [ split // ] } <>;
+my $xmax = $#{$map[0]};
+my $ymax = $#map;
+
+my $mod;
+if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD
+	$mod = 700;
+} else {
+	$mod = ($xmax-1) * ($ymax-1);
+}
+
+my @nmaps;
+sub occupied($x,$y,$time) {
+	my $t = $time % $mod;
+	my $nmap = $nmaps[$t];
+	return $nmap->{"$x,$y"}
+		if defined $nmap;
+	for my $y (0 .. $ymax) {
+		for my $x (0 .. $xmax) {
+			next if ($map[$y][$x] eq '.');
+			my ($nx, $ny) = ($x, $y);
+			if ($map[$y][$x] eq '>') {
+				$nx = 1 + (($x+$t-1) % ($xmax-1));
+			} elsif ($map[$y][$x] eq 'v') {
+				$ny = 1 + (($y+$t-1) % ($ymax-1));
+			} elsif ($map[$y][$x] eq '^') {
+				$ny = 1 + (($y-$t-1) % ($ymax-1));
+			} elsif ($map[$y][$x] eq '<') {
+				$nx = 1 + (($x-$t-1) % ($xmax-1));
+			}
+			if ($nmap->{"$nx,$ny"}) {
+				if ($nmap->{"$nx,$ny"} =~ /\d/) {
+					$nmap->{"$nx,$ny"}++;
+				} else {
+					$nmap->{"$nx,$ny"} = 2;
+				}
+			} else {
+				$nmap->{"$nx,$ny"} = $map[$y][$x];
+			}
+		}
+	}
+	$nmaps[$t] = $nmap;
+	return $nmap->{"$x,$y"};
+}
+
+my @q = [$xmax+$ymax, 1, 0, 0];
+my %seen;
+while (@q) {
+	my $now = pop_heap @q;
+	my ($dist, $x, $y, $time) = @$now;
+	my $key = join(',',$x, $y, ($time % $mod));
+	next if $seen{$key}++;
+	# say "at $x $y dist $dist time $time";
+	if ($x == $xmax-1 && $y == $ymax) {
+		say "$time";
+		last;
+	}
+	$time++;
+	$dist++;
+	if (!occupied($x,$y,$time)) {
+		push_heap @q, [ $dist, $x, $y, $time ];
+	}
+	if (!occupied($x+1,$y,$time)) {
+		push_heap @q, [ $dist-1, $x+1, $y, $time ];
+	}
+	if (!occupied($x-1,$y,$time)) {
+		push_heap @q, [ $dist+1, $x-1, $y, $time ];
+	}
+	if (!occupied($x,$y+1,$time)) {
+		push_heap @q, [ $dist-1, $x, $y+1, $time ];
+	}
+	if ($y > 1 && !occupied($x,$y-1,$time)) {
+		push_heap @q, [ $dist+1, $x, $y-1, $time ];
+	}
+}
+
diff --git a/2022/48.pl b/2022/48.pl
new file mode 100755
index 0000000..adde9f8
--- /dev/null
+++ b/2022/48.pl
@@ -0,0 +1,92 @@
+#!/usr/bin/perl -w
+
+use v5.36;
+use strict;
+use Array::Heap;
+
+my @map = map { chomp; [ split // ] } <>;
+my $xmax = $#{$map[0]};
+my $ymax = $#map;
+
+my $mod;
+if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD
+	$mod = 700;
+} else {
+	$mod = ($xmax-1) * ($ymax-1);
+}
+
+my @nmaps;
+sub occupied($x,$y,$time) {
+	my $t = $time % $mod;
+	my $nmap = $nmaps[$t];
+	return $nmap->{"$x,$y"}
+		if defined $nmap;
+	for my $y (0 .. $ymax) {
+		for my $x (0 .. $xmax) {
+			next if ($map[$y][$x] eq '.');
+			my ($nx, $ny) = ($x, $y);
+			if ($map[$y][$x] eq '>') {
+				$nx = 1 + (($x+$t-1) % ($xmax-1));
+			} elsif ($map[$y][$x] eq 'v') {
+				$ny = 1 + (($y+$t-1) % ($ymax-1));
+			} elsif ($map[$y][$x] eq '^') {
+				$ny = 1 + (($y-$t-1) % ($ymax-1));
+			} elsif ($map[$y][$x] eq '<') {
+				$nx = 1 + (($x-$t-1) % ($xmax-1));
+			}
+			if ($nmap->{"$nx,$ny"}) {
+				if ($nmap->{"$nx,$ny"} =~ /\d/) {
+					$nmap->{"$nx,$ny"}++;
+				} else {
+					$nmap->{"$nx,$ny"} = 2;
+				}
+			} else {
+				$nmap->{"$nx,$ny"} = $map[$y][$x];
+			}
+		}
+	}
+	$nmaps[$t] = $nmap;
+	return $nmap->{"$x,$y"};
+}
+
+my @q = [3*($xmax+$ymax), 1, 0, 0, 0];
+my %seen;
+while (@q) {
+	my $now = pop_heap @q;
+	my ($dist, $x, $y, $time, $phase) = @$now;
+	my $key = join(',',$x, $y, ($time % $mod), $phase);
+	next if $seen{$key}++;
+	# say "at $x $y dist $dist time $time phase $phase";
+	if ($phase % 2 == 0) {
+		if ($x == $xmax-1 && $y == $ymax) {
+			if (++$phase == 3) {
+				say $time;
+				last;
+			}
+		}
+	} else {
+		if ($x == 1 && $y == 0) {
+			++$phase;
+		}
+	}
+
+	$time++;
+	$dist++;
+	my $add = ($phase % 2) ? -1 : 1;
+	if (!occupied($x,$y,$time)) {
+		push_heap @q, [ $dist, $x, $y, $time, $phase ];
+	}
+	if (!occupied($x+1,$y,$time)) {
+		push_heap @q, [ $dist-$add, $x+1, $y, $time, $phase ];
+	}
+	if (!occupied($x-1,$y,$time)) {
+		push_heap @q, [ $dist+$add, $x-1, $y, $time, $phase ];
+	}
+	if ($y < $ymax && !occupied($x,$y+1,$time)) {
+		push_heap @q, [ $dist-$add, $x, $y+1, $time, $phase ];
+	}
+	if ($y > 0 && !occupied($x,$y-1,$time)) {
+		push_heap @q, [ $dist+$add, $x, $y-1, $time, $phase ];
+	}
+}
+