"""
Cuboid route

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.

The path is a diagonal along the 6x5 floor, then a diagonal up the 6x3 wall

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 math import sqrt
from time import time


def solve(target):
    """
    For an AxBxC room, A <= B <= C, the shortest path will be the hypotenuse of a right triangle with legs A+B and C.
    Start with C = M = 1, and find all A+B (x) values 2<=x<=2M with integer solutions. Then count the number of A,B
    combinations that lead to this right triangle.
    """
    solutions = 0
    M = 0
    while solutions < target:
        M += 1
        for x in range(2, 2 * M + 1):
            if sqrt(M ** 2 + x ** 2).is_integer():
                solutions += x // 2
                if x > M:
                    solutions -= x - M - 1
    return M


assert solve(2000) == 100
start = time()
print(solve(1000000))
print(time() - start)
