[Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo

Aureliano Guedes guedes_1000 em hotmail.com
Domingo Abril 27 16:49:48 PDT 2014


Bruno,
Tratei a maioria dos erros e ainda ganhei em desempenho.O problema é que tem um bug que não consegui tratar.
Quando 89 <= time() <= 96 sempre retorna 131 e não 101, mas quando >89 ou <96 retorna corretamente 101.
http://pastebin.com/3QVnbjbP

Date: Sun, 27 Apr 2014 14:00:02 -0300
From: guedes_1000 em hotmail.com
To: rio-pm em pm.org
Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo








Buss,

Obrigado por analisar o código. 

Realmente eu fiz apenas alguns teste mas nao o suficiente para perceber esses bugs que me falou.

Essa heurística foi apenas experimental.

E ainda pode ser otimizada. 

Nao sou muito habilidoso quando se trata de achar esses tipos de erros.

Por exemplo, se na rotina de geração de palíndromo eu verificasse se o palíndromo gerado e par já ganharia no desempenho mas nao resolveria os problemas que citou.

Vou ver o que posso fazer para resolver esses bugs.

 Obrigado pela análise.





Bruno Buss <bruno.buss em gmail.com> escreveu:





Olá Aureliano,



Muito bom seu esforço... mas eu acho que você deveria elaborar e rodar alguns testes unitários para o seu código. :-)






Por exemplo, o seu código anterior (com as subs _par e _impar), imprimia "101" se o time() fosse "102". A resposta correta seria "131". A sua "heurística geradora de palindromos" andou para trás nesse caso... me parece um erro de design do algoritmo.






Essa sua nova versão:
* Imprime "13" se o time() for "13"... e 13 nem é palindromo! O resultado correto nesse caso é "101". Mas isso é só um erro no seu loop principal, que se for primo direto no começo ele nem verifica se é palindromo mas já imprime direto.



* Imprime "1003001" se o time() for 96... o que me parece meio longe do resultado esperado, "101". Nesse caso, emho, o problema é a sua "heurística geradora de palindromos".









Ou seja, a eficiência do algoritmo é muito importante... mas sua corretude deve vir antes. (A menos é claro que estejamos falando de algoritmos aproximativos ou heurísticas para problemas intratáveis :-)



Nesse caso em específico, parece que essa sua função geradora de palindromos é de fato uma heurística para dar bumps na sequência e economizar verificações... mas como observado você corre o risco de pular algo que não deveria.



Só como dúvida, essa sua heurística é fundamentada em algum resultado matemático de fato ou apenas experimental?






[ ]'s
Buss







2014-04-27 3:06 GMT-03:00 Aureliano Guedes 
<guedes_1000 em hotmail.com>:



Esquece a ultima versão.
Divisão é pesado para o processador. 



Fiz uma versão menor com menos divisões que parece ter uma melhor performance.



http://pastebin.com/jrjEv3eh







From: guedes_1000 em hotmail.com

To: rio-pm em pm.org

Date: Sun, 27 Apr 2014 02:44:57 +0000



Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo



Então tenho essa versão que executou em 1s.



http://pastebin.com/DLdPwAkp





From: blabos em gmail.com

Date: Sat, 26 Apr 2014 18:39:15 -0300

To: rio-pm em pm.org

Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo



Vamos dar um desconto por causa do "primo".




2014-04-25 23:26 GMT-03:00 Junior Moraes <juniiior182 em gmail.com>:


Hi.



Se for válido usar módulos externos, dá pra implementar com o Math::Prime::XS para ficar mais performático. :-)



[]'s





Em 25 de abril de 2014 23:21, Aureliano Guedes <guedes_1000 em hotmail.com> escreveu:





Não fiz em poucas linhas, mas fis em poucos segundos: http://pastebin.com/DLdPwAkp





Date: Tue, 22 Apr 2014 15:09:22 -0300



From: guedes_1000 em hotmail.com

To: rio-pm em pm.org

Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo



Claro que esta. Mas nao consegui fazer o que o que o Bablos sugeriu em uma única linha.



Vinícius Miasato <viniciusmiasato em gmail.com> escreveu:







Opa,




parabéns por aceitar o desafio e levá-lo até o fim! Não sei se o código funciona, mas o jogo de GOLF ainda está de pé?




atenciosamente,

Vinícius Miasato






Em 22 de abril de 2014 13:13, Aureliano Guedes <guedes_1000 em hotmail.com> escreveu:



http://ideone.com/LjvMRz



4:30 rodando no dinossauro (AMD Athlon 1.6GHz, 2GB Ram)





Date: Thu, 17 Apr 2014 22:25:48 -0300

From: guedes_1000 em hotmail.com

To: rio-pm em pm.org

Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo





Boa ideia. Vou tentar.



Blabos de Blebe <blabos em gmail.com> escreveu:





Que tal o menor palíndromo primo maior que time()?




2014-04-17 22:02 GMT-03:00 Aureliano Guedes <guedes_1000 em hotmail.com>:



Pode ficar menor.

say '906609'



Tiago Peczenyj <tiago.peczenyj em gmail.com> escreveu:







sub palindromo { 906609 }




2014-04-17 21:45 GMT-03:00 Aureliano Guedes <guedes_1000 em hotmail.com>:



Ola monges,



Nos últimos meses tenho visto nosso grupo um pouco parado.
E como estamos em véspera de pascoa.
Proponho uma brincadeira.
Jogar golf com o Desafio do Maior Palíndromo.



O desafio é simples, achar o maior número palíndromo (ou seja, quando lido de trás pra frente continua o mesmo) que seja resultado de uma multiplicação de dois números de 3 dígitos.



O resultado deverá ser: 906609



Eis a minha tacada:



for(my$i=100;$i<1000;$i++){for(100..999){$_[0]=$_*$i if(($_*$i==reverse($_*$i))&&($_*$i>=$_[0]))}}say$_[0]




_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm









-- 

Tiago B. Peczenyj

Linux User #405772



http://about.me/peczenyj 






_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm









_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm

_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm







_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm









_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm

_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm






_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm










_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm








_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm




_______________________________________________ Rio-pm mailing list 
Rio-pm em pm.org 
http://mail.pm.org/mailman/listinfo/rio-pm







_______________________________________________

Rio-pm mailing list

Rio-pm em pm.org

http://mail.pm.org/mailman/listinfo/rio-pm









-- 

Bruno C. Buss

http://www.brunobuss.net 





_______________________________________________
Rio-pm mailing list
Rio-pm em pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm em pm.org
http://mail.pm.org/mailman/listinfo/rio-pm 		 	   		  
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/rio-pm/attachments/20140427/c046dfa6/attachment.html>


Mais detalhes sobre a lista de discussão Rio-pm