From fe4d8ec08525af68241a04efd036d28d4d9ab542 Mon Sep 17 00:00:00 2001 From: "Jan \"Yenya\" Kasprzak" Date: Sat, 24 Dec 2022 07:13:17 +0100 Subject: [PATCH] Day 24: priority queue with memoization --- 2022/47.pl | 82 ++++++++++++++++++++++++++++++++++++++++++++++++ 2022/48.pl | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 174 insertions(+) create mode 100755 2022/47.pl create mode 100755 2022/48.pl diff --git a/2022/47.pl b/2022/47.pl new file mode 100755 index 0000000..1a61d2e --- /dev/null +++ b/2022/47.pl @@ -0,0 +1,82 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use Array::Heap; + +my @map = map { chomp; [ split // ] } <>; +my $xmax = $#{$map[0]}; +my $ymax = $#map; + +my $mod; +if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD + $mod = 700; +} else { + $mod = ($xmax-1) * ($ymax-1); +} + +my @nmaps; +sub occupied($x,$y,$time) { + my $t = $time % $mod; + my $nmap = $nmaps[$t]; + return $nmap->{"$x,$y"} + if defined $nmap; + for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + next if ($map[$y][$x] eq '.'); + my ($nx, $ny) = ($x, $y); + if ($map[$y][$x] eq '>') { + $nx = 1 + (($x+$t-1) % ($xmax-1)); + } elsif ($map[$y][$x] eq 'v') { + $ny = 1 + (($y+$t-1) % ($ymax-1)); + } elsif ($map[$y][$x] eq '^') { + $ny = 1 + (($y-$t-1) % ($ymax-1)); + } elsif ($map[$y][$x] eq '<') { + $nx = 1 + (($x-$t-1) % ($xmax-1)); + } + if ($nmap->{"$nx,$ny"}) { + if ($nmap->{"$nx,$ny"} =~ /\d/) { + $nmap->{"$nx,$ny"}++; + } else { + $nmap->{"$nx,$ny"} = 2; + } + } else { + $nmap->{"$nx,$ny"} = $map[$y][$x]; + } + } + } + $nmaps[$t] = $nmap; + return $nmap->{"$x,$y"}; +} + +my @q = [$xmax+$ymax, 1, 0, 0]; +my %seen; +while (@q) { + my $now = pop_heap @q; + my ($dist, $x, $y, $time) = @$now; + my $key = join(',',$x, $y, ($time % $mod)); + next if $seen{$key}++; + # say "at $x $y dist $dist time $time"; + if ($x == $xmax-1 && $y == $ymax) { + say "$time"; + last; + } + $time++; + $dist++; + if (!occupied($x,$y,$time)) { + push_heap @q, [ $dist, $x, $y, $time ]; + } + if (!occupied($x+1,$y,$time)) { + push_heap @q, [ $dist-1, $x+1, $y, $time ]; + } + if (!occupied($x-1,$y,$time)) { + push_heap @q, [ $dist+1, $x-1, $y, $time ]; + } + if (!occupied($x,$y+1,$time)) { + push_heap @q, [ $dist-1, $x, $y+1, $time ]; + } + if ($y > 1 && !occupied($x,$y-1,$time)) { + push_heap @q, [ $dist+1, $x, $y-1, $time ]; + } +} + diff --git a/2022/48.pl b/2022/48.pl new file mode 100755 index 0000000..adde9f8 --- /dev/null +++ b/2022/48.pl @@ -0,0 +1,92 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use Array::Heap; + +my @map = map { chomp; [ split // ] } <>; +my $xmax = $#{$map[0]}; +my $ymax = $#map; + +my $mod; +if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD + $mod = 700; +} else { + $mod = ($xmax-1) * ($ymax-1); +} + +my @nmaps; +sub occupied($x,$y,$time) { + my $t = $time % $mod; + my $nmap = $nmaps[$t]; + return $nmap->{"$x,$y"} + if defined $nmap; + for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + next if ($map[$y][$x] eq '.'); + my ($nx, $ny) = ($x, $y); + if ($map[$y][$x] eq '>') { + $nx = 1 + (($x+$t-1) % ($xmax-1)); + } elsif ($map[$y][$x] eq 'v') { + $ny = 1 + (($y+$t-1) % ($ymax-1)); + } elsif ($map[$y][$x] eq '^') { + $ny = 1 + (($y-$t-1) % ($ymax-1)); + } elsif ($map[$y][$x] eq '<') { + $nx = 1 + (($x-$t-1) % ($xmax-1)); + } + if ($nmap->{"$nx,$ny"}) { + if ($nmap->{"$nx,$ny"} =~ /\d/) { + $nmap->{"$nx,$ny"}++; + } else { + $nmap->{"$nx,$ny"} = 2; + } + } else { + $nmap->{"$nx,$ny"} = $map[$y][$x]; + } + } + } + $nmaps[$t] = $nmap; + return $nmap->{"$x,$y"}; +} + +my @q = [3*($xmax+$ymax), 1, 0, 0, 0]; +my %seen; +while (@q) { + my $now = pop_heap @q; + my ($dist, $x, $y, $time, $phase) = @$now; + my $key = join(',',$x, $y, ($time % $mod), $phase); + next if $seen{$key}++; + # say "at $x $y dist $dist time $time phase $phase"; + if ($phase % 2 == 0) { + if ($x == $xmax-1 && $y == $ymax) { + if (++$phase == 3) { + say $time; + last; + } + } + } else { + if ($x == 1 && $y == 0) { + ++$phase; + } + } + + $time++; + $dist++; + my $add = ($phase % 2) ? -1 : 1; + if (!occupied($x,$y,$time)) { + push_heap @q, [ $dist, $x, $y, $time, $phase ]; + } + if (!occupied($x+1,$y,$time)) { + push_heap @q, [ $dist-$add, $x+1, $y, $time, $phase ]; + } + if (!occupied($x-1,$y,$time)) { + push_heap @q, [ $dist+$add, $x-1, $y, $time, $phase ]; + } + if ($y < $ymax && !occupied($x,$y+1,$time)) { + push_heap @q, [ $dist-$add, $x, $y+1, $time, $phase ]; + } + if ($y > 0 && !occupied($x,$y-1,$time)) { + push_heap @q, [ $dist+$add, $x, $y-1, $time, $phase ]; + } +} + -- 2.43.5