Números Reversíveis

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Números Reversíveis

Mensagempor Bruno Oliveira em Quinta Jun 03, 2010 8:46 pm

Este problema é um dos do project euler, que estou a utilizar para me treinar na programação funcional;

Sei que o código, pode não estar pitónico, e pode até ter alguns erros... Mas já pensei bastante sobre ele, e como não estou a conseguir chegar a uma solução, decidi postar aqui o meu código a ver se ele pode ser (e pode de certeza) melhorado para dar a resposta em tempo útil e usando o mínimo de memória possível também (presumo que seja aqui que entra o funcional).

Aqui vai então:

O enunciado do problema é o seguinte:

Código: Seleccionar Todos
"""
Project Euler Problem 145:

Some positive integers n have the property that the sum [ n + reverse(n) ]
consists entirely of odd (decimal) digits.
For instance, 36 + 63 = 99 and 409 + 904 = 1313.
We will call such numbers reversible; so 36, 63, 409, and 904 are reversible.
Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^(9))?
"""


Está no topo do meu código como uma doc string...

Vou dividir este post em passos, tal como fiz com o código:

1º Passo: Escrever uma função ou funções que me dêem o reverso de um número:

Para este passo, utilizei duas funções:

A primeira função, chamada reverse_as_list, recebe como input um número, converte-o em string e adiciona cada dígito desse mesmo número à lista L.
De seguida, pego nesses elementos e adiciono-os pela ordem inversa, a uma nova lista a que decidi chamar T;

A função está então com este aspecto:

Código: Seleccionar Todos
def reverse_as_list(number):
        L = []
        T = []
        for s in range(0,len(str(number))):
                L.append(str(number)[s:s+1])
        j = len(L)-1
        while j >= 0:
                v = L[j]
                T.append(v)
                j -= 1
        return T


De seguida, escrevi uma outra função, chamada reverse que me dá o reverso do número propriamente dito, usando a função anteriormente definida:

Código: Seleccionar Todos
def reverse(n):
        return int(join(reverse_as_list(n),''))


2º passo: Escrever uma função para testar a condição de reversibilidade de um número (a soma de n com reverse(n) ser apenas formada por dígitos ímpares)

Aqui, usei os idiomas mais comuns para mim, os tradicionais contadores e ciclos for; o que faço é inicializar uma variável, chamada c com o valor 0 que será o meu contador.

Depois uso um ciclo for para percorrer a string toda, testando a divisibilidade de cada elemento da string por 2, com um if, e actualizando o valor do contador sempre que um dígito "passa" na condição de divisibilidade, chamei string_reversibility à função;

Código: Seleccionar Todos
def string_reversibility(s):
        c = 0
        for a in range(0, len(str(s))):
                if int(str(s)[a:a+1]) % 2 != 0:
                       c += 1
        if c == len(str(s)):
                return True
        else:
                return False


3º passo: Escrever a função reversible propriamente dita, que me diz finalmente, se um número é ou não reversível

Esta função, foi fácil de escrever para mim, dado que, creio eu, fui bastante metódico na escrita das outras funções...

Para esta, só precisei de criar uma variável de nome, res, cujo valor é igual ao da soma de n com reverse(n).
De seguida, apliquei a função string_reversibility ao valor de res, retornando esta função True, caso res seja reversível e False caso contrário;

Código: Seleccionar Todos
def reversible(t):
        res = t + reverse(t)
        if string_reversibility(res) == True:
                return True
        else:
                return False


A partir daqui, tinha apenas de fazer um loop ou usar listas por compreensão ou algo do género para obter a resposta... O pior é que o pedaço de código:

Código: Seleccionar Todos
R = filter(reversible, xrange(1 ,10**9))
print len(R)


dá-me logo MemoryError como é de esperar ao testar tantos valores...

Tendo sido eu tão metódico a questão é, o que é que estou a fazer mal, ou que "salto mental" é que preciso de dar para obter o valor correcto? Penso que a resposta esteja na programação funcional que quero mesmo começar a dominar, mas uma ajuda era de extrema utilidade claro;

Peço desde já desculpa por meter aqui mais um problema do PE, mas só o faço quando preciso mesmo de ajuda,

Bruno
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Números Reversíveis

