Metathesis
Descripción
“Metathesis” es la transposición de letras en una palabra. Dos palabras forman un par de metathesis si puedes transformar una en la otra cambiando un par de letras, por ejemplo “converse” y “conserve”. Escribe un programa que encuentre todos los pares de metathesis en la lista de palabras del archivo words.txt.
Consejos::
- Las palabras de un par de metathesis deben ser anagrama de la otra.
- Tal vez necesites revisar los ejercicios Todos los Anagramas y Distancia Entre Palabras
Créditos: Este ejercicio está inspirado por un ejemplo de http://puzzlers.org.
Ejemplo de Ejecución:
>>> python metathesis.py
('aah', 'aha')
('aal', 'ala')
('aals', 'alas')
('aba', 'baa')
('abas', 'baas')
('abbe', 'babe')
('abbes', 'babes')
('bate', 'beta')
('beat', 'beta')
('bates', 'betas')
('bates', 'tabes')
('beast', 'beats')
('beats', 'betas')
('abide', 'abied')
(...)
Solución
Mostrar solución
def get_word_list():
with open('/content/drive/MyDrive/words.txt') as f:
word_list = f.read().splitlines()
return word_list
def get_anagrams_dict(word_list):
anagrams = {}
for word in word_list:
key = ''.join(sorted(word))
if key in anagrams:
anagrams[key].append(word)
else:
anagrams[key] = [word]
return anagrams
def word_distance(word1, word2):
if len(word1) != len(word2):
return None
distance = 0
for c1, c2 in zip(word1, word2):
if c1 != c2:
distance += 1
return distance
def get_metathesis_pairs(anagrams):
pairs = []
for key, words in anagrams.items():
if len(words) > 1:
for i in range(len(words)):
for j in range(i+1, len(words)):
if word_distance(words[i], words[j]) == 2:
pairs.append((words[i], words[j]))
return pairs
word_list = get_word_list()
anagrams = get_anagrams_dict(word_list)
metathesis_pairs = get_metathesis_pairs(anagrams)
for p in metathesis_pairs:
print(p)
Fuente del ejercicio: https://allendowney.github.io/ThinkPython/chap11.html#id5