[pyar] Ejercicio (para entretenerse)

[Alejandro J. Cura]

2012/1/13 fisa <fisadev en gmail.com>:
> El día 13 de enero de 2012 13:14, Lucio Torre <lucio.torre en gmail.com> escribió:
>> On Fri, Jan 13, 2012 at 11:44 AM, Sebastian Bassi
>> <sebastian.bassi en globant.com> wrote:
>>> De casualidad encontré una página que propone el siguiente problema, lo
>>> posteo porque se de varios que le gustan resolver estas cosas:
>>
>> Obviamente lo interesante aca es hacerlo en O(N), no O(N**2). Es
>> decir, no podes hacer una funcion que sea is_anagram(w1, w2) y hacer
>> todos contra todos.
>>
>> Lucio.
>
> Asumiendo que el .get de los diccionarios es O(1), esto sería O(N) con
> N = cantidad de palabras, no?
>
> palabras = 'abracadabra beards breads constant learner myopic
> relearn'.lower().split()
> abecedario = 'abcdefghijklmnopqrstuvwxyz'
>
> resultados = {}
>
> for p in palabras:
>    letras = {}
>    for l in p:
>        letras[l] = letras.get(l, 0) + 1
>
>    hash = ''.join(l + str(letras.get(l,0)) for l in abecedario)
>
>    resultados[hash] = resultados.get(hash, []) + [p,]
>
> # esto es para mostrar los resultados, no entra dentro del O del
> proceso para obtenerlos
> print '\n'.join(' '.join(r)
>                for r in resultados.values()
>                if len(r) > 1)
>
> --
> fisa  -  Juan Pedro Fisanotti

Mi versión es:
#------->8---------
# anagram.py
import sys
import collections

results = collections.defaultdict(list)

for line in sys.stdin:
    word = line.strip()
    key = "".join(sorted(word))
    results[key].append(word)

for words in results.values():
    if len(words) > 1:
        print " ".join(words)
#------->8---------

Cuando lo probé con "python anagram.py <
/etc/dictionaries-common/words", me di cuenta que no considera
Mayúsculas ni apóstrofes, pero me encantó que encontró estas líneas:

creationism romanticise
mantissa satanism

saludos,
-- 
alecu