about summary refs log tree commit diff
path: root/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py
blob: 9ccc08526a9954cb58735d2d119c141ae8400a3a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import random

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

def travel(a, b):
    if a == b:
        return 1

    ax, ay = a
    bx, by = b
    if ax > bx or ay > by:
        return 0

    return sum([travel((ax + 1, ay), b), travel((ax, ay + 1), b)])

def travel_compute(a, b):
    bx, by = b
    return int(factorial(bx + by) / (factorial(bx) * factorial(by)))

a = (0, 0)
b = (random.randint(1, 10), random.randint(1, 10))
print("Travelling to {}, {}".format(b[0], b[1]))
print(travel(a, b))
print(travel_compute(a, b))