TL;DR

On with Advent of Code puzzle 12 from 2022: solving the puzzle with a little human insight.

When I see path search puzzles my brain goes automatically to the A* algorithm. I know that going by default solutions can be dangerous, but I’ve got a Raku implementation and I want to use it when possible.

Let’s start from the beginning, i.e. reading the inputs:

sub get-inputs ($filename) { my @field =$filename.IO.lines.map(
{ .comb.map(
{
$_ eq 'S' ?? -101 !!$_ eq 'E' ?? 101
!! .ord - 'a'.ord
}).Array }
);
my (@start, @end);
for (^@field X ^@field) -> ($y,$x) {
if @field[$y][$x] < -100 { @start = $x,$y; @field[$y][$x] = 0 }
if @field[$y][$x] > 100  { @end   = $x,$y; @field[$y][$x] = 'z'.ord - 'a'.ord }
}
return {
start => @start,
end   => @end,
field => @field,
};
}


There must surely be a better way to do this! I’m especially ashamed about going through the field twice, so that i can properly track where the Start and the End are located. Whatever.

Part 1 of the puzzle is about finding the shortest path according to some rules for going upwards. I saw a meme or two about this, and I wholeheartedly agree: we can jump down as much as we want?!? Whatever.

So the solution is pretty straightforward:

sub part1 ($inputs) { my @path = path($inputs, $inputs<start>,$inputs<end>);
return @path.elems - 1;
}


Uh… ehm… right, this is path:

sub path ($inputs,$from, $to) { my \rows =$inputs<field>.elems;
my \cols = $inputs<field>.elems; my$nav = Astar.new(
distance => -> $u,$v { 1 },
successors => -> $pos { my ($px, $py) = @$pos;
my $max =$inputs<field>[$py][$px] + 1;
my @valid =
gather for ([$px-1,$py], [$px+1,$py], [$px,$py-1], [$px,$py+1]) -> ($x,$y) {
next unless 0 <= $y < rows && 0 <=$x < cols;
take [$x,$y] if $inputs<field>[$y][$x] <=$max;
};
@valid;
},
heuristic => {($^v «-»$^w).map(*²).sum.sqrt},
identifier => {$^v.join(',')}, ); return$nav.best-path($from,$to);
}


It’s just a wrapper around Astar to feed it the right data, with particular reference to finding the successors for each position.

Part 2 is supposed to be more challenging because it asks about finding another starting spot among… a lot of possible starting positions. I mean a lot.

The most clever apprach I saw about it is to reverse the search and start from the end, up until the closest a character in the map. I mean… Flavio, you might use your brain every now and then!

But I started brute-forcing it, just to understand that it was not the right way to go. There are so many candidates for the starting position that this is not feasible.

So I thought about looking at the inputs. There are many as and cs there… but whatever the starting point, it must have a b to make the first step, right?

So I went for the human-machine interface and looked at the input. Not general, I know, so my solution will most probably not be general at all. Whatever.

Then I saw that all bs are in the second column! Look by yourself:

abccccca...
abccccca...
abccccaa...
abcccaaa...
...
abaaaacc...
abaacccc...


Well… not really a clear view, right? Whatever.

This insight makes it possible to only check the a characters in the first column as a starting point:

sub part2 ($inputs) { my \rows =$inputs<field>.elems;
my \cols = $inputs<field>.elems; my$best = cols * rows;
for (0 X ^rows) -> ($x,$y) {
next if $inputs<field>[$y][$x] > 0; my @path = path($inputs, [$x,$y], $inputs<end>); my$n = @path.elems;
$best =$n if $best >$n;
}
return \$best - 1;
}


It’s not fast, it’s not smart… but it works!

Stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!