APL Hacking: Project Euler Daily (#15)

This was a problem to find all of the forward searching paths in a 20 by 20 grid. This is one that we actually use a lot in our introductory programming courses, but I did not want to do it the way that we do it in those classes, where it is a lesson in recursion. Instead, I applied my rusty knowledge of combinatorics to the problem and remembered how to compute the answer to this problem using binomial coefficients.

The solution, of course, would be too easy if I could just use 20!40 in APL. This number is too large for 32-bit integers, so it goes to floating point, and I lose two digits that I need. I could have done this the long way, but I decided that this would be a great chance to play with the Foreign Function interface to Java.

Problem #15:

∇R←PEFIFTEEN;N;K;FACT;TIMES;NBI;STR;DIV;⎕IO
⎕IO←1
⍝ Compute the number of paths through a 20×20 grid

⍝ which is just 20!40.
N←40 ⋄ K←20
⊣⎕FX 'R←NBI X' 'R←''java'' ⎕NEW ''java.math.BigInteger''(⍕X)'

⊣⎕FX 'R←X TIMES Y' 'R←X.multiply Y'

⊣⎕FX 'R←FACT N' 'R←TIMES/NBI¨⍳N'

⊣⎕FX 'R←STR J' 'R←J.toString'

⊣⎕FX 'R←X DIV Y' 'R←X.divide Y'
R←STR(FACT N)DIV(FACT K)TIMES FACT N-K

∇