From 16e2246c542d001a5466401527213299847899b6 Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Sun, 24 Dec 2023 09:25:56 +0100
Subject: [PATCH] Day 23: quite slow to write

---
 2023/45.pl | 41 +++++++++++++++++++++++++
 2023/46.pl | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 131 insertions(+)
 create mode 100755 2023/45.pl
 create mode 100755 2023/46.pl

diff --git a/2023/45.pl b/2023/45.pl
new file mode 100755
index 0000000..28185b8
--- /dev/null
+++ b/2023/45.pl
@@ -0,0 +1,41 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+$; = ',';
+
+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 %seen;
+my @q = [ 1, 1, 1, [1, 1] ];
+while (@q) {
+	my ($x, $y, $steps, @path) = @{ shift @q };
+
+	next if $seen{$x,$y} && $seen{$x,$y} > $steps;
+	$seen{$x,$y} = $steps;
+	if ($x == $xmax-1 && $y == $ymax) {
+		say "at $x,$y, $steps, ", join(' ', map { "[$_->[0],$_->[1]]" } @path);
+		say "path len $steps";
+		next;
+	}
+	my %visited;
+	$visited{$_->[0],$_->[1]} = 1 for @path;
+	for my $d (0 .. 3) {
+		my $nx = $x + $dx[$d];
+		my $ny = $y + $dy[$d];
+		next if $map[$ny][$nx] eq '#';
+		next if $ny == 0;
+		next if $visited{$nx,$ny};
+		next if	$d != 0 && $map[$y][$x] eq '>';
+		next if	$d != 1 && $map[$y][$x] eq 'v';
+		next if	$d != 2 && $map[$y][$x] eq '<';
+		next if	$d != 3 && $map[$y][$x] eq '^';
+		push @q, [ $nx, $ny, $steps+1, @path, [ $nx, $ny ] ];
+	}
+}
+
diff --git a/2023/46.pl b/2023/46.pl
new file mode 100755
index 0000000..e6e8471
--- /dev/null
+++ b/2023/46.pl
@@ -0,0 +1,90 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+use Array::Heap;
+$; = ',';
+
+my @map = map { chomp; y/<>^v/..../; [ split // ] } <>;
+my $xmax = $#{ $map[0] };
+my $ymax = $#map;
+
+my @dx = (1, 0, -1, 0);
+my @dy = (0, 1, 0, -1);
+
+my @crossings = ([1, 0], [$xmax-1, $ymax]);
+
+for my $y (1 .. $ymax-1) {
+	for my $x (1 .. $xmax-1) {
+		next if $map[$y][$x] ne '.';
+		my $cnt;
+		for my $d (0 .. 3) {
+			my $nx = $x + $dx[$d];
+			my $ny = $y + $dy[$d];
+			$cnt++ if $map[$ny][$nx] eq '.';
+		}
+		next if $cnt <= 2;
+		say "cross ", scalar @crossings, " at $x,$y: $cnt";
+		push @crossings, [$x,$y];
+	}
+}
+
+my %is_cross;
+for (0 .. $#crossings) {
+	$is_cross{$crossings[$_]->[0],$crossings[$_]->[1]} = $_;
+}
+
+my %xnei;
+
+my %seen;
+my @q = [ 1, 1, 0, 0, 0 ];
+while (@q) {
+	my ($x, $y, $len, $prevx, $prevdist) = @{ shift @q };
+	
+	if (defined $is_cross{$x,$y}) {
+		my $self = $is_cross{$x,$y};
+		if (defined $prevx) {
+			if ($self != $prevx) {
+				my $l = $len - $prevdist;
+				say "$prevx-$self $l";
+				$xnei{$self}{$prevx} = $l;
+				$xnei{$prevx}{$self} = $l;
+			}
+		}
+		$prevx = $self;
+		$prevdist = $len;
+	}
+	next if $seen{$x,$y,$prevx}++;
+
+	for my $d (0 .. 3) {
+		my $nx = $x + $dx[$d];
+		my $ny = $y + $dy[$d];
+		next if $ny == 0;
+		next if $ny > $ymax;
+		next if $map[$ny][$nx] eq '#';
+		push @q, [$nx, $ny, $len+1, $prevx, $prevdist];
+	}
+}
+
+my $maxlen = 0;
+%seen = ();
+sub walk {
+	my ($self, $dist) = @_;
+
+	# say "at $self $dist @path";
+	if ($self == 1) {
+		if ($maxlen < $dist) {
+			$maxlen = $dist;
+			say "$dist";
+		}
+	}
+	$seen{$self} = 1;
+	for my $nxt (keys %{ $xnei{$self} }) {
+		next if $seen{$nxt};
+		walk($nxt, $dist + $xnei{$self}{$nxt});
+	}
+	$seen{$self} = 0;
+}
+
+walk(0, 1);
+
-- 
2.43.0