Project Euler Problem 086

Statement

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.

p_086.gif

However, there are up to three "shortest" path candidates for any given cuboid and the shortest route is not always integer.

By considering all cuboid rooms with integer dimensions, up to a maximum size of M by M by M, there are exactly 2060 cuboids for which the shortest distance is integer when M=100, and this is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions is 1975 when M=99.

Find the least value of M such that the number of solutions first exceeds one million.

Solution

I use an incremental search on the M until I find the first value that after processing it I have more than 106 boxes.

In each iteration what we need to calculate is all of the possible combination of values, but like they are going to be combined to calculate the distance instead of writing a double nested for loop what we just need is the different sums. As the sides can go from 1 to M the sums can go from 2(1 + 1) to 2M inclusive. If using those values we have an integer side for the path then: how many different combinations of 2 valid side's sizes give that sum?

Solving that riddle is really easy: if the number is X, the possible sides to get it go from (1, X-1) to (X/2, X/2) but they can be invalid, the top value can't go higher than M. So we are keeping the minimum between X/2 and M - X/2 + 1. The plus 1 is important because M counts.

Translated this into code for python 3:

if __name__ == '__main__':
    cant = 0
    limit = 10 ** 6
    m = 0
    while cant <= limit:
        m += 1
        m_sq = m ** 2
        for l23 in range(2, m*2 + 1):
            l23_sq = l23 ** 2
            side = m_sq + l23_sq
            sq = int(side**(.5))
            if sq**2 == side:
                to_sum = min(l23 // 2, int(m - l23 / 2) + 1)
                cant += to_sum
    print("The result is:", m)

The Python3 file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License