def is_anagram(first, second):
return sorted(str(first)) == sorted(str(second))
is_anagram(1264, 1543)
False
is_anagram(1264, 1642)
True
cubes = {}
cube_lens = {}
n = 1
cube = 1
while len(str(cube)) < 15:
cubes[n] = cube
cube_lens[n] = len(str(cube))
n += 1
cube = n ** 3
max(cubes.keys())
46415
candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 8]
anagrams = {}
for c in candidates:
for o in candidates:
if is_anagram(c, o):
if c not in anagrams:
anagrams[c] = [o]
else:
anagrams[c].append(o)
[anagrams[c] for c in anagrams.keys() if len(anagrams[c]) >= 3]
[[41063625, 56623104, 66430125], [41063625, 56623104, 66430125], [41063625, 56623104, 66430125]]
c
64481201
candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 12]
sorted_candidates = ["".join(sorted(str(c))) for c in candidates]
from collections import Counter
c = Counter(sorted_candidates)
c.most_common(5)
[('012334566789', 5), ('012334556789', 5), ('122334566788', 4), ('011245567789', 4), ('011223346789', 4)]
for c in candidates:
if is_anagram(c, 102334556789):
print(c)
break
127035954683
C'est beaucoup plus efficace comme ça !
La raison ? On a plus besoin de faire toutes les comparaisons dans les anagrammes. Sachant que si $n$ est le nombre de candidates, on a $n^2$ comparaisons d'anagrammes à faire, ce qui est beaucoup.
Dans cette méthode, il suffit de compter le nombre d'occurences d'une permutation et on prend le plus grand nombre d'occurences.
candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 14]
len_dict = {}
for c in candidates:
key = "".join(sorted(str(c)))
if key not in len_dict:
len_dict[key] = [c]
else:
len_dict[key].append(c)
s = sorted(list(len_dict.iteritems()), key=lambda s: len(s[1]), reverse=True)
max_len = len(s[0][1])
for i in range(5):
print "{0} combinations, smallest cube: {1}".format(len(s[i][1]), s[i][1][0])
9 combinations, smallest cube: 13465983902671 8 combinations, smallest cube: 10314675896832 8 combinations, smallest cube: 10340284735656 8 combinations, smallest cube: 15302864497283 8 combinations, smallest cube: 12620043581768
Au lieu de calculer des permutations, il est plus simples de juste prendre une seule représentation du nombre sous forme de chiffres triés qu'on utilise comme clé dans un dictionnaire. C'est cool ça !