Problem 86 of Project Euler is the next problem I took up. Given a cuboid with integral dimensions, the shortest distance for an ant to crawl from one corner to diagonally opposite corner need not be an integral number. The problem statement required one to consider all the possible cuboid up to a maximum size of 
The question has a huge hint hidden within its wording. It goes on to provide two examples – for M = 99 the count is 1975 and for M = 100 the count is 2060! Solve the problem incrementally. This problem can be disintegrated into 3 smaller problems.
Firstly, we need to know the calculation of shortest path in a cuboid as an ant would crawl. To do this, explode the 3D figure into a 2D figure keeping track of the corners. It’s a pretty simple matter to calculate the distance now. There’s one thing to be remembered though – the explosion can be done in 3 different ways. So we have potentially 3 candidates for the shortest path.
Given the dimension as 
Next we tackle the problem of induction. Say we know that the count for the problem size 
i X j X (M+1)
where i = 1 to M + 1
and j = i to M + 1
There lies our solution! We setup a nested for loop and calculate the shortest distances for each of these extra cuboid. It should now be pretty obvious to notice that for the computation of shortest distance we only need to consider the case 
I hope you have noticed some redundancy in the above loop setup. Every time we calculate 
i = 1, j = 3
i = 2, j = 2
In both these cases the value of (i+j) is the same. We are unnecessarily computing values already computed. Being a little cleverer we can improve the current 
Instead of using a nested loop, we use a single for-loop from the range of 2 to 2*(M+1) as those are the range for the sum of i and j. But this introduces another problem. Say for a particular sum we get that the shortest path is an integer. We need to know the number of ways in which the sum can be decomposed into i and j. I setup a single line function to calculate this value and I was done!
The code ran in 258ms on my Lenovo T410 laptop. Below is my function to move from M to M+1. To solve the Project Euler problem, I just needed to call this function in a loop, always updating the memoized value.
/**
* Count the number of integral shortest paths in all cuboids upto a size of size X size X size
*
* @param size the maximum dimensions of the cuboid
* @param memoizedValue the value for a cuboid with max dimension size - 1
* @return the value for a cuboid of max dimension size X size X size
*/
public int countIntegralShortDistances(int size, int memoizedValue) {
double sizeSquared = Math.pow(size, 2);
for (int i = 2; i <= 2 * size; i++)
if (NumberUtil.isInteger(Math.sqrt(Math.pow(i, 2) + sizeSquared))) memoizedValue += NumberUtil
.countSummations(i, size);
return memoizedValue;
}
Popularity: 14% [?]
