134 lines
3.4 KiB
Python
134 lines
3.4 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.
|
|
#
|
|
# 4
|
|
# \
|
|
# \
|
|
# 3
|
|
# / \
|
|
# / \
|
|
# 1------2------6
|
|
# /
|
|
# /
|
|
# 5
|
|
#
|
|
# Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example),
|
|
# each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.
|
|
#
|
|
# It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.
|
|
#
|
|
# Total Solution Set
|
|
# 9 4,2,3; 5,3,1; 6,1,2
|
|
# 9 4,3,2; 6,2,1; 5,1,3
|
|
# 10 2,3,5; 4,5,1; 6,1,3
|
|
# 10 2,5,3; 6,3,1; 4,1,5
|
|
# 11 1,4,6; 3,6,2; 5,2,4
|
|
# 11 1,6,4; 5,4,2; 3,2,6
|
|
# 12 1,5,6; 2,6,4; 3,4,5
|
|
# 12 1,6,5; 3,5,4; 2,4,6
|
|
#
|
|
# By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.
|
|
#
|
|
# Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string
|
|
# for a "magic" 5-gon ring?
|
|
#
|
|
# O
|
|
# \
|
|
# O
|
|
# / \ O
|
|
# / \ /
|
|
# O O
|
|
# / \ /
|
|
# O O--O---O
|
|
# \
|
|
# O
|
|
#
|
|
|
|
from itertools import permutations
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
# Function to evaluate the ring. The ring is represented as a vector of 2*n elements,
|
|
# the first n elements represent the external nodes of the ring, the next n elements
|
|
# represent the internal ring.
|
|
def eval_ring(ring, n):
|
|
for i in range(1, n):
|
|
# We need to start from the lowest external node, so if
|
|
# the first element in the vector is not the lowest of
|
|
# the first n elements (the external elements), the configuration
|
|
# is not a valid one.
|
|
if ring[i] < ring[0]:
|
|
return None
|
|
|
|
res = [0] * 3 * n
|
|
|
|
# Each group of three must have the same value.
|
|
magic_val = ring[0] + ring[n] + ring[n+1]
|
|
|
|
j = 0
|
|
|
|
for i in range(n):
|
|
# We need to find the maximum 16-digit string, this is possible only if the element "10" is used only once,
|
|
# i.e. if it's one of the external nodes.
|
|
if ring[n+i] == 10 or ring[n+(i+1) % n] == 10:
|
|
return None
|
|
|
|
# Check that the value of the current three-element group is the "magic" value.
|
|
val = ring[i] + ring[n+i] + ring[n+(i+1) % n]
|
|
|
|
if val != magic_val:
|
|
return None
|
|
|
|
# Save the current element group in the result string.
|
|
res[j] = ring[i]
|
|
res[j+1] = ring[n+i]
|
|
res[j+2] = ring[n+(i+1) % n]
|
|
|
|
j = j + 3
|
|
|
|
return res
|
|
|
|
|
|
def list_to_int(l):
|
|
if l is None:
|
|
return 0
|
|
|
|
res = 0
|
|
k = 0
|
|
|
|
for i in reversed(l):
|
|
res = res + i * 10 ** k
|
|
|
|
if i >= 10:
|
|
k = k + 2
|
|
else:
|
|
k = k + 1
|
|
|
|
return res
|
|
|
|
|
|
@timing
|
|
def p068():
|
|
# Generate all possible permutations, for each one check if it's a possible solution for the ring and save the maximum
|
|
rings = list(permutations(list(range(1, 11))))
|
|
max_ = 0
|
|
n = None
|
|
|
|
for ring in rings:
|
|
eval_ = eval_ring(ring, 5)
|
|
|
|
# Convert the list into an integer number.
|
|
n = list_to_int(eval_)
|
|
|
|
if n > max_:
|
|
max_ = n
|
|
|
|
print('Project Euler, Problem 68')
|
|
print(f'Answer: {max_}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p068()
|