Reading the description of Problem 86 gives me a headache. Every time I am convinced that I finally got it, I begin to drool, wee myself and have to start over. What an excellent premise for a new blog post.

This is Problem 86 in all its glory:

The first part is easy to understand. A happy little spider is put onto a cuboid and walks from corner S to corner F.

It is stated that, given the exact measurements of the cuboid, the length of the shortest possible path from point S to point F is 10. How’s that?

Back to elementary school where I learned how to build a paper die.

That’s how the given cuboid looks unfolded. By applying some basic math it is now easy to calculate the distance between S and F. As it is a straight line it is indeed the shortest route from S to F. It is also the hypotenuse h of a right-angled triangle. Therefore…

The distance between S and F does not have to be of integer value though. Just imagine a cuboid having slightly different measurements.

So far so good. Let’s continue. The part about “up to three shortest path candidates” can be simple ignored. Interesting but not necessary to solve this particular problem.

Back to calculating h.

And applied to the cuboid:

That’s the formula to get the shortest route h. Just remember that we are only interested in integer values of h. So we will need a check for that.

The cuboid is of volume a x b x c. It is safe to assume that all are of integer value as the problem description does not state otherwise. We can start with 1 for a, b and c, with a maximum value of M. For example we can have cuboids of volume 1 x 1 x 1, 1 x 1 x 2, 1 x 1 x 3 and so on up to M x M x M.

Each increase of a, b or c will result in a different cuboid. And for each of these cuboids (at least) one shortest route from S to F exists.

We now have to find the least value of M, where the total number of shortest routes exceeds 1.000.000.

Let’s suppose M = 1. That’s simple. We only have a single 1 x 1 x 1 cuboid. And only one solution for h, which is 2.23. This does not qualify as it is not of integer value. Our total count would be still 0.

Let’s suppose M = 2. What kind of cuboids can we build?
1 x 1 x 1: no integer solution for h
1 x 1 x 2: no integer solution for h
1 x 2 x 1: no integer solution for h
1 x 2 x 2: no integer solution for h
2 x 1 x 1: no integer solution for h
2 x 1 x 2: no integer solution for h
2 x 2 x 1: no integer solution for h
2 x 2 x 2: no integer solution for h

Still a total count of 0.

What might be not so obvious right away is that we have duplicates here. The problem description states that rotations can be ignored. So which ones are actually duplicates?

1 x 1 x 1: unique cuboid
1 x 1 x 2: first unique occurrence of cuboid
1 x 2 x 1: rotation of 1 x 1 x 2
1 x 2 x 2: first unique occurrence of cuboid
2 x 1 x 1: rotation of 1 x 1 x 2
2 x 1 x 2: rotation of 1 x 2 x 2
2 x 2 x 1: rotation of 1 x 2 x 2
2 x 2 x 2: unique cuboid

Note: Even though some cuboids are just a rotation of other cuboids the result for h will be different.

But in the end it’s actually just:

(a x b x c)
1 x 1 x 1
1 x 1 x 2
1 x 2 x 2
2 x 2 x 2

And that looks like a simple for-lop ranging from 1 to M = 2 where always a >= b >= c (or c <= b <= a).

Let’s increase M one more time to M = 3. When do we have the first integer solution for h? If I’m correct this would be 3 x 2 x 2.

Let’s sum it up. We have a simple formula to calculate h. We also know that we could use a simple for-loop to gradually increase the size of our cuboids. What else do we need? Definitely we need to keep count of the integer occurrences of h because we have to abort the creation of cuboids when we reach a certain limit. Namely 1.000.000.

And once we abort, we are only interested in the value of a. That’s all.

I refer from posting my source code here. But this should be explanation enough so you can start coding a solution yourself. Good luck and have fun!