-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem61.py
73 lines (58 loc) · 2.71 KB
/
problem61.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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Project Euler Problem 61:
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are
generated by the following formulae:
Triangle P(3,n)=n(n+1)/2 1, 3, 6, 10, 15, ...
Square P(4,n)=n^2 1, 4, 9, 16, 25, ...
Pentagonal P(5,n)=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal P(6,n)=n(2n−1) 1, 6, 15, 28, 45, ...
Heptagonal P(7,n)=n(5n−3)/2 1, 7, 18, 34, 55, ...
Octagonal P(8,n)=n(3n−2) 1, 8, 21, 40, 65, ...
The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
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).
Each polygonal type: triangle (P(3,127)=8128), square (P(4,91)=8281), and pentagonal (P(5,44)=2882), is represented by a
different number in the set.
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.
"""
# Generates a map of {first 2 digits: last 2 digits} for each 4-digit n-gonal number, then uses recursion to find a path
# through all 6 maps that ends at the same 2 digits as it starts at. Runs in ~80ms.
from itertools import count
# Generate all n-gonal maps of first 2 digits to last 2 digits
def get_ngonal_map(func):
ngonal_map = {}
for n in map(func, count(1)):
if n > 9999:
break
if n > 999:
first, last = divmod(n, 100)
ngonal_map[first] = last
return ngonal_map
ngonal_maps = list(map(get_ngonal_map, [
lambda n: n * (n + 1) // 2, # triangular
lambda n: n * n, # square
lambda n: n * (3*n - 1) // 2, # pentagonal
lambda n: n * (2*n - 1), # hexagonal
lambda n: n * (5*n - 3) // 2, # heptagonal
lambda n: n * (3*n - 2), # octagonal
]))
# Find a path that touches all of them (starting with the triangular map)
def search(digit_set, remaining_ngonal_maps=ngonal_maps[1:]):
if not remaining_ngonal_maps:
yield digit_set
return
n = digit_set[-1]
for i, ngonal_map in enumerate(remaining_ngonal_maps):
if n in ngonal_map:
yield from search([*digit_set, ngonal_map[n]], remaining_ngonal_maps[:i] + remaining_ngonal_maps[i+1:])
def find_cyclic_polygonal():
for n0, n1 in ngonal_maps[0].items():
for digit_set in search([n1]):
if digit_set[-1] == n0:
return digit_set
digit_set = find_cyclic_polygonal()
print(sum(map(lambda x: x[0]*100 + x[1], list(zip(digit_set, digit_set[1:])) + [(digit_set[-1], digit_set[0])])))