Projeto Euler – Problema #11

O problema #11 do projeto Euler deseja saber o maior produto de quatro números adjacentes calculados em qualquer direção (direita, esquerda, diagonais, cima, baixo) em uma matriz dada..

 

Como de costume, vamos resolver em J . Vamos começar com uma matriz pequena para facilitar a visualização.

 

   A=. ?. 6 6 $ 10

Ok, criamos uma matriz 6×6 com elementos aleatórios entre 0 a 9 (como foi utilizado o ?. o resultado será sempre o mesmo).

 

   A
6 5 9 2 4 9
0 7 0 4 6 8
3 8 1 2 8 0
0 2 1 6 0 4
4 1 3 3 6 6
5 7 8 8 2 1

Para o agrupamento de quatro elementos de uma coluna podemos utilizar 4\ e termos:

 

   4<\A
┌───────────┬───────────┬───────────┐
│6 5 9 2 4 9│0 7 0 4 6 8│3 8 1 2 8 0│
│0 7 0 4 6 8│3 8 1 2 8 0│0 2 1 6 0 4│
│3 8 1 2 8 0│0 2 1 6 0 4│4 1 3 3 6 6│
│0 2 1 6 0 4│4 1 3 3 6 6│5 7 8 8 2 1│
└───────────┴───────────┴───────────┘

Como é possível ver, a primeira coluna da matriz A contendo 6 0 3 0 4 5 foi seccionada em três com quatro elementos cada: 6 0 3 0, 0 3 0 4 e 3 0 4 5. Todas as outras também. Como tanto faz de baixo para cima ou o contrário que o resultado será o mesmo.

 

   4*/\A
0 560  0  96 0 0
0 112  0 144 0 0
0 112 24 288 0 0

Para saber o maior produto obtido:

 

   >./, 4*/\A 560

A primeira etapa foi muito simples. Bastaram 9 caracteres para resolver o nosso problema. Mas é apenas a primeira etapa. Obtemos a maior soma de quatro número consecutivos de todas as colunas da nossa matriz. Como próxima etapa, podemos calcular a maior soma das linhas da nossa matriz. Para obter o resultado é um pouquinho mais complexo.

 

   >./,4*/\"1 A
2240

Da mesma forma que para as colunas, não é necessário efetuar o mesmo cálculo da esquerda para a direita. Agora entraremos na parte mais complexa. Trabalhar com as diagonais.

 

   A
6 5 9 2 4 9
0 7 0 4 6 8
3 8 1 2 8 0
0 2 1 6 0 4
4 1 3 3 6 6
5 7 8 8 2 1

Para obter as diagonais da matriz é só utilizar /.

 

   </.A
┌─┬───┬─────┬───────┬─────────┬───────────┬─────────┬───────┬─────┬───┬─┐
│6│5 0│9 7 3│2 0 8 0│4 4 1 2 4│9 6 2 1 1 5│8 8 6 3 7│0 0 3 8│4 6 8│6 2│1│
└─┴───┴─────┴───────┴─────────┴───────────┴─────────┴───────┴─────┴───┴─┘

É fácil associar as diagonais com a matriz original.

 

   >./,4*/\"1]/.A
1152

Na diagonal irá fazer diferença da direita para a esquerda e da esquerda para a direita. Então teremos que pegar a outra, que pode ser obtida por:

 

   </.|.A
┌─┬───┬─────┬───────┬─────────┬───────────┬─────────┬───────┬─────┬───┬─┐
│5│7 4│8 1 0│8 3 2 3│2 3 1 8 0│1 6 6 1 7 6│6 0 2 0 5│4 8 4 9│0 6 2│8 4│9│
└─┴───┴─────┴───────┴─────────┴───────────┴─────────┴───────┴─────┴───┴─┘
   >./,4*/\"1]/.|.A
1152

Juntando tudo temos o que poderíamos chamar de ‘one liners’. 😉

 

   (>./,4*/\"1]/.|.A) >. (>./,4*/\"1]/.A) >. (>./,4*/\"1 A) >. >./, 4*/\A
2240

Que nos dará o resultado do problema em uma etapa. É só substituir nossa matriz pela do exercício e o problema estará resolvido.

 

A=: ".;._2(0 : 0)
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
...
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
)

E aplicar o nosso programa de uma linha. 😉

Projeto Euler – Problema #24

A resolução de problema #24 do Projeto Euler não tem muita graça em J. Conforme o enunciado, temos que as permutações possíveis de 0, 1 e 2 são: 012, 021, 102, 120, 201 e 210.

