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/I