# ETOOBUSY ðŸš€ minimal blogging for the impatient

# AoC 2016/24 - Brute-force for a Traveling-Salesman-like problem

**TL;DR**

On with Advent of Code puzzle 24 from 2016: a brute-force approach to a problem

similarto 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!