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

Sábado Maio 3 14:57:58 PDT 2014

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_1000 em hotmail.com>:

> Então, esse problema já é do loop principal e não do módulo.
> Porque eu faço:
>
>    1. $time = next_palindrome($time);
>
> Antes do loop principal.
> acho que pode ser corrigido fazendo:
>
>    1. $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 > 25
> logo  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 < 96
> logo 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.buss em gmail.com
> Date: Sat, 3 May 2014 10:01:11 -0300
>
> To: rio-pm em 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_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
>
> _______________________________________________ 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/451b7a49/attachment-0001.html>