From: Jan "Yenya" Kasprzak <kas@fi.muni.cz>
Date: Wed, 15 Dec 2021 06:30:12 +0000 (+0100)
Subject: Day 15: too slow
X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc2021.git;a=commitdiff_plain;h=0febc3a8a728adf5c84e9049f443b85414bfcb79

Day 15: too slow
---

diff --git a/29.pl b/29.pl
new file mode 100755
index 0000000..d4a2441
--- /dev/null
+++ b/29.pl
@@ -0,0 +1,34 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use Data::Dumper;
+
+$; = ',';
+my @m;
+my ($maxx, $maxy) = (0, 0);
+while (<>) {
+	chomp;
+	push @m, [ split // ];
+	$maxx = length;
+	$maxy++;
+}
+
+my %cost = ("0,0" => 0);
+my @todo = ([0, 0]);
+
+while (my $p = shift @todo) {
+	my ($sx, $sy) = @$p;
+	for my $d ([ 0, 1], [0, -1], [1, 0], [-1, 0]) {
+		my $dx = $sx + $d->[0];
+		my $dy = $sy + $d->[1];
+		next if $dx < 0 || $dx >= $maxx || $dy < 0 || $dy >= $maxy;
+		if (!defined $cost{$dx,$dy}
+			|| $cost{$dx,$dy} > $cost{$sx,$sy} + $m[$dy][$dx]) {
+			$cost{$dx,$dy} = $cost{$sx,$sy} + $m[$dy][$dx];
+			push @todo, [$dx,$dy];
+		}
+	}
+}
+
+say $cost{$maxx-1,$maxy-1};
+
diff --git a/30.pl b/30.pl
new file mode 100755
index 0000000..8cee293
--- /dev/null
+++ b/30.pl
@@ -0,0 +1,46 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use Data::Dumper;
+
+$; = ',';
+my @m1;
+my ($maxx, $maxy) = (0, 0);
+while (<>) {
+	chomp;
+	push @m1, [ split(//) ];
+	$maxx = length;
+}
+$maxy = @m1;
+
+my @m;
+$maxx *= 5;
+$maxy *= 5;
+
+for my $x (0 .. $maxx-1) {
+for my $y (0 .. $maxy-1) {
+	my $add = int($x*5/$maxx)+int($y*5/$maxy);
+	my $x1 = $x % ($maxx/5);
+	my $y1 = $y % ($maxy/5);
+	$m[$y][$x] = $m1[$y1][$x1] + $add;
+	$m[$y][$x] -= 9 if $m[$y][$x] > 9;
+} }
+
+my %cost = ("0,0" => 0);
+my @todo = ([0, 0]);
+
+while (my $p = shift @todo) {
+	my ($sx, $sy) = @$p;
+	for my $d ([ 0, 1], [0, -1], [1, 0], [-1, 0]) {
+		my $dx = $sx + $d->[0];
+		my $dy = $sy + $d->[1];
+		next if $dx < 0 || $dx >= $maxx || $dy < 0 || $dy >= $maxy;
+		if (!defined $cost{$dx,$dy}
+			|| $cost{$dx,$dy} > $cost{$sx,$sy} + $m[$dy][$dx]) {
+			$cost{$dx,$dy} = $cost{$sx,$sy} + $m[$dy][$dx];
+			push @todo, [$dx,$dy];
+		}
+	}
+}
+
+say $cost{$maxx-1,$maxy-1};