subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 28 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py
new file mode 100644
index 000000000000..9ccc08526a99
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py
@@ -0,0 +1,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))