problem86.py

"""
Cuboid Routes
Project Euler Problem #86
by Muaz Siddiqui

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.


However, there are up to three "shortest" path candidates for any given cuboid and 
the shortest route doesn't always have integer length.

It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, 
with integer dimensions, up to a maximum size of M by M by M, for which the 
shortest route has integer length when M = 100. This is the least value of M for 
which the number of solutions first exceeds two thousand; the number of solutions 
when M = 99 is 1975.

Find the least value of M such that the number of solutions first exceeds one 
million.
"""
from euler_helpers import timeit, is_square
from math import sqrt
# Shortest path in a cuboid is given by path = (l^2 + (w+h)^2)^0.5
# M in this case will be the length l
@timeit
def answer():
    m = 2
    solutions = 0
    while solutions < 1000000:
        m += 1
        for w in range(3, 2*m):
            if not w*m % 12:
                if not sqrt(w*w + m*m) %1:
                    solutions += w/2 if w <= m else (m - (w+1)/2) + 1
    return m