GMGall’s blog

Programação, Linux e o que mais der na telha

Arquivos Mensais: março 2009

Sequência look and say em Python

Tenho brincado ultimamente com os desafios do Python Challenge. São bem interessantes para quem quer aprender Python na prática. Estou resolvendo o nível 11 e já precisei processar imagens, descompactar dados comprimidos com zip e bz2, serializar objetos, acessar recursos via URL, usar expressões regulares e algumas tarefas que não exigiam necessariamente um módulo.

O último nível que resolvi tinha como resposta o comprimento de um elemento específico de uma sequência de inteiros conhecida como look and say (olhe e descreva). Achei diversas implementações da geração da sequência pela web, nenhuma delas me pareceu pythonica ou legível o suficiente. Resolvi juntar algumas das idéias que vi nessas implementações com os conhecimentos que obtive recentemente com a leitura de um material sobre programação funcional em Python e criei uma função que retorna uma lista com os elementos da sequência. A minha solução não é a mais eficiente possível (essa página contém uma implementação alegadamente otimizada para velocidade), mas acho que é elegante e mostra alguns aspectos interessantes da linguagem. Segue o código:

def look_and_say(first, elements):
    from itertools import groupby
    seq = [str(first)]

    def say(number):
        ret = []
        for k,g in groupby(number):
            ret.append( str(len(list(g))) + k )
        return ''.join(ret)

    for i in xrange(elements):
        seq.append(say(seq[-1]))
    return seq

O argumento first de look_and_say recebe o primeiro elemento da lista e elements quantos elementos depois do primeiro devem ser gerados. Exemplo de uso:

>>> look_and_say(1,10)
['1', '11', '21', '1211', '111221', '312211', '13112221', '1113213211', '31131211131221', '13211311123113112211', '11131221133112132113212221']
>>> look_and_say(55,4)
['55', '25', '1215', '11121115', '31123115']

Dentre os aspectos que gostaria de destacar estão a possibilidade de importar partes de módulos e definir funções dentro de funções, o uso de listas para concatenar strings com eficiência e o uso de itertools.groupby que faz um agrupamento semelhante ao do comando uniq do Unix, juntando elementos iguais consecutivos em um iterator.

Para quem quiser uma abordagem matemática da sequência, o Wolfram Mathworld tem uma página sobre ela.

Anúncios