Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
3 Methods to find how many Ways To Traverse a Grid
factorial=10
permutations=10
recursion=10
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))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment