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

9 files changed, 372 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
new file mode 100644
index 000000000000..03b2de015dfe
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
@@ -0,0 +1,33 @@
+from math import floor
+
+def find_magic_index_brute(xs):
+    for i in range(len(xs)):
+        if xs[i] == i:
+            return i
+    return -1
+
+def mid(lo, hi):
+    return lo + floor((hi - lo) / 2)
+
+def find_magic_index(xs):
+    lo, hi = 0, len(xs) - 1
+    return do_find_magic_index(xs, 0, len(xs) - 1)
+
+def do_find_magic_index(xs, lo, hi):
+    pass
+
+xss = [
+    [],
+    [-1,0,2,4,5,6],
+    [1,1,1,1,1,5],
+    [-2,-2,-2,-2,4],
+    [1,2,3,4,5],
+]
+
+for xs in xss:
+    print(xs)
+    a = find_magic_index_brute(xs)
+    b = find_magic_index(xs)
+    print(a, b)
+    assert a == b
+    print("Success!")
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/making-change.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/making-change.py
new file mode 100644
index 000000000000..30c95a66c319
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/making-change.py
@@ -0,0 +1,56 @@
+# Given an infinite supply of:
+#   - quarters
+#   - dimes
+#   - nickels
+#   - pennies
+# Write a function to count the number of ways to make change of n.
+
+def get(table, row, col):
+    """
+    Defensively get cell `row`, `col` from `table`.
+    """
+    if row < 0 or row >= len(table):
+        return 0
+    if col < 0 or col >= len(table[0]):
+        return 0
+    return table[row][col]
+
+def print_table(table):
+    print('\n'.join([
+        ','.join([str(col) for col in table[row]])
+        for row in range(len(table))]))
+
+def init_table(rows=0, cols=0, default=0):
+    result = []
+    for row in range(rows):
+        r = []
+        for col in range(cols):
+            r.append(default)
+        result.append(r)
+    return result
+
+def make_change(n):
+    coins = [1, 5, 10, 25]
+    table = init_table(rows=len(coins), cols=n)
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_coin = coins[row]
+            curr_n = col + 1
+            # a
+            a = get(table, row - 1, col)
+            # b
+            b = get(table, row, curr_n - curr_coin - 1)
+            # c
+            c = 1 if curr_coin <= curr_n else 0
+            # commit
+            if curr_coin == curr_n:
+                table[row][col] = a + c
+            else:
+                table[row][col] = a + b * c
+            # debug
+            print_table(table)
+            print()
+    return table[-1][-1]
+
+print(make_change(7))
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py
new file mode 100644
index 000000000000..e9e7f6a9c159
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py
@@ -0,0 +1,36 @@
+from collection import deque
+
+def fill(point, canvas, color):
+    if x not in canvas:
+        return
+    elif y not in canvas[x]:
+        return
+
+    x, y = point
+    if canvas[y][x] == color:
+        return
+    canvas[y][x] = color
+    fill((x + 1, y), canvas, color)
+    fill((x - 1, y), canvas, color)
+    fill((x, y + 1), canvas, color)
+    fill((x, y - 1), canvas, color)
+
+def fill_bfs(point, canvas, color):
+    x, y = point
+    if x not in canvas:
+        return None
+    if y not in canvas[x]:
+        return None
+    xs = deque()
+    xs.append((x, y))
+    while xs:
+        x, y = xs.popleft()
+        canvas[y][x] = color
+        for x2, y2 in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
+            if x2 not in canvas:
+                continue
+            elif y2 not in canvas[x2]:
+                continue
+            if canvas[y2][x2] != color:
+                xs.append((x2, y2))
+    return None
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py
new file mode 100644
index 000000000000..f406d64e657f
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py
@@ -0,0 +1,114 @@
+# BNF
+# expression -> bool ( ( '|' | '&' | '^' ) bool )*
+# bool       -> '0' | '1'
+
+def tokenize(xs):
+    result = []
+    for c in xs:
+        if c == '0':
+            result.append(0)
+        elif c == '1':
+            result.append(1)
+        elif c in "&|^":
+            result.append(c)
+        else:
+            raise Exception("Unexpected token, \"{}\"".format(c))
+    return result
+
+class Parser(object):
+    def __init__(self, tokens):
+        self.tokens = tokens
+        self.i = 0
+
+    def prev(self):
+        return self.tokens[self.i - 1]
+
+    def curr(self):
+        return self.tokens[self.i]
+
+    def match(self, xs):
+        if self.exhausted():
+            return False
+        if (self.curr() in xs):
+            self.consume()
+            return True
+        return False
+
+    def consume(self):
+        result = self.curr()
+        self.i += 1
+        return result
+
+    def exhausted(self):
+        return self.i >= len(self.tokens)
+
+def recursive_descent(tokens):
+    parser = Parser(tokens)
+    return parse_expression(parser)
+
+def parse_expression(parser):
+    lhs = parse_bool(parser)
+    while parser.match(['|', '&', '^']):
+        op = parser.prev()
+        rhs = parse_expression(parser)
+        lhs = [op, lhs, rhs]
+    return lhs
+
+def parse_bool(parser):
+    if parser.curr() == 0:
+        parser.consume()
+        return False
+    elif parser.curr() == 1:
+        parser.consume()
+        return True
+    else:
+        raise Exception("Unexpected token: {}".format(parser.curr()))
+
+def f(expr, result):
+    tokens = tokenize(expr)
+    tree = recursive_descent(tokens)
+    return do_f(tree, result)
+
+def do_f(tree, result):
+    if type(tree) == bool:
+        if tree == result:
+            return 1
+        else:
+            return 0
+
+    op, lhs, rhs = tree[0], tree[1], tree[2]
+    truth_tables = {
+        True: {
+            '|': [
+                (True, True),
+                (True, False),
+                (False, True),
+            ],
+            '&': [
+                (True, True),
+            ],
+            '^': [
+                (True, False),
+                (False, True),
+            ],
+        },
+        False: {
+            '|': [
+                (False, False),
+            ],
+            '&': [
+                (False, False),
+                (True, False),
+                (False, True),
+            ],
+            '^': [
+                (True, True),
+                (False, False),
+            ],
+        }
+    }
+
+    return sum([do_f(lhs, x) * do_f(rhs, y) for x, y in truth_tables[result][op]])
+
+print(f("1^0|0|1", False))
+print(f("1|0|1|1", False))
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/permutations.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/permutations.py
new file mode 100644
index 000000000000..e23972d4186d
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/permutations.py
@@ -0,0 +1,13 @@
+def char_and_rest(i, xs):
+    return xs[i], xs[:i] + xs[i+1:]
+
+# perms :: String -> [String]
+def perms(xs):
+    if len(xs) == 1:
+        return [xs]
+    result = []
+    for c, rest in [char_and_rest(i, xs) for i in range(len(xs))]:
+        result += [c + perm for perm in perms(rest)]
+    return result
+
+print(perms("cat"))
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))
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py
new file mode 100644
index 000000000000..5eb4a8560674
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py
@@ -0,0 +1 @@
+# accidentally deleted my solution... TBI (again)
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/subsets.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/subsets.py
new file mode 100644
index 000000000000..a6d26aa85055
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/subsets.py
@@ -0,0 +1,41 @@
+# take-aways:
+#   - Use integers as lists of boolean values
+#   - Use 1 << n to compute 2^n where n = len(xs)
+
+def set_from_int(xs, n):
+    result = []
+    for i in range(len(xs)):
+        if n & (1 << i) != 0:
+            result.append(xs[i])
+    return result
+
+# subsets :: Set a -> List (Set a)
+def subsets(xs):
+    n = len(xs)
+    return [set_from_int(xs, i) for i in range(1 << n)]
+
+#   0 1 2
+# 0 N Y Y
+# 1 _ N Y
+# 2 _ _ N
+
+# For my interview, be able to compute *permutations* and *combinations*
+
+# This differs from permutations because this is about finding combinations...
+#
+# bottom-up
+# 0 =>        { }
+# 1 =>  {3}   {4}   {3}
+# 2 => {5,4} {5,3} {4,3}
+
+xs = [
+    ([], [[]]),
+    ([5], [[], [5]]),
+    ([5,4], [[],[5],[4],[5,4]]),
+]
+
+for x, expected in xs:
+    result = subsets(x)
+    print("subsets({}) => {} == {}".format(x, result, expected))
+    assert result == expected
+    print("Success!")
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
new file mode 100644
index 000000000000..56f2c0b27456
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
@@ -0,0 +1,50 @@
+def valid_parens(n):
+    if n == 0:
+        return []
+    if n == 1:
+        return ["()"]
+
+    result = set()
+    for x in valid_parens(n - 1):
+        result.add("({})".format(x))
+        result.add("(){}".format(x))
+        result.add("{}()".format(x))
+    return result
+
+def valid_parens_efficient(n):
+    result = []
+    curr = [''] * n**2
+    do_valid_parens_efficient(result, curr, 0, n, n)
+    return result
+
+def do_valid_parens_efficient(result, curr, i, lhs, rhs):
+    if lhs == 0 and rhs == 0:
+        result.append(''.join(curr))
+    else:
+        if lhs > 0:
+            curr[i] = '('
+            do_valid_parens_efficient(result, curr, i + 1, lhs - 1, rhs)
+        if rhs > lhs:
+            curr[i] = ')'
+            do_valid_parens_efficient(result, curr, i + 1, lhs, rhs - 1)
+
+# Avoids recursion by using either a stack or a queue. I think this version is
+# easier to understand.
+def valid_parens_efficient_2(n):
+    result = []
+    xs = []
+    xs.append(('', n, n))
+    while xs:
+        curr, lhs, rhs = xs.pop()
+        print(curr)
+        if lhs == 0 and rhs == 0:
+            result.append(''.join(curr))
+        if lhs > 0:
+            xs.append((curr + '(', lhs - 1, rhs))
+        if rhs > lhs:
+            xs.append((curr + ')', lhs, rhs - 1))
+    return result
+
+# print(valid_parens(4))
+print(valid_parens_efficient(3))
+print(valid_parens_efficient_2(3))