Encontrar Anagramas con Python
Encontrar anagramas con Python
Hay ejercicios que aparecen una y otra vez a la hora de hacer entrevistas de trabajo. Y el ejercicio de encontrar los anagramas es uno de esos.
Un anagrama es una palabra que se lee de adelante para atrás y atrás para adelante con sentido. O que mezclando sus letras encontramos nuevas palabras. Ejemplos:
| Alegan – Ángela | Riesgo – Sergio |
|---|---|
| Desamparador – desparramado | Licúa – Lucía |
| Conservadora – conversadora | Amor – Roma |
Más formalmente, un anagrama es una palabra o frase que resulta de la transposición de letras de otra palabra o frase (Anagrama según wikipedia). Esto es dos palabras que usan las mismas letras pero en distinto orden.
Y dió la casualidad que vi en un tweet la siguiente imágen que decia que utilizando el teorema fundamental de la aritmética se podía saber si dos palabras eran anagramas (@fermatslibrary).
Así que lo intenté hacer. Y lo primero que hay que hacer es conseguir 26 números primos (veasé mi post anterior obtener-numeros-primos-con-python) así podemos vincular cada letra ascii con un numero primo.
Así que repitiendo un poco el código de otro post:
import math
import string
def primeSieve(sieveSize):
# Returns a list of prime numbers calculated using
# the Sieve of Eratosthenes algorithm.
sieve = [True] * sieveSize
sieve[0] = False # zero and one are not prime numbers
sieve[1] = False
# create the sieve
for i in range(2, int(math.sqrt(sieveSize)) + 1):
pointer = i * 2
while pointer < sieveSize:
sieve[pointer] = False
pointer += i
# compile the list of primes
primes = []
for i in range(sieveSize):
if sieve[i] is True:
primes.append(i)
return primes
all_ascii = string.ascii_lowercase
primes = primeSieve(102)
ascii_primes = dict(zip(all_ascii, primes))
Al final podemos ver como usamos la libreria built-in de python string (python.org - string) para obtener todos los caracteres "abcdefghijklmnopqrstuvwxyz". Después con los números primos y las letras armamos un dict con zip(). Para qué, para que me quede un dictionary de la siguiente forma:
{
'o': 47,
'y': 97,
'n': 43,
'r': 61,
'i': 23,
'g': 17,
'j': 29,
'q': 59,
'v': 79,
'b': 3,
'a': 2,
's': 67,
'm': 41,
'e': 11,
'l': 37,
'u': 73,
't': 71,
'z': 101,
'c': 5,
'p': 53,
'f': 13,
'd': 7,
'k': 31,
'x': 89,
'w': 83,
'h': 19
}
Está desordenado, pero un dictionary, como los json, no están necesariamente ordenados. Acá cada letra tiene asignado un numero. Luego la función que calcula el numero para cada palabra:
def calculate_word(word):
"""
Multiply the caracters of each word. Since every integer is a prime.
Two words are anagram if their product is the same.
"""
first = True
total = 0
for letter in word:
number = d[letter]
if first:
first = False
total = number
else:
total *= number
return total
Esto es relativamente sencillo. Recorremos cada letra de la palabra y, por cada una de esas letras, buscamos su correspondiente numero primo en el diccionario y primero guardamos el numero y en la siguiente iteración multiplicamos con el siguiente numero primo/letra.