TheAlgorithms-Python

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

4
Magic 5-gon ring
5

6
Problem Statement:
7
Consider the following "magic" 3-gon ring,
8
filled with the numbers 1 to 6, and each line adding to nine.
9

10
   4
11
    \
12
     3
13
    / \
14
   1 - 2 - 6
15
  /
16
 5
17

18
Working clockwise, and starting from the group of three
19
with the numerically lowest external node (4,3,2 in this example),
20
each solution can be described uniquely.
21
For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.
22

23
It is possible to complete the ring with four different totals: 9, 10, 11, and 12.
24
There are eight solutions in total.
25
Total   Solution Set
26
9       4,2,3; 5,3,1; 6,1,2
27
9       4,3,2; 6,2,1; 5,1,3
28
10      2,3,5; 4,5,1; 6,1,3
29
10      2,5,3; 6,3,1; 4,1,5
30
11      1,4,6; 3,6,2; 5,2,4
31
11      1,6,4; 5,4,2; 3,2,6
32
12      1,5,6; 2,6,4; 3,4,5
33
12      1,6,5; 3,5,4; 2,4,6
34

35
By concatenating each group it is possible to form 9-digit strings;
36
the maximum string for a 3-gon ring is 432621513.
37

38
Using the numbers 1 to 10, and depending on arrangements,
39
it is possible to form 16- and 17-digit strings.
40
What is the maximum 16-digit string for a "magic" 5-gon ring?
41
"""
42

43
from itertools import permutations
44

45

46
def solution(gon_side: int = 5) -> int:
47
    """
48
    Find the maximum number for a "magic" gon_side-gon ring
49

50
    The gon_side parameter should be in the range [3, 5],
51
    other side numbers aren't tested
52

53
    >>> solution(3)
54
    432621513
55
    >>> solution(4)
56
    426561813732
57
    >>> solution()
58
    6531031914842725
59
    >>> solution(6)
60
    Traceback (most recent call last):
61
    ValueError: gon_side must be in the range [3, 5]
62
    """
63
    if gon_side < 3 or gon_side > 5:
64
        raise ValueError("gon_side must be in the range [3, 5]")
65

66
    # Since it's 16, we know 10 is on the outer ring
67
    # Put the big numbers at the end so that they are never the first number
68
    small_numbers = list(range(gon_side + 1, 0, -1))
69
    big_numbers = list(range(gon_side + 2, gon_side * 2 + 1))
70

71
    for perm in permutations(small_numbers + big_numbers):
72
        numbers = generate_gon_ring(gon_side, list(perm))
73
        if is_magic_gon(numbers):
74
            return int("".join(str(n) for n in numbers))
75

76
    msg = f"Magic {gon_side}-gon ring is impossible"
77
    raise ValueError(msg)
78

79

80
def generate_gon_ring(gon_side: int, perm: list[int]) -> list[int]:
81
    """
82
    Generate a gon_side-gon ring from a permutation state
83
    The permutation state is the ring, but every duplicate is removed
84

85
    >>> generate_gon_ring(3, [4, 2, 3, 5, 1, 6])
86
    [4, 2, 3, 5, 3, 1, 6, 1, 2]
87
    >>> generate_gon_ring(5, [6, 5, 4, 3, 2, 1, 7, 8, 9, 10])
88
    [6, 5, 4, 3, 4, 2, 1, 2, 7, 8, 7, 9, 10, 9, 5]
89
    """
90
    result = [0] * (gon_side * 3)
91
    result[0:3] = perm[0:3]
92
    perm.append(perm[1])
93

94
    magic_number = 1 if gon_side < 5 else 2
95

96
    for i in range(1, len(perm) // 3 + magic_number):
97
        result[3 * i] = perm[2 * i + 1]
98
        result[3 * i + 1] = result[3 * i - 1]
99
        result[3 * i + 2] = perm[2 * i + 2]
100

101
    return result
102

103

104
def is_magic_gon(numbers: list[int]) -> bool:
105
    """
106
    Check if the solution set is a magic n-gon ring
107
    Check that the first number is the smallest number on the outer ring
108
    Take a list, and check if the sum of each 3 numbers chunk is equal to the same total
109

110
    >>> is_magic_gon([4, 2, 3, 5, 3, 1, 6, 1, 2])
111
    True
112
    >>> is_magic_gon([4, 3, 2, 6, 2, 1, 5, 1, 3])
113
    True
114
    >>> is_magic_gon([2, 3, 5, 4, 5, 1, 6, 1, 3])
115
    True
116
    >>> is_magic_gon([1, 2, 3, 4, 5, 6, 7, 8, 9])
117
    False
118
    >>> is_magic_gon([1])
119
    Traceback (most recent call last):
120
    ValueError: a gon ring should have a length that is a multiple of 3
121
    """
122
    if len(numbers) % 3 != 0:
123
        raise ValueError("a gon ring should have a length that is a multiple of 3")
124

125
    if min(numbers[::3]) != numbers[0]:
126
        return False
127

128
    total = sum(numbers[:3])
129

130
    return all(sum(numbers[i : i + 3]) == total for i in range(3, len(numbers), 3))
131

132

133
if __name__ == "__main__":
134
    print(solution())
135