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

Bruno Buss bruno.buss em gmail.com
Sábado Maio 3 06:01:11 PDT 2014


Então, eu não consigo instalar seu modulo no meu sistema, mas supondo que
ele esteja correto, principalmente que a função "next_palindrome" retorne
exatamente o próximo palindromo maior ou igual ao número...

Para esse seu programa:
(1) Entrada: 9. Saída esperada: 9. Saída atual: 11.

(2) Entrada: 191. Saída esperada: 191. Saída atual: Alguma coisa que não é
191 e fiquei com preguiça de terminar o chinês.

(3) Entrada: 666. Saída esperada: 727. Saída atual: Alguma coisa que não é
727 e fiquei com preguiça de terminar o chinês. Mas logo depois da 1a
iteração do while... o $time foi bumpado para 796 - por causa do
if((reverse $time) % 2 == 0) - e já passou do 727 e nunca vai voltar para
ele....



japa++ pela consideração entre as duas versões do reverse reverse $time. Eu
ainda acho que esse trecho ta errado destrói qualquer tentativa de
construir uma invariante no algoritmo.


2014-05-01 22:27 GMT-03:00 Aureliano Guedes <guedes_1000 em hotmail.com>:

> E pronto minha solução sem os bugs que falou: http://pastebin.com/PQQyg5BK
>
> Engraçado: teve o melhor desempenho.
> Um simples detalhe reduziu o tempo de execução pela metade.
>
> Fazer:
> $time = reverse $time;
> $time++;
>  $time = reverse $time;
>
> gera um desempenho melhor que fazer:
>
> $time = reverse (reverse $time++);
> ------------------------------
> From: guedes_1000 em hotmail.com
> To: rio-pm em pm.org
> Date: Fri, 2 May 2014 00:04:04 +0000
>
> Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
>
> Bruno, resolvi o problema e segui a sua dica:
> http://cpansearch.perl.org/src/ACPGUEDES/Math-Palindrome-undef/lib/Math/Palindrome.pm
>
> O
> http://search.cpan.org/~kryde/Math-NumSeq-70/lib/Math/NumSeq/Palindromes.pm era
> muito incompleto!
>
> ------------------------------
> From: bruno.buss em gmail.com
> Date: Mon, 28 Apr 2014 21:24:50 -0300
> To: rio-pm em pm.org
> Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
>
> O problema é que quando time() está entre 89 e 96, next_prime($time)
> retorna 97... e a palindrome(97) retorna 107 - se não errei o chines mental
> que acabei de fazer - ou seja, pulando um palíndromo primo, que seria a
> resposta correta. O mesmo problema de antes, sua heurística para tentar
> pular números na sequencia de primos/palíndromos ainda não está muito boa.
>
> Mais uma dica: Ao invés de usar aquela formula toda para pegar a 1a/2a
> metade dos dígitos do numero, porque você não usa a substr()? :-)
>
>
> 2014-04-27 20:49 GMT-03:00 Aureliano Guedes <guedes_1000 em hotmail.com>:
>
> 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
>
> _______________________________________________
> 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
>
> _______________________________________________
> Rio-pm mailing list
> Rio-pm em pm.org
> http://mail.pm.org/mailman/listinfo/rio-pm
>



-- 
Bruno C. Buss
http://www.brunobuss.net
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/rio-pm/attachments/20140503/1060d073/attachment-0001.html>


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