Project Euler – Cuboid route

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:

screenshot_3990.png

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.

screenshot_3991.png

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…

screenshot_3992.png

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

screenshot_3994.png

screenshot_3995.png

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.

screenshot_4001

And applied to the cuboid:

screenshot_4003

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s