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

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

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
∇

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

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]
∇