Problem:
You are playing a 2D game where your character is trapped within a
$6 \times 6$grid. Your character starts at$(0,0)$and can only move up and right.How many possible paths can your character take to get to
$(6,6)$?
No matter the path we take, our total moves will be 12 where 6 are up and 6 are right.
We can compute the number of possible paths by computing the number of ways to choose 6 up moves out of 12 total moves.
This is done by using the combination formula:
$$ \binom{n}{r} = \frac{n!}{r!(n-r)!} $$
Where $n$ is the total number of moves and $r$ is the number of up moves. First we need to create a function which computes the factorial of a number.
f = lambda n: 1 if n == 0 else n * f(n - 1)
This is a recursive function which computes the factorial of a number from $n$ to $1$. In our example, the factorial of 6 is written as:
$$ 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 $$
The function becomes convient espcially when we want to compute the factorial of a large number. You don’t want to be doing this by hand..
To then compute the answer, we can use the combination formula but written as:
n = 12
r = 6
print((f(n))/(f(r)*f((n-r))))
Which give us 924 possible paths.