Lattice path finder using pascal's triange. Tests here : https://gist.github.com/tamizhgeek/827ffaaf3e6856ec6bad

LatticePathFinder.scala

  package assignments

  // m! / n!(n - m)!
  // m = row, n = element

  class Lattice(size : Int) {

      val cache : scala.collection.mutable.Map[(Int, Int), BigInt] = scala.collection.mutable.Map.empty

    /*
        Using pascal's triangle to generate no of paths.

        So the general formula is for nxn grid, the number of paths will be in the
        2n-th row, n/2-th column of the pascal's triangle.

        To generate kth row, nth column value in pascal's triangle the formula is
        n!/k!(n-k)!
     */
      def findNoOfPathsPascalsWay : BigInt = {
        factorial(size * 2) / (factorial(size/2 + 1) * factorial((2 * size) - (size / 2 + 1)))
      }

      /*
        This will surely suck for a 20x20 grid. Incorporated some dyanamic programming. Let's see if this sucks less
        There is a bug in this code. The results for this and pascals way are different.
       */
      def findNoOfPathsTrivialWay() : BigInt = {
        def findPath(down : Int, right : Int) : BigInt = {
          if(down == 0 || right == 0) 1
          else {
            memoized(down - 1, right, findPath) + memoized(down, right - 1, findPath)
          }

        }
        findPath(size, size)
      }

      def memoized(down :Int, right : Int, func : (Int, Int) => BigInt) : BigInt = {
        if(cache.get((down, right)).isEmpty) {
          cache.put((down, right), func.apply(down, right))
        }
        cache.get((down, right)).get
      }

      def factorial(n : Int) : BigInt = {
        def innerFactorial(n: Int, accumulator: BigInt): BigInt = {
          if (n == 1) accumulator
          else innerFactorial(n - 1, n * accumulator)
        }
        innerFactorial(n, BigInt.apply(1))
      }
  }

  object LatticePathFinder extends App {
    println(new Lattice(2).findNoOfPathsTrivialWay)

    println(new Lattice(4).findNoOfPathsTrivialWay)

    println(new Lattice(20).findNoOfPathsTrivialWay)

    println(new Lattice(2).findNoOfPathsPascalsWay)

    println(new Lattice(4).findNoOfPathsPascalsWay)

    println(new Lattice(20).findNoOfPathsPascalsWay)
  }