]> www.fi.muni.cz Git - aoc.git/commitdiff
Day 15: too slow
authorJan "Yenya" Kasprzak <kas@fi.muni.cz>
Wed, 15 Dec 2021 06:30:12 +0000 (07:30 +0100)
committerJan "Yenya" Kasprzak <kas@fi.muni.cz>
Wed, 15 Dec 2021 06:30:12 +0000 (07:30 +0100)
29.pl [new file with mode: 0755]
30.pl [new file with mode: 0755]

diff --git a/29.pl b/29.pl
new file mode 100755 (executable)
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 (executable)
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};