Answered by:
I can not make continuation passing style function to solve problem from Project Euler.
Question

Hi everyone!
I'm newbie in F#. Now I'm trying to solve Problem 15 from project Euler. It says:
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 2020 grid?
Here is my code that fails with StackOverflowException:
let left (x, y) = (x + 1, y) let down (x, y) = (x, y + 1) let (LeftDownBothEnd) (x, y) = if (x < 20 && y >= 20) then Left else if (x >= 20 && y < 20) then Down else if (x < 20 && y < 20) then Both else End let rec compute x count continuation = match x with  End > continuation(count + 1L)  Left > compute (left x) count continuation  Down > compute (down x) count continuation  Both > compute (left x) count (fun acc > compute (down x) acc continuation) let processing = compute (1, 1) 0L (fun x > x) printfn "%A" processing
Please point me where I mistaken.Thanks!
Wednesday, August 17, 2011 2:41 PM
Answers

as far as I can tell serges code is in tailcall style but I guess I didn't check the "use tail calls" settings in "projectsettings/build"
 Marked as answer by serge.prozorov Thursday, August 18, 2011 6:17 AM
Wednesday, August 17, 2011 5:57 PM
All replies

Hi Serge,
I don't see a problem with the continuation passing, and it is running ok for me. But, the algorithm is too slow for this problem.
The code works for smaller problems (10x10), so maybe you can use the code to help you find a more efficient algorithm.
Dave
Wednesday, August 17, 2011 4:22 PM 
A bit OT but if you think a bit on the problem the solution is rather simple math (only the number is asked). You have to make 20+20 moves total (only right and down is ok right?) and you have to make 20 down  moves. So you only have to count the the combinations of possible downmove positions inside your 40 steps. Thats what the binominal coefficient is for (http://en.wikipedia.org/wiki/Binomial_coefficient). So you "just" have to calculate "40 choose 20"  this is a nice problem itself (but not using BigIntegers) but you don't have to enumerate all possible ways...
Sample for 2x2: "4 choose 2" = (4*3)/2! = 2*3 = 6
Sample for 3x3: "6 choose 3" = (6*5*4)/3! = 120/6 = 20
I hope the reasoning is correct ... if not shame on me ;)
Wednesday, August 17, 2011 5:32 PM 
Regardles of the algorithm choice if you want to deal with deep recursion you have to implement tail call optimization. Otherwise you'll sooner or later meet inevitable "StackOverflowException".
See for example: http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understandingtailrecursion.aspx
Petr
Wednesday, August 17, 2011 5:51 PM 
as far as I can tell serges code is in tailcall style but I guess I didn't check the "use tail calls" settings in "projectsettings/build"
 Marked as answer by serge.prozorov Thursday, August 18, 2011 6:17 AM
Wednesday, August 17, 2011 5:57 PM 
I never managed to make it complete with case 20, it was just much too long.
I do not think the following is tail call:
(fun acc > compute (down x) acc continuation)
And I had it bite me in the past trying to implement a simple factorial n that way.
Changing it to the following still completes and gives the same result for grid size 10:
(fun acc > continuation(compute (down x) acc id))
Give that a shot if you have a humongous CPU and it might complete for grid size 20.
Note that the following function is already defined:
let inline id x = x
David
edit: Looking at it now, I don't think the above is tail call either.Thursday, August 18, 2011 12:06 AM 
I think both are  it's the same as your 101 example on trees  see http://weblogs.asp.net/podwysocki/archive/2008/08/13/recursingonrecursioncontinuationpassing.aspx for example.
Maybe the original poster might help by telling us if he checked the option I gave. And someone might try to look at the generated IL (got no reflectorlike tools on this computer  sorry)
Thursday, August 18, 2011 5:49 AM 
Thank you very much! I could not understand why the compiler do not want to translate my code to tail recursive calls. Now it is OK! Yes, of course it is not the best way to solve the problem, but I wanted to make the code work :).Thursday, August 18, 2011 6:17 AM

As others have pointed out, probably a tail call opt. problem.
I solved that problem like this.
https://bitbucket.org/bokmal/projecteuler/src/9d9291f81842/ProjectEuler.Exercises/E015.fsThursday, August 18, 2011 9:30 AM