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. 😉
Anúncios