From: Jan "Yenya" Kasprzak <kas@fi.muni.cz>
Date: Thu, 21 Dec 2023 11:04:00 +0000 (+0100)
Subject: Day 21: examining the input
X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc.git;a=commitdiff_plain;h=cb7662a16eca1ff55e28338ef8ea7161224ac078

Day 21: examining the input
---

diff --git a/2023/41.pl b/2023/41.pl
new file mode 100755
index 0000000..34e72b5
--- /dev/null
+++ b/2023/41.pl
@@ -0,0 +1,54 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+$; = ';';
+
+my @map;
+my ($sx, $sy);
+
+while (<>) {
+	chomp;
+	if (/S/g) {
+		$sx = pos;
+		$sy = $.;
+		s/S/./;
+	}
+	push @map, [ split //, "#$_#" ];
+}
+my $xmax = $#{ $map[0] };
+my $ymax = $. + 1;
+
+push    @map, [ ('#') x ($xmax+1) ];
+unshift @map, [ ('#') x ($xmax+1) ];
+
+my %seen;
+
+my @dx = (1, 0, -1, 0);
+my @dy = (0, 1, 0, -1);
+
+my $steps = 64;
+my @q = ([ $sx, $sy, 0 ]);
+while (@q) {
+	my ($x, $y, $st) = @{ shift @q };
+	# say "$x $y";
+	next if $st >= $steps;
+	for my $d (0 .. 3) {
+		my $nx = $x + $dx[$d];
+		my $ny = $y + $dy[$d];
+		if ($map[$ny][$nx] eq '.') {
+			next if $seen{$nx,$ny,$st+1}++;
+			push @q, [ $nx, $ny, $st+1 ];
+		}
+	}
+}
+
+my $sum;
+for my $y (0 .. $ymax) {
+	for my $x (0 .. $xmax) {
+		print $seen{$x,$y,$steps} ? 'O' : $map[$y][$x];
+		$sum++ if $seen{$x,$y,$steps};
+	}
+	print "\n";
+}
+say $sum;
diff --git a/2023/42.pl b/2023/42.pl
new file mode 100755
index 0000000..ae9152b
--- /dev/null
+++ b/2023/42.pl
@@ -0,0 +1,69 @@
+#!/usr/bin/perl -w
+
+use v5.38;
+use experimental 'multidimensional';
+$; = ';';
+
+my @map;
+my ($sx, $sy);
+while (<>) {
+	chomp;
+	if (/S/g) {
+		$sx = pos()-1;
+		$sy = $.-1;
+		s/S/./;
+	}
+	push @map, [ split // ];
+}
+my $xmax = $#{ $map[0] };
+my $ymax = $. - 1;
+
+my @dx = (1, 0, -1, 0);
+my @dy = (0, 1, 0, -1);
+
+my @sums;
+my @oddeven;
+my @todo = [ $sx, $sy ];
+my %seen;
+$seen{$sx,$sy}++;
+
+for my $step (0 .. 1000) {
+	my @ntodo;
+	for my $pt (@todo) {
+		my ($x, $y) = @$pt;
+		$oddeven[$step & 1]++;
+		for my $d (0 .. 3) {
+			my $nx = $x + $dx[$d];
+			my $ny = $y + $dy[$d];
+			next if $map[$ny % ($ymax + 1)][$nx % ($xmax + 1)] ne '.';
+			next if $seen{$nx,$ny}++;
+			push @ntodo, [$nx, $ny];
+		}
+	}
+	
+	push @sums, $oddeven[$step & 1];
+	@todo = @ntodo;
+}
+
+my $start = 100;
+my $period = 1;
+my $steps = 26501365;
+
+PERIOD:
+while ($period++) {
+	for my $i ($start .. ($#sums - 3*$period)) {
+		my @d;
+		push @d, $sums[$i+($_+1)*$period]
+			-$sums[$i+$_*$period]
+			for 0 .. 2;
+		next PERIOD if $d[1]-$d[0] != $d[2]-$d[1];
+	}
+	last;
+}
+
+$start += ($steps - $start) % $period;
+my $a = $sums[$start+$period] - $sums[$start];
+my $d = $sums[$start+2*$period] - $sums[$start+$period] - $a;
+my $n = ($steps - $start) / $period;
+say $sums[$start] + (2*$a + ($n-1)*$d)*$n/2;
+