Project Euler Problem #15

Home/Uncategorized/Project Euler Problem #15

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #15.

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?

These grids can be represented as a set of nodes pointing from the upper left corner, always down and to the right. The answer is simply the number of unique traversals that can be made of that graph.

Representing the lower right corner as (0,0) and the upper left as (20,20) I’ll produce a memoized function to compute the results:

open System.Collections.Generic
 
let memoize (func:'a->'b) =
  let cache = Dictionary<_, _>()
  fun n ->
    let (found, result) = cache.TryGetValue(n)
    if found then
      result
    else
      let result = func n
      cache.[n] <- result
      result
 
let rec numRoutes =
    let f (x,y) =
        if x = 0 or y = 0
            then 1L
            else numRoutes (x-1,y) + numRoutes (x,y-1)
    f |> memoize
 
let answer = lazy( numRoutes (20,20))
 
answer.Force() |> printfn "Answer = %d"

Pretty good, but if you look closely at the values this generates, if you’re familiar with mathematics you’ll quickly recognize Pascal’s triangle in there – the solution to this problem could easily be solved by one simple mathematical expression!

Leave a Comment