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!