project euler problem 86 https projecteuler netproblem86 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 solution label the 3 sidelengths of the cuboid a b c such that 1 a b c m by conceptually opening up the cuboid and laying out its faces on a plane it can be seen that the shortest distance between 2 opposite corners is sqrtab2 c2 this distance is an integer if and only if ab c make up the first 2 sides of a pythagorean triplet the second useful insight is rather than calculate the number of cuboids with integral shortest distance for each maximum cuboid sidelength m we can calculate this number iteratively each time we increase m as follows the set of cuboids satisfying this property with maximum sidelength m1 is a subset of the cuboids satisfying the property with maximum sidelength m since any cuboids with side lengths m1 are also m to calculate the number of cuboids in the larger set corresponding to m we need only consider the cuboids which have at least one side of length m since we have ordered the side lengths a b c we can assume that c m then we just need to count the number of pairs a b satisfying the conditions sqrtab2 m2 is integer 1 a b m to count the number of pairs a b satisfying these conditions write d ab now we have 1 a b m 2 d 2m we can actually make the second equality strict since d 2m d2 m2 5m2 shortest distance m sqrt5 not integral a b d b d a and a b a d2 also a m a minm d2 a b d a d b and b m a d m also a 1 a max1 d m so a is in rangemax1 d m minm d 2 1 for a given d the number of cuboids satisfying the required property with c m and a b d is the length of this range which is minm d 2 1 max1 d m in the code below d is sumshortestsides and m is maxcuboidsize return the least value of m such that there are more than one million cuboids of side lengths 1 a b c m such that the shortest distance between two opposite vertices of the cuboid is integral solution100 24 solution1000 72 solution2000 100 solution20000 288 return the least value of m such that there are more than one million cuboids of side lengths 1 a b c m such that the shortest distance between two opposite vertices of the cuboid is integral solution 100 24 solution 1000 72 solution 2000 100 solution 20000 288
from math import sqrt


def solution(limit: int = 1000000) -> int:
    
    num_cuboids: int = 0
    max_cuboid_size: int = 0
    sum_shortest_sides: int

    while num_cuboids <= limit:
        max_cuboid_size += 1
        for sum_shortest_sides in range(2, 2 * max_cuboid_size + 1):
            if sqrt(sum_shortest_sides**2 + max_cuboid_size**2).is_integer():
                num_cuboids += (
                    min(max_cuboid_size, sum_shortest_sides // 2)
                    - max(1, sum_shortest_sides - max_cuboid_size)
                    + 1
                )

    return max_cuboid_size


if __name__ == "__main__":
    print(f"{solution() = }")