TL;DR

On with Advent of Code puzzle 24 from 2016: a brute-force approach to a problem similar to the Traveling Salesman Problem.

Puzzle 24 from the 2016 edition of Advent of Code is interesting because it forced me to look at it from the right angle.

It’s basically a maze with a few locations inside marked with a one-digit number; an agent (well, a small robot) starts at position 0 and has to to through all of the other locations with a digit ensuring that it does the least number of steps possible.

As I read it, it struck me that it’s similar to the Traveling Salesman Problem, with two notable exceptions:

• the path must not be necessarily closed (at least in part 1 of the puzzle 😉)
• it’s possible to go through the same location multiple times.

My gut feeling is that the complexity of the resulting algorithm does not really benefit from these two differences.

A two steps approach

This puzzle actually has two halves:

• first, it’s necessary to estimate what is the minimum distance between each pair of locations, taking into account paths allowed inside the maze;
• second, it’s necessary to arrange the locations in the right order so that the corresponding visit has the minimum length possible.

Distance between locations

To find out the distance between any pair of locations, I decided to do a double loop (to find out all possible pairs) and use the A* algorithm to find the minimum distance between them.

After this calculation, we are left with a simpler graph where the maze disappears and there are as many nodes as there are digit-marked locations in the maze (which is 8 locations in my case, marked from 0 to 7 included).

Path with minimum length

This is what resembles the Traveling Salesman Problem (at least from my point of view).

I already started thinking about possible arrangements, ways to memoize parts of the researches to prune stuff that would otherwise be evaluated multiple times, etc… because the very basic approach I had in mind grows factorially with the input size (that is, the number of marked locations).

Then I thought back on the approach and the factorial algorithm.

We are always required to start from the node marked with 0, and we know that each possible path will be that 0 followed by a permutation of the other locations. Going through all the permutations will provide us all the possible paths.

So, for example, these are two possible paths:

0 1 2 3 4 5 6 7

0 2 1 5 6 4 7 3

It’s then easy to calculate the length of each path because we have to consider each pair of adjacent locations in the specific path, and we have this from the previous section.

And yet… this goes factorially!

It’s not efficient at all!

I have to do something!

Wait a minute…

… I don’t have to solve a generic problem with an efficient solution here. I have to solve a very specific problem where there are only 8 locations and the number of possible paths is $7! = 5040$.

$5040$ is… nothing.

So yes… the good old brute force approach is perfect here! Which probably clarifies my interest for Permutations with Heap’s Algorithm lately 🙄

So the solution is readily available!

So it seems that the solution to part 1 is actually available through some integration of existing tools.

It turns out that the solution to part 2 is more or less the same, requiring the path to start at node 0 and end at node 0 too, which means that the two example paths above would turn into:

0 1 2 3 4 5 6 7 0

0 2 1 5 6 4 7 3 0

This has the same number of possible paths as before (i.e. $5040$) and the calculation function is basically the same as before, so we can reuse the code with small adjustments.

If you’re interested in the full Perl code you can find a local version here. Running it for both parts is… interesting:

$ time perl 24.pl 24.input
428 680

real  0m1.148s
user  0m1.108s
sys   0m0.016s

I have been on the brink of losing a lot of sleep hours… to pre-enhance a solution that takes so little.

So it’s true… premature optimization is the root of all evil!