3 Methods to find how many Ways To Traverse a Grid
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
factorial=10 | |
permutations=10 | |
recursion=10 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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