Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
246 lines (232 sloc) 19.5 KB
# Solution to Project Euler problem 98
# Copyright (c) Project Nayuki. All rights reserved.
import eulerlib
def compute():
anagrams = {}
for word in WORDS:
key = "".join(sorted(word))
if key not in anagrams:
anagrams[key] = []
ans = 0
for (key, words) in anagrams.items():
for i in range(len(words)):
for j in range(i + 1, len(words)):
assignments = {}
ans = max(max_square_pair(words[i], words[j], 0, assignments, [False] * 10), ans)
return str(ans)
# Strings a and b must be anagrams of each other.
def max_square_pair(a, b, index, assignments, isdigitused):
if index == len(a):
if a[0] in assignments and assignments[a[0]] == 0 or \
b[0] in assignments and assignments[b[0]] == 0:
return 0
anum = 0
bnum = 0
for (x, y) in zip(a, b):
anum = anum * 10 + assignments[x]
bnum = bnum * 10 + assignments[y]
if eulerlib.is_square(anum) and eulerlib.is_square(bnum):
return max(anum, bnum)
return 0
elif a[index] in assignments:
return max_square_pair(a, b, index + 1, assignments, isdigitused)
result = 0
for i in range(10):
if not isdigitused[i]:
isdigitused[i] = True
assignments[a[index]] = i
result = max(max_square_pair(a, b, index + 1, assignments, isdigitused), result)
del assignments[a[index]]
isdigitused[i] = False
return result
WORDS = ( # 10 strings per line, except final line
if __name__ == "__main__":