Projeto Euler – Problema #20 em J

O problema 20 deseja saber a soma dos dígitos de um determinado fatorial. Como exemplo dá o fatorial de 10 que é:

10! = 10 x 9 x 8 x ... x 1 = 3628800

e o resultado do problema deve ser:

3+6+2+8+8+0+0 = 27

Para calcular o fatorial de um número bastaria gerar uma sequencia com >:i.n e inserir a multiplicação entre os termos do vetor */>:5 => 120. Mesmo assim J possui a definição Factorial ‘!’ na linguagem. Então é mais fácil escrever 5!.

A segunda parte que é a soma dos dígitos e deveria ser simples, para mim não foi. Pelo meu ainda pequeno conhecimento da linguagem e seus diversos caminhos, não consegui achar facilmente na documentação uma forma de somar os dígitos e passar uma explicação de uma forma mais idiomática. Apenas colar uma resposta do tipo +/”.”0″:!3628800 => 27 não faz muito sentido. Estou compartilhando o aprendizado e não querendo demonstrar algo que não sei. Na expressão anterior, o “0 não me deu uma resposta a contento.

Resolvi efetuar a tarefa de uma forma mais comum (pelo menos para quem não está acostumado com a linguagem). O método é simples. Enquanto o número for maior que zero, pegamos o módulo do número dividido por 10, colocamos em um vetor e dividimos o número por 10 e pegamos a parte inteira. Depois somamos os valores do vetor com +/ e pronto. Não é elegante mas funciona. Fazer o que? O verbo ficou assim:

sd=: 3 : 0
d=.0
while. y>0 do.
d=.d,10|y
y=.<. y % 10
end.
+/d
)

A maioria das linguagens possui um loop do tipo while, então fica fácil de compreender (só muda os pontos após o while, do e end). Adicionamos o resto da divisão do número por 10 10|y em um vetor utilizando Append ‘,’, dividimos o número por 10 e pegamos a parte inteira (Floor) e reiniciamos o laço. Ao término somamos os valores e obtemos o resultado. Então:

sd !10 => 27

Agora é só trocar o !10 por !100x para obter o resultado. É importante o x no final do número para trabalhar com número estendidos e não receber um resultado que não possua todos os dígitos significativos.

!15 => 1.30767e12

!15x => 1307674368000

Até a próxima, mas antes um comentário. Utilizando as estruturas de controles da minha solução, nem existe diferença no tempo de execução entre ela e +/”.”0″:!100x (fatorial de 100 possui 158 dígitos). Algo em torno de 0,05s. Porém, se colocarmos como argumento o fatorial de 1000 (resultado com 2568 dígitos), a minha solução leva 0,5s para mostrar a resposta, enquanto que a mais otimizada leva 0,06s. Um diferença de tempo de quase 10x entre as duas soluções.

Como após resolver o problema não estava disponível nenhum documento com outras explicações sobre a resolução da questão, acredito que não exista nenhuma fórmula mirabolante para se chegar ao resultado a não ser efetuar o fatorial de 100.

Apesar de já ter resolvido outras questões que não coloquei no blog, as coisas estão ficando mais difíceis para quem não tem uma formação nas exatas ou já terminou os estudos há algum tempo e esqueceu muita coisa. 😀

p.s.: Depois de ler um pouco sobre matrizes, dimensões e células, a construção: “.”0”:123 faz todo o sentido. Parece ser a única forma normal para a extração dos dígitos de um número. Mais informações podem ser obtidas aqui e aqui. Usando Box < fica mais fácil a visualização do resultado de “0.

<'123'
┌───┐
│123│
└───┘
<"0'123'
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘

Anúncios