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

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).

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