GMGall’s blog

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

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

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: