Projeto Euler – #48

O problema #48 do projeto Euler é bem simples. A série 11 + 22 + 33 + … + 1010 = 10405071317. Qual os últimos 10 dígitos da série 11 + 22 + 33 + … + 10001000

Bem, dá para fazer até no papel. Mas como o meu objetivo é aprender J, então vou resolver em J. Mas vou resolver passo a passo conforme o enunciado. Primeiro a geração da sequencia:

>:i.10x
1 2 3 4 5 6 7 8 9 10

Como a sequencia inicia com zero, devemos incrementar os elementos >: e o x foi utilizado para trabalhar com precisão estendida.

^~>:i.10x
1 4 27 256 3125 46656 823543 16777216 387420489 10000000000

O ^ irá elevar um número a um determinado expoente e, como o ~ duplica a lista antes do verbo, significa elevar um número a ele mesmo.

Para somar os elementos de uma lista, inserimos / o verbo + entre cada elemento dela. Como resultado temos:

+/^~>:i.10x
10405071317

Ok, está conforme o enunciado. Para obtermos os últimos dez dígitos do resultado, primeiro deveremos converter o número para um string utilizando “: e, logo em seguida, obter os últimos dez dígitos _10{. (como foi visto na resolução do problema #13, 10{. retorna os 10 primeiros elementos)

_10{.":+/^~>:i.10x
0405071317

A solução não é otimizada e resultou em um tempo mais longo do que eu espera para a sequencia 1…1000. Apesar do problema permitir que eu exclua 100 número dos cálculos (como desejamos os últimos dez dígitos e todo o múltiplo de dez ira gerar um valor como dez ou mais zeros que não seriam significativos na soma), essa exclusão não melhorou muito a performance do cálculo. Após resolver o exercício e entrar no fórum do problema, uma outra forma de resolução do problema em J possui uma performance bem melhor. Enquanto a minha leva 3s, o método lá leva 0.09s. Mas é para quem já está no nível 1 de aprendizado de J.

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

Anúncios

Projeto Euler – Problema #13

Bem, o problema #13 do projeto Euler é bem simples. Apenas pede os 19 primeiros dígitos da soma de 100 números com 50 dígitos cada um. É só somar todos e pegar os 10 primeiro. Mas como resolver em J?

A=: “.;._2(0 : 0)
37107287533902102798797998220837590246510135740250

53503534226472524250874054075591789781264330331690
)
Ok, criamos uma lista com os 100 números de 50 digitos. Para o resultado é só:
10{.”:x:+/A
Mais um sem graça.
+/ soma todos os elementos da lista, x: torna precisão extendida, “: converte para string, 10{. retorna os 10 primeiros elementos.

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