77 lines
2.0 KiB
Python
77 lines
2.0 KiB
Python
from lib_misc import permutations
|
|
|
|
|
|
def all_equal(xs):
|
|
x_1 = xs[0]
|
|
for x in xs[1:]:
|
|
if x_1 != x:
|
|
return False
|
|
return True
|
|
|
|
|
|
def is_3_gon_ring(r):
|
|
if not (r[2] > r[0] and r[1] > r[0]):
|
|
return False
|
|
line_034 = r[0] + r[3] + r[4]
|
|
line_154 = r[1] + r[5] + r[4]
|
|
line_253 = r[2] + r[5] + r[3]
|
|
return all_equal([line_034, line_154, line_253])
|
|
|
|
|
|
def is_5_gon_ring(r):
|
|
if not (r[1] > r[0] and r[2] > r[0] and
|
|
r[3] > r[0] and r[4] > r[0]):
|
|
return False
|
|
l_056 = r[0] + r[5] + r[6]
|
|
l_167 = r[1] + r[6] + r[7]
|
|
l_278 = r[2] + r[7] + r[8]
|
|
l_389 = r[3] + r[8] + r[9]
|
|
l_495 = r[4] + r[9] + r[5]
|
|
return all_equal([l_056, l_167, l_278, l_389, l_495])
|
|
|
|
|
|
def five_gon_ring_to_group_presentation(r):
|
|
xs = [r[0], r[5], r[6],
|
|
r[1], r[6], r[7],
|
|
r[2], r[7], r[8],
|
|
r[3], r[8], r[9],
|
|
r[4], r[9], r[5]]
|
|
xs = "".join(map(str, xs))
|
|
return xs
|
|
|
|
|
|
def euler_068():
|
|
"""
|
|
This one was really fun. The hardest part was to get the
|
|
check for the representation right. This is how my five
|
|
gon ring is indexed:
|
|
|
|
# 0 1 #
|
|
# 5 #
|
|
# 9 6 #
|
|
# 4 #
|
|
# 8 7 2 #
|
|
# #
|
|
# 3 #
|
|
|
|
There is probably and automatic indexing scheme that would
|
|
make the check and presentation function easier to write, but not
|
|
necessarily easier to read. Also generating all permutations creates
|
|
a lot of over head. For example, the lowest number cannot be higher
|
|
than six so that removes about 40% of the permutations right away and
|
|
there are probably more heuristics.
|
|
"""
|
|
rs = []
|
|
for p in permutations(list(range(1, 11))):
|
|
if is_5_gon_ring(p):
|
|
r = five_gon_ring_to_group_presentation(p)
|
|
if len(r) == 16:
|
|
# print(r)
|
|
rs.append(int(r))
|
|
return max(rs)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e068.py: " + str(euler_068()))
|
|
assert(euler_068() == 6531031914842725)
|