From 663a3716676ceb007561c8655b51cd9db84c8b5c Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Sun, 17 Dec 2023 07:12:38 +0100
Subject: [PATCH] Day 17: A-star using Array::Heap

---
 2023/33.pl | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 2023/34.pl | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 95 insertions(+)
 create mode 100755 2023/33.pl
 create mode 100755 2023/34.pl

diff --git a/2023/33.pl b/2023/33.pl
new file mode 100755
index 0000000..2187c71
--- /dev/null
+++ b/2023/33.pl
@@ -0,0 +1,47 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+use Array::Heap;
+$; = ';';
+
+my @map = map { chomp; [ split // ] } <>;
+my $xmax = $#{ $map[0] };
+my $ymax = $#map;
+
+my @dx = (1, 0, -1, 0);
+my @dy = (0, 1, 0, -1);
+
+my @q;
+push_heap @q, [ $xmax + $ymax, 0, 0, 0, 0, 0, [0, 0] ];
+my %min_cost;
+$min_cost{0,0,0,0} = 0; # $x, $y, $dir, $dist
+
+while (@q) {
+	my $node = pop_heap @q;
+	my ($w, $x, $y, $cost, $prevdir, $dist, @path) = @$node;
+
+	if ($x == $xmax && $y == $ymax) {
+		say "$cost : ", join(', ', map { join(',', @$_) } @path);
+		last;
+	}
+
+	for my $dir (0 .. 3) {
+		next if $dir == ($prevdir ^ 2);
+
+		my $nx = $x + $dx[$dir];
+		my $ny = $y + $dy[$dir];
+		next if $nx > $xmax || $ny > $ymax || $nx < 0 || $ny < 0;
+
+		my $ndist = ($dir == $prevdir) ? $dist+1 : 1;
+		next if $ndist > 3;
+
+		my $ncost = $cost + $map[$ny][$nx];
+		next if defined $min_cost{$nx,$ny,$dir,$ndist}
+			&& $min_cost{$nx,$ny,$dir,$ndist} <= $ncost;
+		$min_cost{$nx,$ny,$dir,$ndist} = $ncost;
+		my $nw = ($xmax-$nx) + ($ymax-$ny) + $ncost;
+		push_heap @q, [ $nw, $nx, $ny, $ncost, $dir, $ndist, @path, [$nx, $ny] ];
+	}
+}
+
diff --git a/2023/34.pl b/2023/34.pl
new file mode 100755
index 0000000..1df2b96
--- /dev/null
+++ b/2023/34.pl
@@ -0,0 +1,48 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+use Array::Heap;
+$; = ';';
+
+my @map = map { chomp; [ split // ] } <>;
+my $xmax = $#{ $map[0] };
+my $ymax = $#map;
+
+my @dx = (1, 0, -1, 0);
+my @dy = (0, 1, 0, -1);
+
+my @q;
+push_heap @q, [ $xmax + $ymax, 0, 0, 0, 4, [0, 0] ];
+my %min_cost;
+$min_cost{0,0,0} = 0; # $x, $y, $dir
+while (@q) {
+	my $node = pop_heap @q;
+	my ($w, $x, $y, $cost, $prevdir, @path) = @$node;
+
+	if ($x == $xmax && $y == $ymax) {
+		say "$cost : ", join(', ', map { join(',', @$_) } @path);
+		last;
+	}
+
+	DIR:
+	for my $dir (0 .. 3) {
+		next if $dir == ($prevdir ^ 2) || $dir == $prevdir;
+		my $nx = $x;
+		my $ny = $y;
+		my $ncost = $cost;
+		for (1 .. 10) {
+			$nx += $dx[$dir];
+			$ny += $dy[$dir];
+			next DIR if $nx > $xmax || $ny > $ymax || $nx < 0 || $ny < 0;
+			$ncost += $map[$ny][$nx];
+			next if $_ < 4;
+			next if defined $min_cost{$nx,$ny,$dir}
+				&& $min_cost{$nx,$ny,$dir} <= $ncost;
+			$min_cost{$nx,$ny,$dir} = $ncost;
+			my $nw = ($xmax-$nx) + ($ymax-$ny) + $ncost;
+			push_heap @q, [ $nw, $nx, $ny, $ncost, $dir, @path, [$nx, $ny] ];
+		}
+	}
+}
+
-- 
2.43.0