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 + 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
Re: [Rio-pm] [GOLF] Descanso de Pascoa: Maior palindromo
Opa Aureliano,
eu não olhei seu código, só olhei esse seu trecho:
Fazer:
$time = reverse $time;
$time++;
$time = reverse $time;
gera um desempenho melhor que fazer:
$time = reverse (reverse $time++);
Eu não estou preocupado com a performance aqui. Meu ponto é a corretude
disso. Eu posso estar falando besteira, estou com um pouco de sono, mas os
trecho fazem coisas diferentes:
Ex.:
$time_original = time;
print qq{TIME:[$time_original]$/$/};
$time1 = $time_original;
$time2 = $time_original;
{
$time1 = reverse $time1;
$time1++;
$time1 = reverse $time1;
print qq{TIME 1: [$time1]$/$/};
}
{
$time2 = reverse (reverse $time2++);
print qq{TIME 2: [$time2]$/$/};
}
atenciosamente,
Vinícius Miasato
Em 1 de maio de 2014 22:27, Aureliano Guedes guedes_1...@hotmail.comescreveu:
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 +
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