Mensagempor jap em Sexta Jun 04, 2010 12:55 pm

Bruno,

O teu código é um bom ponto de partida, mas nota-se mesmo que andaste a aprender C! :lol:

Aqui vai uma versão pitónica, usando programação funcional (e que testa o problema para o caso em que N =1000). Não está optimizado em velocidade, pelo que demorará bastante tempo a dar a resposta para N = 10**9, mas não irá estourar por falta de memória. :lol:

De qualquer forma, deixo o desafio da optimização para os quarkianos! :mock:

Código: Seleccionar Todos
from itertools import imap
from operator import add,iand

odd = lambda i:  int(i) % 2

def reversible(n):
    s = list(str(n)) 

    if s[-1]=='0': return False
                 
    s.reverse()

    n = int(reduce(add,s)) + n
   
    return reduce(iand,map(odd,str(n)))
           

if __name__ == "__main__":

    print sum(imap(reversible, xrange(10**3)))
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Sexta Jun 04, 2010 5:30 pm

Boa tarde para todos os quarkianos :)

Prof, desde já obrigado pelo tempo que perdeu a ler o meu código...

Após fazer uns testes entre a minha versão e a versão que o prof. aqui disponibilizou, apercebi-me que faltava considerar-me o caso em que reverse(n) começaria com um 0... Estava a obter 125 números reversiveis abaixo de 1000, agora já obtenho os 120 que é o resultado que está explicitado no enunciado do problema...

O pior deste estilo de programação que uso, é mesmo o facto de não estar a conseguir lidar bem com grandes quantidades de dados... Sei que estará relacionado com o memória que tenho disponível neste PC, e também estou consciente que utilizar um estilo de programação funcional pode ajudar a reduzir ( e muito!!) o uso da memória... Apenas vou ter de me habituar creio...

Por outro lado, creio que o prof, interpretou o enunciado "ao contrário" já que um número é dito reversivel se a soma dele mesmo com o seu reverso for apenas formada por digitos ímpares e não pares... Assim, creio que a linha ou as linhas:

Código: Seleccionar Todos
n = int(reduce(add,s)) + n
   
    return reduce(iand,map(even,str(n)))


terão de ser modificadas...

Por outro lado, descobri também (ao pensar no problema durante a noite) que não precisamos de fazer 10**9 testes...Já que se n é reversivel, então reverse(n) também o será, certo? :roll:

Já deve ser mais facil lidar com a enormidade de dados se a reduzirmos, verificando primeiramente se reverse(n) está na lista, se estiver podemos removê-los a todos e tendo também em conta que os números que acabam em 0 são automaticamente não reversiveis e podem ser excluidos, o número 10**9 deve reduzir-se significativamente...

Vou correr mais uns testes e mais logo direi alguma coisa.

Bruno
última vez editado por Bruno Oliveira s Sexta Jun 04, 2010 5:40 pm, editado 1 vez no total
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Números Reversíveis

Mensagempor jap em Sexta Jun 04, 2010 5:40 pm

Já corrigi, mudando o even para odd. Tinha, de facto, treslido o enunciado. :oops:

Já agora, aqui fica o desafio adicional: um programa que faça a tarefa, numa só linha de programação funcional pura! :wink:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Sexta Jun 04, 2010 6:27 pm

Hum.. uma só linha de programação funcional acho que me esgotava a capacidade de pensar...pelo menos agora gastará de certeza.. :?

Mas, se o prof. quiser ir dando umas dicas, ou postar uma resolução explicada do desafio, teria todo o gosto em resolvê-lo para aprender mais um pouco de programação funcional.

Sempre disseram que mudar de paradigma de programação era díficl... :evil: Agora entendo porquê...
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Números Reversíveis

Mensagempor jap em Sexta Jun 04, 2010 8:53 pm

Aqui vai um one-liner:


Código: Seleccionar Todos
from itertools import imap
from operator import add,and_

if __name__ == "__main__":

    print sum(imap(lambda n: str(n)[-1]!='0'and reduce(and_,map(lambda i: int(i) % 2 , \
                   str(int(str(n)[::-1]) + n))), xrange(10**3)))



Tecnicamente, as instruções de import e o if não contam! :lol: Não é particularmente rápido mas não irá estourar por falta de memória para números grandes...