Inicialmente temos que 0, 1 e 2 pode ser traduzido para J como i.3. O número de permutações para três elementos seria dada pelo fatorial de 3 ou !3 em J que é 6. Para resolver as permutações e selecionar uma das sequências utilizamos A. (Anagram Index). Como no exemplo são três elementos e seis possíveis combinações, para obtermos todas as combinações podemos utilizar:

0 1 2 3 4 5 A. 0 1 2

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Apesar do número de permutações aumentar rapidamente e não ser interessante visualizar todas, uma forma mais genéria poderia ser:

(i.!3) A. i.3

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Então, para sabermos a quinta permutação, usamos diretamente 4 A. i.3 que retorna 2 0 1. Para saber a décima sexta permutação onde os elementos são os números inteiros de 0 a 9, podemos escrever:

15 A. i.10

0 1 2 3 4 5 8 7 9 6

Até aqui tudo bem, só que o problema deseja um número sem espaços. A solução mais complicada seria copiar a lista gerada e apagar manualmente os espaços. Outra forma é utilizar a #. (base) utilizando 10 como base. Como exemplo: 10#.2 3 4 => 234. A resposta para o problema ficaria como 10#.999999 A.i.10.

Como uma string é uma lista de caracteres (como pode ser visto no final do artigo sobre programas em uma linha), o problema também poderia ser resolvido usando uma string. No exemplo do problema ficaria:

(i.6) A. '012'

012
021
102
120
201
210

Facinho né?

=-=-=-=-=
Powered by Blogilo

Projeto Euler – Problema #29

Hoje o Thiago Silva colocou no twitter via Thiago Arrais (pô, quanto Thiago): “One word? Inspiring! ‘How I Failed, Failed, and Finally Succeeded at Learning How to Code‘: ”

Legal para ler. Fala do Colin Hughese e da criação do Projeto Euler. Lembrei dos velhos tempos do Ruby e do Code Kata do Dave Thomas. Basicamente, o treino leva a prefeição. Uma mente brilhante e preguiçosa pode ser ultrapassada por uma nem tão brilhante mas ativa.

Como já fiz algumas coisas do Projeto Euler e coloquei aqui, decidi resolver o problema #29. Em J é claro. Após ler o enunciado e pensar um pouquinho (saiu um cheirinho de queimado mas não estragou nada 🙂 ) verifiquei que seria muito fácil resolver em J. Nem impressionaria os seus amigos pois não poderia ser considerado ‘uma linha‘. Talvez alguns caracteres.

A primeira coisa seria gerar uma seqüência para efetuar as operações, no caso elevar os números a uma determinada potência. No caso do exemplo do exercício que tem como base de 2 a 5, a seqüência seria dada por 2+i.4 que resultaria na lista 2 3 4 5. e seria assumida por a e b para efetuar a^b. Então:


^/ ~2+i.4

4   8  16   32
9  27  81  243
16  64 256 1024
25 125 625 3125

Não preciso explicar, mas sabemos que i.x gera uma seqüência de números inteiros entre 0 e x-1, ~ duplica o operador a esqurda do verbo (+~2=4), ^ é para exponenciação e o advérbio / insere o verbo entre cada elemento da lista.

O próximo passo seria eliminar os elementos duplicados. Para tanto nos poderemos converter a matriz gerada pelo resultado em uma lista utilizando , (Ravel) e selecionar os elementos não duplicados utilizando ~. (Nub). Fica:

~. , ^/ ~ 2+i.4

4 8 16 32 9 27 81 243 64 256 1024 25 125 625 3125

Agora é só verificar quantos elementos possui a lista para obtermos a resposta para o problema. Vamos de # (Tally). Temos então, para a resolução do problema conforme o enunciado:

# ~. , ^/ ~ 2+i.4

15

São 15 termos distintos para a=b=2 3 4 5. É só substituir o 4 por (aqui fica por sua conta) para obter o resultado do problema onde a=b=2…100. Como não sabemos os valores resultantes, pode ser interessante colocar o sufixo x no número para trabalhar com precisão extendida e garantir que não haverá conflitos onde o ponto flutuante for assumido. Por exemplo:

32^45

5.39199e67

32^45x

53919893334301279589334030174039261347274288845081144962207220498432

=-=-=-=-=
Powered by Blogilo

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

já

!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│
└─┴─┴─┘