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!