# ((λ (x) (x x)) (λ (x) (x x)))

Thoughts on Eternity, God, and lesser endeavors

## APL Hacking: Project Euler Daily (#13)

, , , ...

So, this is actually my post for Friday, but since I was traveling, I was not able to post anything for that day.

This one was pretty fun. The problem is that the input to the incoming function was a series of 100 50-digit numbers. Now, this won't fit within 32-bit integers on my system (bah, 32-bit APL on a 64-bit machine, oh well). This required that I split the integers up, do the additions on them in small chunks, and finally apply a carry algorithm to them.

I initially wanted to do this with a scan and a CARRY operator, but I realized that this won't work because of the nature of the scan algorithm. Instead, I had to collect the results of the carry as I went and do a reduce. That seems to work okay, though. Here's the basic use:

```⍝ First ten digits of the sum of the numbers in X.

⌽⊃(100000 CARRY)/⍬,+⌿100 10⍴⎕FI(6000⍴(5⍴1),0)\(~⎕R=X)/X```

I used the following carry algorithm:

```R←E(B CARRY)S

⍝ Performs a carry operation.
R←(¯1↓S),(B|¯1↑S),E+⌊(¯1↑S)÷B```

## APL Hacking: Project Euler Daily (#12)

, , , ...

This was the first problem that I had to deal with that didn't work right or quickly if I used the standard operators the way that I was used to using them. Instead, I had to create some helper functions that made sense. In this case, they were really small, but I decided that now was as good a time as any to play with the Object Oriented features of APLX. In the end, it was actually pretty easy to use compared to what it might have been, and for that, I am grateful that APLX favors simple solutions.

I also took this opportunity to come up with a decent way to give feedback that indicates a not found error.

This is the class that I wrote for the system;

```Twelve; D;R;Match {
D←0⍴0
R←0⍴0

∇X←Match N
X←D<2×+/0=(⍳⌊N*0.5)|N
∇

∇Twelve A
(D R)←A
∇

∇X←Solve;Y;⎕IO
⎕IO←1
∇
}```

And this is my function that uses it for Problem #12:

```∇R←PETWELVE;T

⍝ What is the value of the first triangle number
⍝ to have over five hundred divisors?

T←⎕NEW 'Twelve' 500 13000
R←T.Solve
∇```

## APL Hacking: Project Euler Daily (#11)

, , , ...

I really liked doing this one. I had no idea how to approach this idea at first. I couldn't think of any simple approach to it at all. I decided to look at the APLX Scrapbook and see if I could glean any inspiration from there. Lo, and behold, what did I find, but a snippet of code for raveling the diagonal of a matrix! I did not really understand what the grade up and grade down functions did until I went through this problem. After playing around with the scrapbook entry for a while, it made sense to me, and I could see how to apply it to this problem.

I am fairly certain that after figuring out the diagonals, I neglected to properly think about the rest of the code, but here it is anyways.

Problem #11:

```∇R←PEELEVEN;B;DA;DB;G;S;⎕IO
⎕IO←1

⍝ What is the greatest product of four adjacent numbers in any direction
⍝ (up, down, left, right, or diagonally) in the following 20×20 grid?

G←'08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 '
G←G,'49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 '
G←G,'81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 '
G←G,'52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 '
G←G,'22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 '
G←G,'24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 '
G←G,'32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 '
G←G,'67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 '
G←G,'24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 '
G←G,'21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 '
G←G,'78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 '
G←G,'16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 '
G←G,'86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 '
G←G,'19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 '
G←G,'04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 '
G←G,'88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 '
G←G,'04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 '
G←G,'20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 '
G←G,'20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 '
G←G,'01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'
G←20 20⍴⎕FI G

⍝ Diagonal selector
S←6↓394↑⍋+⌿(⍴G)⊤(⍳⍴,G)-⎕IO

⍝ Edge partition
B←1+0,+\2>/S

⍝ Grab the diagonals
DA←⊃B⊂(,G)[S]
DB←⊃B⊂(,⊖G)[S]

⍝ Best of the products of each way to grab numbers
R←⌈/,4×/DA⍪DB⍪G⍪⍉G
∇```

## APL Hacking: Project Euler Daily (#10)

, , , ...

This was a bit of a fun one, since I had trouble trying to get the result into a 32-bit integer. I had to do a bit of math to get that to work. This one I did a while back, actually, so I am not sure that it contains all of the wisdom that I have learned from the previous feedback!

