F# – Grid Traveler

The grid traveler challenge is basically to find how many ways a traveler can travel to from the top left cell to the bottom right cell (you can move down or right). For a two row and three column grid, there are 3 ways to arrive at the bottom right cell.

The first solution below uses a brute force approach.

// Basic implementation of the grid traveler
let zero = uint64 0
let one = uint64 1
let rec gridTraveler1 (m: uint64, n: uint64) =
    match (m, n) with
        | (m,n) when m = one && n = one -> one
        | (m,n) when m = zero || n = zero -> zero
        | (m, n) -> gridTraveler1(m - one, n) + gridTraveler1(m, n - one)

The solution below uses memorization to save and reuse previous calculations.

// Optimized (memoized) implementation of the grid traveler
open System.Collections.Generic

let rec gridTraveler2 (m: uint64, n: uint64, memo: Dictionary<string, uint64>) =
    let key = $"{m},{n}"
    
    match (m, n) with
        | (_, _) when memo.ContainsKey(key) -> memo[key]
        | (m,n) when m = one && n = one -> one
        | (m,n) when m = zero || n = zero -> zero
        | (m, n) -> 
            memo.Add(key, gridTraveler2(m - one, n, memo) + gridTraveler2(m, n - one, memo))
            memo[key]