diff options
Diffstat (limited to 'users/wpcarro/scratch/facebook/recursion-and-dynamic-programming')
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 0000000000..03b2de015d --- /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 0000000000..30c95a66c3 --- /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 0000000000..e9e7f6a9c1 --- /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 0000000000..f406d64e65 --- /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 0000000000..e23972d418 --- /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 0000000000..9ccc08526a --- /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 0000000000..5eb4a85606 --- /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 0000000000..a6d26aa850 --- /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 0000000000..56f2c0b274 --- /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)) |