TheAlgorithms-Python

1
"""
2
Project Euler Problem 86: https://projecteuler.net/problem=86
3

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

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

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

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

18
Solution:
19
    Label the 3 side-lengths of the cuboid a,b,c such that 1 <= a <= b <= c <= M.
20
    By conceptually "opening up" the cuboid and laying out its faces on a plane,
21
    it can be seen that the shortest distance between 2 opposite corners is
22
    sqrt((a+b)^2 + c^2). This distance is an integer if and only if (a+b),c make up
23
    the first 2 sides of a pythagorean triplet.
24

25
    The second useful insight is rather than calculate the number of cuboids
26
    with integral shortest distance for each maximum cuboid side-length M,
27
    we can calculate this number iteratively each time we increase M, as follows.
28
    The set of cuboids satisfying this property with maximum side-length M-1 is a
29
    subset of the cuboids satisfying the property with maximum side-length M
30
    (since any cuboids with side lengths <= M-1 are also <= M). To calculate the
31
    number of cuboids in the larger set (corresponding to M) we need only consider
32
    the cuboids which have at least one side of length M. Since we have ordered the
33
    side lengths a <= b <= c, we can assume that c = M. Then we just need to count
34
    the number of pairs a,b satisfying the conditions:
35
        sqrt((a+b)^2 + M^2) is integer
36
        1 <= a <= b <= M
37

38
    To count the number of pairs (a,b) satisfying these conditions, write d = a+b.
39
    Now we have:
40
        1 <= a <= b <= M  =>  2 <= d <= 2*M
41
                                   we can actually make the second equality strict,
42
                                   since d = 2*M => d^2 + M^2 = 5M^2
43
                                              => shortest distance = M * sqrt(5)
44
                                              => not integral.
45
        a + b = d => b = d - a
46
                 and a <= b
47
                  => a <= d/2
48
                also a <= M
49
                  => a <= min(M, d//2)
50

51
        a + b = d => a = d - b
52
                 and b <= M
53
                  => a >= d - M
54
                also a >= 1
55
                  => a >= max(1, d - M)
56

57
        So a is in range(max(1, d - M), min(M, d // 2) + 1)
58

59
    For a given d, the number of cuboids satisfying the required property with c = M
60
    and a + b = d is the length of this range, which is
61
        min(M, d // 2) + 1 - max(1, d - M).
62

63
    In the code below, d is sum_shortest_sides
64
                   and M is max_cuboid_size.
65

66

67
"""
68

69
from math import sqrt
70

71

72
def solution(limit: int = 1000000) -> int:
73
    """
74
    Return the least value of M such that there are more than one million cuboids
75
    of side lengths 1 <= a,b,c <= M such that the shortest distance between two
76
    opposite vertices of the cuboid is integral.
77
    >>> solution(100)
78
    24
79
    >>> solution(1000)
80
    72
81
    >>> solution(2000)
82
    100
83
    >>> solution(20000)
84
    288
85
    """
86
    num_cuboids: int = 0
87
    max_cuboid_size: int = 0
88
    sum_shortest_sides: int
89

90
    while num_cuboids <= limit:
91
        max_cuboid_size += 1
92
        for sum_shortest_sides in range(2, 2 * max_cuboid_size + 1):
93
            if sqrt(sum_shortest_sides**2 + max_cuboid_size**2).is_integer():
94
                num_cuboids += (
95
                    min(max_cuboid_size, sum_shortest_sides // 2)
96
                    - max(1, sum_shortest_sides - max_cuboid_size)
97
                    + 1
98
                )
99

100
    return max_cuboid_size
101

102

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