Pretty ugly, huh! :mock:

Mais tarde postarei a explicação detalhada de como funciona este brainteaser. :wink:

Parece bem mais complicado do que é na realidade! 8)
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor hexphreak em Sábado Jun 05, 2010 12:43 pm

Project Euler Escreveu:I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Claramente, Python é a linguagem errada para o Project Euler :P Experimentem um dos descendentes da APL, como J ou K, que são linguagens extremamente rápidas (e sucintas, ou não descendessem de APL) construídas propositadamente para manipulação matemática de grandes volumes de dados e com grande precisão.
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Números Reversíveis

Mensagempor jap em Sábado Jun 05, 2010 12:55 pm

hexphreak Escreveu:
Project Euler Escreveu:I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Claramente, Python é a linguagem errada para o Project Euler :P Experimentem um dos descendentes da APL, como J ou K, que são linguagens extremamente rápidas (e sucintas, ou não descendessem de APL) construídas propositadamente para manipulação matemática de grandes volumes de dados e com grande precisão.


Usar Python, J, K or whatever linguagem de programação não tem grande importância para o one-minute rule! :lol:

Na realidade se o programa acima é lento não é culpa do Python, mas sim do algoritmo. Programar o mesmo algoritmo em J ou em C não iria adiantar nada. :mock:

Aliás é por isso que o Python até é uma boa linguagem para o projecto Euler porque te permite testar diferentes algoritmos minimizando o tempo que gastas a escrever os programas - isso é mais importante do que minimizar o tempo de execução, quando estás à procura do melhor algoritmo.

Já agora um bom algoritmo para resolver este problema é ...? :roll:

Estou à espera das vossas contribuições. :XD
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Tharis em Sábado Jun 05, 2010 4:14 pm

Deixo aqui o meu one-liner.

Código: Seleccionar Todos
print len([i for i in xrange(1,10**3) \
   if not len( filter(lambda x: not(ord(x)%2), str(int(str(i)[::-1]) + i)) ) and str(i)[-1] != '0'])
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Sábado Jun 05, 2010 4:41 pm

jap Escreveu:
hexphreak Escreveu:
Project Euler Escreveu:I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Claramente, Python é a linguagem errada para o Project Euler :P Experimentem um dos descendentes da APL, como J ou K, que são linguagens extremamente rápidas (e sucintas, ou não descendessem de APL) construídas propositadamente para manipulação matemática de grandes volumes de dados e com grande precisão.


Usar Python, J, K or whatever linguagem de programação não tem grande importância para o one-minute rule! :lol:

Na realidade se o programa acima é lento não é culpa do Python, mas sim do algoritmo. Programar o mesmo algoritmo em J ou em C não iria adiantar nada. :mock:

Aliás é por isso que o Python até é uma boa linguagem para o projecto Euler porque te permite testar diferentes algoritmos minimizando o tempo que gastas a escrever os programas - isso é mais importante do que minimizar o tempo de execução, quando estás à procura do melhor algoritmo.

Já agora um bom algoritmo para resolver este problema é ...? :roll:

Estou à espera das vossas contribuições. :XD


Como tinha dito ontem, em qualquer problema do ProjectEuler, há sempre uma maneira matemática de reduzir (e bastante!!) o número de casos a testar.

Para este caso particular, do universo que queremos testar (os números todos até 10**9 ,exclusive) podemos reduzir em muito este número já que:

Os numeros cujo ultimo digito é 0 não contam para os casos de teste, pois não têm reverso;

Se um número for reversivel, como é o caso do 36, sabemos automaticamente que o seu reverso também é reversivel e não precisamos de o incluir na nossa contagem...basta adicionarmos 2 a um suposto contador que tenhamos implementado previamente...
Não sei se podem ajudar estas duas observações..mas penso que sim!!

Independentemente disso, o limite de 1 bilião imposto pelo problema, come-me a memória do PC quase instantaneamente... Tentei ainda ontem aplicar um filter à lista de 10**9 números para remover todos os números acabados em 0 e deu logo memoryError... É isto que me falta adquirir/treinar para programar melhor...Saber optimizar algoritmos para lidarem com grandes quantidades de dados, usando a memória que tenho à disposição... Pode ser que aprenda bastante a este respeito com este problema! :D
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Números Reversíveis

