# ETOOBUSY ðŸš€ minimal blogging for the impatient

# AoC 2021/15 - A* in the sea

**TL;DR**

On with Advent of Code puzzle 15 from 2021: using A*.

This dayâ€™s puzzle was about finding a path through a field according to a minimization principle, which is somehow textbook for search algorithms.

A lot of people used Dijkstraâ€™s Algorithm but I thought of
re-using my A* implementation from
cglib-raku. I was *not* thrilled with the results, though: thereâ€™s
probably ample space for improvement.

Anyway, I learned that using *integers* instead of strings for
identifying the different nodes gave some execution boost that was good
to see.

The core of the solution is in the implementation for part 1, as part 2 is basically the same with different parameters:

```
sub part1 ($b, :$kr = 1, :$kc = 1) {
my $size = [$b.elems, $b[0].elems];
my $max = ($size Â«*Â» ($kr, $kc)) Â«-Â» (1, 1);
my $row-size = $max[1] + 1;
my &cost = -> $p {
my $v = $p Â«%Â» $size;
my $base = $b[$v[0]][$v[1]];
my $shift = ($p Â«/Â» $size)Â».Int.sum;
1 + ($base + $shift - 1) % 9;
};
my $astar = Astar.new(
heuristic => -> $v, $w { ($v Â«-Â» $w)Â».abs.sum },
distance => -> $v, $w { &cost($w) },
identifier => -> $v { $v[0] * $row-size + $v[1] },
successors => -> $v {
((1, 0), (0, 1), (-1, 0), (0, -1)).map({ $v Â«+Â» $_ })
.grep({.min >= 0 && ($max Â«-Â» $_).min >= 0});
},
);
my $path = $astar.best-path([0, 0], $max);
return $path.map(&cost).sum - $b[0][0];
}
```

The heuristic is a basic Manhattan distance, which plays well with the movement restrictions (no diagonals) and with the heuristicâ€™s constraint for optimality (i.e. not overestimating the actual distance). Itâ€™s probably not great, though, and the whole thing is likely collapsing to plain Dijkstra.

As anticipating, Iâ€™m using an integer for the identifier, although it is
anyway stringified in the algorithmâ€™s implementation. It does not excel
in performanceâ€¦ but it works `Â¯\_(ãƒ„)_/Â¯`

.

Finding the successors is an occasion to show off some meta-operations:
we iterate through the allowable displacements and apply them to the
current position using `Â«+Â»`

. To check if the result is within the bound
we still apply meta stuff.

The result if found by summing the elements in the whole pathâ€¦ except for the starting tile, whose cost must be ignored by explicit requirement.

Well, enough for todayâ€¦ stay safe and have `-Ofun`

people!

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