-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patheuler_061.py
73 lines (64 loc) · 3.21 KB
/
euler_061.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
64
65
66
67
68
69
70
71
72
73
# (Euler 61)
# Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers
# and are generated by the following formulae:
#
# Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
# Square P4,n=n^2 1, 4, 9, 16, 25, ...
# Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
# Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
# Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
# Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, ...
#
# The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
#
# 1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number
# (including the last number with the first).
# 2. Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882),
# is represented by a different number in the set.
# 3. This is the only set of 4-digit numbers with this property.
#
# Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type:
# triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
from itertools import permutations
from figurate_numbers import *
def is_cyclic_set(numbers):
numbers = [str(x) for x in numbers]
# check they are all length 4
if not all([len(x)==4 for x in numbers]):
return False
for i in range(len(numbers)):
if numbers[i][-2:] != numbers[(i+1)%len(numbers)][:2]:
return False
return True
def is_cyclic_and_contains_types(numbers, types):
return is_cyclic_set(numbers) and all([any([type_test(x) for x in numbers]) for type_test in types])
def find_next_terms(current_terms, missing_groups, tests):
if len(missing_groups) == 0:
if is_cyclic_and_contains_types(current_terms, tests):
print("{}, sum: {}".format(current_terms, sum(current_terms)))
exit()
else:
return
if len(current_terms) == 0:
gr = missing_groups.pop()
for x in gr:
find_next_terms([x], missing_groups, tests)
return
last_term_digits = str(current_terms[-1])[-2:]
for mg in permutations(missing_groups):
mg = list(mg)
next_group = mg.pop()
for next_term in [i for i in next_group if last_term_digits == str(i)[:2]]:
find_next_terms(current_terms+[next_term], mg, tests)
def solve_061():
# get list of 4-digit numbers, and the 3rd cannot be 0 as they cannot be cyclical
tri = [x for x in range(1000,10000) if is_triangular(x) and "0" != str(x)[2]]
sqr = [x for x in range(1000,10000) if is_square(x) and "0" != str(x)[2]]
pen = [x for x in range(1000,10000) if is_pentagonal(x) and "0" != str(x)[2]]
hex = [x for x in range(1000,10000) if is_hexagonal(x) and "0" != str(x)[2]]
hep = [x for x in range(1000,10000) if is_heptagonal(x) and "0" != str(x)[2]]
oct = [x for x in range(1000,10000) if is_octagonal(x) and "0" != str(x)[2]]
all_figurate_tests = [is_triangular, is_square, is_pentagonal, is_hexagonal, is_heptagonal, is_octagonal]
find_next_terms([], [tri,sqr,pen,hex,hep,oct], all_figurate_tests)
if __name__ == '__main__':
solve_061()