Mensagempor hexphreak em Sábado Jun 05, 2010 5:58 pm

jap Escreveu:Na realidade se o programa acima é lento não é culpa do Python, mas sim do algoritmo. Programar o mesmo algoritmo em J ou em C não iria adiantar nada. :mock:

Não necessariamente. Acredito que neste caso a culpa seja do algoritmo, mas o Python tem uma forma enervante de conseguir ser lento mesmo com algoritmos eficientes :P Aliás, o próprio Guido van Rossum disse que um dos objectivos do Python é ter o interpretador mais estúpido possível que ainda funcione. Como o Francisco provou na GRID, C consegue ser três ou mais ordens de magnitude mais eficiente que Python, com o mesmo algoritmo...
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Números Reversíveis

Mensagempor Tharis em Sábado Jun 05, 2010 6:53 pm

O Python é de facto, sem qualquer disputa (nem da minha parte :P) uma linguagem lenta em execução. No entanto, não deixa de ser uma excelente linguagem que compensa essa lentidão na execução com uma rapidez na escrita do código.

Depois, qualquer algoritmo eficiente correr em Python em pouco mais tempo que em C não é bem verdade. Já fiz testes e certos algoritmos em C demoram menos que 1 segundo e em Python nem chegou a acabar. Um dos mais divertidos que fiz foi um interpretador de Brainfuck em C e outro em Python com os mesmos algoritmos. Ambos deram como tempos 27. Só que um era minutos e o outro segundos.

hexphreak Escreveu:Como o Francisco provou na GRID, C consegue ser três ou mais ordens de magnitude mais eficiente que Python, com o mesmo algoritmo...


Por acaso não é bem assim. O algoritmo implementado em Python era O(N^3), era um one-liner. E o de C era O(N sqrt N), no entanto continua a ter uma grande disparidade de tempos para a diferença de complexidades.


Deixando agora de parte Python vs C vs Whatever, vamos mas é ao problema.

@BrunoOliveira, podes filtrar os múltiplos de 10, certo. Se n é reversível, então reverse(n) também o é, certo. O primeiro corte podes fazê-lo bem. O segundo duvido que te vá ajudar, uma vez que para "cortares" o outro terias de fazer uma pesquisa na lista e no mínimo seria log N que numa linguagem ideal não deve compensar.

Normalmente a melhor "técnica" neste tipo de problemas é gerar em vez de filtrar. Posto isto, depois vejo se penso em algo. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números Reversíveis

Mensagempor jap em Domingo Jun 06, 2010 4:48 pm

Gostei do one-liner do Francisco! :hands:

By the way a resposta ao problema é 608720! :lol:

E sim, para não ultrapassarem o minuto de tempo de execução têm mesmo de alterar o algoritmo. Bem, em C ou assembly o algoritmo estúpido talvez corra num minuto, mas não vou codificá-lo em assembly ou no "assemblador mais próximo de uma linguagem de alto nível que conseguimos conceber" (K & R dixit) :lol:

PS: WTF brainfuck program takes 27 mins to run under Python? :XD
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Domingo Jun 06, 2010 5:35 pm

Bom, além das modificações acima, não vejo outras modificações (pelo menos á primeira vista) possíveis... Se tiver de ser usada alguma estrutura de armazenamento de dados nova para mim, como os sets (vi lá várias soluções com sets, todas a demorarem 2h+ segundo os coders, pelo que não deve sequer ser por aí...) ou algo do género, prefiro ver a resolução e aprender algo com ela :P

A ver se começo a aprender técnicas para melhorar estes meus algoritmos extremamente lentos... :(
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Números Reversíveis

Mensagempor Tharis em Domingo Jun 06, 2010 11:38 pm

Bruno, IMO o Project Euler é dos piores "sistemas"/"métodos"/"whatever" para melhorar skills algorítmicas. Ele está destinado a aplicar essas skills, não a desenvolvê-las. Para aprender e desenvolveres skills algorítmicas, existem 2 sítios: USACO e SPOJ. USACO para aprendizagem progressiva, tipo escola. SPOJ para treino específico aka treinares um assunto qualquer, como pesquisas ou programação dinâmica.
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Próximo

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 3 visitantes

cron