This repository has been archived by the owner on Apr 18, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
68.py
63 lines (54 loc) · 2.33 KB
/
68.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import operator
from functools import partial
from itertools import (chain,
permutations)
from typing import (Iterable,
Tuple,
List)
from utils import has_n_elements
LINE_LENGTH = 3
MagicNGonRingType = List[Tuple[int, int, int]]
def ring_to_string(ring: MagicNGonRingType) -> str:
return ''.join(map(str, chain(*ring)))
def magic_n_gon_rings(numbers: Iterable[int],
*,
n: int) -> Iterable[MagicNGonRingType]:
for line in permutations(numbers, LINE_LENGTH):
first_start = line[0]
target_sum = sum(line)
rest_numbers = set(numbers) - set(line)
next_starts_candidates = filter(partial(operator.lt,
first_start),
rest_numbers)
for next_starts in permutations(next_starts_candidates,
r=n - 1):
ring = [line]
next_ends_candidates = rest_numbers - set(next_starts)
next_middle = line[-1]
*next_starts, last_start = next_starts
for next_start in next_starts:
next_end = target_sum - next_start - next_middle
if next_end not in next_ends_candidates:
break
next_line = next_start, next_middle, next_end
ring.append(next_line)
next_middle = next_end
else:
last_line = last_start, next_middle, line[1]
if sum(last_line) != target_sum:
continue
ring.append(last_line)
yield ring
# reversing numbers order gives us maximum on the first entry
magic_3_gon_rings = magic_n_gon_rings(range(6, 0, -1),
n=3)
magic_3_gon_rings_strings = map(ring_to_string,
magic_3_gon_rings)
magic_5_gon_rings = magic_n_gon_rings(range(10, 0, -1),
n=5)
magic_5_gon_rings_strings = map(ring_to_string,
magic_5_gon_rings)
has_sixteen_elements = partial(has_n_elements, n=16)
assert next(magic_3_gon_rings_strings) == '432621513'
assert next(filter(has_sixteen_elements,
magic_5_gon_rings_strings)) == '6531031914842725'