Acabei de subir para o CPAN a versão 0.02 daquele
módulo.https://metacpan.org/pod/Math::Palindrome
Mas agora que acabei de ver seu e-mail.
Algumas modificações já irei fazer para subir a versão 0.03.
Se você tentar instalar depois me fala se deu certo?
From: bruno.b...@gmail.com
Date: Sat, 3 May 2014 18:57:58 -0300
To: rio-pm@pm.org
Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
Sobre o lance do next_palindrome antes do loop:
Mas com isso você quebrou o caso onde o valor inicial já é um palindromo
primo... ou seja, não ta certo :P
Você não consegue fazer uma condição do loop melhor, tal que ela verifique as
duas condições e só pare quando o número for um primo palindromo sempre, desde
a 1a verificação? ;)
Sobre a explicação do modulo:
Opa, muito bom! Seems good to me :-)Só acho que você precisa tratar todos os
casos onde $n =~ m/^9+$/, porque só o 99 e 999 não bastam (mas foi legal que
você já tinha percebido o problema deles :-)
Tratar eles é bem fácil eu acho:if($n =~ m/^9+$/){ $r = '1' . (0 x ((length
$n) - 1)) . '1';}
Seems legit?
Por fim, seria legal voce escrever tudo isso na documentação do seu módulo,
pois provavelmente vai ajudar quem estiver escolhendo um para usar :-)
Acho que já estou convencido que sua next_palindrome está ok (tirando esse
problema aí de cima dos números com todos os dígitos 9). Agora só precisamos
melhorar o loop principal do seu programa. Lembre-se do que você quer (um primo
palindromo) e do que você realmente precisa dentro desse seu loop. Tente
construir uma invariante das iterações do loop, o que você pode garantir a cada
passada do loop?
2014-05-03 11:27 GMT-03:00 Aureliano Guedes <guedes_1...@hotmail.com>:
Então, esse problema já é do loop principal e não do módulo. Porque eu faço:
$time = next_palindrome($time);
Antes do loop principal.acho que pode ser corrigido fazendo:
$time = next_palindrome($time) if (!is_palindrome($time));
Fiz isso para evitar que um time() primo finalize o loop mesmo sem ele começar,
já que o loop inicia assim: while(!is_prime($time))
Agora quanto ao módulo em sí, a logica usada é a seguinte:- Um número
palíndromo é obrigatoriamente igual a ele mesmo se lido de traz para frente,
então- Se dividirmos pela metade os dígitos de um numero palíndromo de número
de dígitos maior ou igual a 2 então a primeira metade é obrigatoriamente igual
a segunda lida de traz para frente. Isso me leva as seguintes conclusões:
1- Se o reverso da segunda parte é menor que a primeira parte # 8652 -> 86 >
25logo o próximo palíndromo é obrigatoriamente a primeira parte concatenada
com o reverso dela mesma
# 86 . (reverse 86)Isso se torna verdadeiro porque no caso usado para exemplo
'8668' a segunda parte é o '68' que tem seu reverso '86' que é igual a primeira
parte.
2- Se se o reverso da segunda parte é maior ou igual a primeira parte# 8668 ->
86 == 86 # ou # 8669 -> 86 < 96logo o próximo palíndromo é obrigatoriamente a
primeira parte incrementada concatenada com seu reverso
# 8668 -> 86 +1 -> 87 . 78 -> 8778
Então minha heurística foi aplicada em cima de uma lógica matemática, o que
apesar do módulo não vir com os testes, em meus testes ao final do
desenvolvimento ele fez corretamente todas as respostas.
Inclusive estou fazendo algumas correções para subir estas correções.Eu não sei
fazer direito aqueles testes, mas enviarei com os testes na próxima.
Quanto ao Math::NumSeq::Palindromes, acho que poderia ser melhor de usar, mais
direto, no meu você pode imprimir o próximo palindromo fazendo apenas 'say
next_palindrome($n);'.
From: bruno.b...@gmail.com
Date: Sat, 3 May 2014 10:01:11 -0300
To: rio-pm@pm.org
Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
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_1...@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_1...@hotmail.com
To: rio-pm@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.b...@gmail.com
Date: Mon, 28 Apr 2014 21:24:50 -0300
To: rio-pm@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_1...@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_1...@hotmail.com
To: rio-pm@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.b...@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_1...@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_1...@hotmail.com
To: rio-pm@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: bla...@gmail.com
Date: Sat, 26 Apr 2014 18:39:15 -0300
To: rio-pm@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 <juniiior...@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_1...@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_1...@hotmail.com
To: rio-pm@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 <viniciusmias...@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_1...@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_1...@hotmail.com
To: rio-pm@pm.org
Subject: Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
Boa ideia. Vou tentar.
Blabos de Blebe <bla...@gmail.com> escreveu:
Que tal o menor palíndromo primo maior que time()?
2014-04-17 22:02 GMT-03:00 Aureliano Guedes <guedes_1...@hotmail.com>:
Pode ficar menor.
say '906609'
Tiago Peczenyj <tiago.pecze...@gmail.com> escreveu:
sub palindromo { 906609 }
2014-04-17 21:45 GMT-03:00 Aureliano Guedes <guedes_1...@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@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@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________ Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
--
Bruno C. Buss
http://www.brunobuss.net
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
--
Bruno C. Buss
http://www.brunobuss.net
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
--
Bruno C. Buss
http://www.brunobuss.net
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
--
Bruno C. Buss
http://www.brunobuss.net
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
_______________________________________________
Rio-pm mailing list
Rio-pm@pm.org
http://mail.pm.org/mailman/listinfo/rio-pm
