locked
I can not make continuation passing style function to solve problem from Project Euler. RRS feed

  • 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 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

    How many routes are there through a 20×20 grid?

    Here is my code that fails with StackOverflowException:

    let left (x, y) = (x + 1, y)
    let down (x, y) = (x, y + 1)
    
    let (|Left|Down|Both|End|) (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 tail-call style but I guess I didn't check the "use tail calls" settings in "project-settings/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 down-move 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/understanding-tail-recursion.aspx

     


    Petr

    Wednesday, August 17, 2011 5:51 PM
  • as far as I can tell serges code is in tail-call style but I guess I didn't check the "use tail calls" settings in "project-settings/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/recursing-on-recursion-continuation-passing.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 reflector-like 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.fs 

    Thursday, August 18, 2011 9:30 AM