Problem #10:

```∇R←PETEN;D;I;N;X;⎕IO
⎕IO←1

⍝ Find the Sum of all the primes below two million.

N←2000000 ⋄ I←2 ⋄ X←N⍴1 ⋄ D←10000
LOOP:X[I×1↓⍳⌊N÷I]←0 ⋄ I←I+(I↓X)⍳1 ⋄ →((I*2)≤N)/LOOP
X←+/(2⍴D)⊤X/⍳N

I←(⍴X[1])-4 ⋄ R←(X[1]+⌊X[2]÷D)(D|X[2])
∇```

## APL Hacking: Project Euler Daily (#9)

, , , ...

Finally, we get an interesting one. In this problem, I struggled with a desire to express the solution simply, and to also make it computable in a reasonable amount of time. To make things worse, the simplest approach also uses the most memory. I had to figure out a way to fit things within the limited memory constraints that I have (2GB, yeah, really limited, I know), and also get good, fast results out of the system. More than either of these though, I wanted to have a solution that was immediately comprehensible for what it was doing.

In the end, my solution was to do some initial analysis of the problem, which allowed me to be very confident that there were many less pythagorean triples than there were possible triples summing to 1000. Thus, I started by generating the pythagorean triples in a reasonable range that I figured would contain the solution. After that, I extracted the triples from that and reduced them to only the one combinations that add up to 1000. This will give only a single set of triples, but two different results in two orderings.

This is an especially inefficient operation memory-wise, because it is computing way too many results. On the other hand, for what it is doing, it generates these triples and filters them plenty quick enough.

Problem #9:

```R←PENINE;X;Y;I;⎕IO
⎕IO←1

⍝ Product of the pythagorean triple where a + b + c = 1000.

X←500 ⋄ Y←(⍳X)*2
Y←Y∘.=Y∘.+Y
I←1+(⍴Y)⊤(,Y)/0,⍳(×/⍴Y)-1
R←×⌿1↑[2](1000=+⌿I)/I```

## APL Hacking: Project Euler Daily (#8)

, , , ...

Again, this problem was just too easy. I wonder why this one was even given actually, because in something like Scheme, this would also be very easy.

Anyways, here it is. Nothing fancy here:

```∇R←PEEIGHT;S
S←'73167176531330624919225119674426574742355349194934'
S←S,'96983520312774506326239578318016984801869478851843'
S←S,'85861560789112949495459501737958331952853208805511'
S←S,'12540698747158523863050715693290963295227443043557'
S←S,'66896648950445244523161731856403098711121722383113'
S←S,'62229893423380308135336276614282806444486645238749'
S←S,'30358907296290491560440772390713810515859307960866'
S←S,'70172427121883998797908792274921901699720888093776'
S←S,'65727333001053367881220235421809751254540594752243'
S←S,'52584907711670556013604839586446706324415722155397'
S←S,'53697817977846174064955149290862569321978468622482'
S←S,'83972241375657056057490261407972968652414535100474'
S←S,'82166370484403199890008895243450658541227588666881'
S←S,'16427171479924442928230863465674813919123162824586'
S←S,'17866458359124566529476545682848912883142607690042'
S←S,'24219022671055626321111109370544217506941658960408'
S←S,'07198403850962455444362981230987879927244284909188'
S←S,'84580156166097919133875499200524063689912560717606'
S←S,'05886116467109405077541002256983155200055935729725'
S←S,'71636269561882670428252483600823257530420752963450'

⍝ Find the greatest product of five consecutive digits in S
R←⌈/5×/⎕FI ((2×⍴S)⍴1 0)\S
∇```

## APL Hacking: Project Euler Daily (#7)

, , , ...

Nothing much to say about this one. I use the basic prime sieve on this one. I am still playing with whether I like branch arrows or control structures better.

```∇R←PESEVEN;X;N;⎕IO
⎕IO←1

⍝ The 10001st prime number.

N←150000 ⋄ X←N⍴1 ⋄ I←2
LOOP:X[I×1↓⍳⌊N÷I]←0 ⋄ I←I+(I↓X)⍳1 ⋄ →(N>I*2)/LOOP
X←X/⍳N ⋄ R←(1↓X)[10001]
∇```
December 2013
S M T W T F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31