3 Methods to find how many Ways To Traverse a Grid

output.txt

factorial=10
permutations=10
recursion=10

WaysToTraverseGrid.scala

import scala.annotation.tailrec

/** width by height grid
 starting top left
 how many ways to travel to bottom right?
 can only go right or down
 3 methods shown
**/
object WaysToTraverseGrid extends App{

  val width=4
  val height=3

  val steps=width+height-2

  val factorial: (BigInt) => BigInt = (x: BigInt) => {
    @tailrec def loop(x: BigInt, acc: BigInt = 1): BigInt = {
      if (x <= 1) acc
      else loop(x - 1, x * acc)
    }

    loop(x)
  }
  // 1
  // https://mathlibra.com/number-of-permutations-by-using-kinds-of-duplicate-elements/
  println("factorial="+factorial(steps)/(factorial(width-1)*factorial(height-1)))

  // 2
  val stepList=(List.fill(width-1)(0)++List.fill(height-1)(1))
  val li=stepList.permutations.toList
  println("permutations="+li.size)

  // 3
  def recursion(x: Int, y: Int): Int={
    if (x==1 || y==1) 1
    else{
      recursion(x-1,y)+recursion(x,y-1)
    }
  }

  println("recursion="+recursion(width, height))

}