diff options
Diffstat (limited to 'users/wpcarro/scratch/facebook/moderate')
6 files changed, 345 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/facebook/moderate/decompress-xml.py b/users/wpcarro/scratch/facebook/moderate/decompress-xml.py new file mode 100644 index 0000000000..b22983ed7a --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/decompress-xml.py @@ -0,0 +1,98 @@ +import string +from parser import Parser + +mapping = { + 1: "family", + 2: "person", + 3: "firstName", + 4: "lastName", + 5: "state", +} + +def parse_int(i, xs): + result = "" + while i < len(xs) and xs[i] in string.digits: + result += xs[i] + i += 1 + return i, int(result) + +def parse_string(i, xs): + result = "" + while xs[i+1] not in string.digits: + result += xs[i] + i += 1 + return i, result + +def tokenize(xs): + result = [] + i = 0 + while i < len(xs): + if xs[i] in string.digits: + i, n = parse_int(i, xs) + result.append(n) + elif xs[i] in string.ascii_letters: + i, x = parse_string(i, xs) + result.append(x) + elif xs[i] == " ": + i += 1 + continue + return result + +def parse(xs): + parser = Parser(tokenize(xs)) + return parse_element(parser) + +# Element -> Tag Attribute* End Element* End ; +# Tag -> INTEGER ; +# Value -> STRING End ; +# Attribute -> Tag Value ; +# End -> 0 ; + +def parse_element(parser): + if type(parser.curr()) == str: + return parser.consume() + tag_id = parser.expect_predicate(lambda x: type(x) == int) + tag = mapping[tag_id] + attrs = parse_attrs(parser) + parser.expect([0]) + children = [] + while not parser.exhausted() and parser.curr() != 0: + children.append(parse_element(parser)) + parser.expect([0]) + return [tag, attrs, children] + +def parse_attrs(parser): + result = [] + while parser.curr() != 0: + tag_id = parser.expect_predicate(lambda x: type(x) == int) + tag = mapping[tag_id] + value = parser.consume() + result.append((tag, value)) + return result + +def stringify_xml(tree, indent=0): + if type(tree) == str: + return tree + result = "" + tag, attrs, children = tree + + str_attrs = [] + for k, v in attrs: + str_attrs.append("{}=\"{}\"".format(k, v)) + str_attrs = (" " if str_attrs else "") + " ".join(str_attrs) + + str_children = [] + for child in children: + str_children.append(" " * 2 * indent + stringify_xml(child, indent + 1)) + str_children = "\n".join(str_children) + + result += "{}<{}{}>\n{}{}\n{}</{}>".format( + " " * 2 * indent, tag, str_attrs, " " * 2 * indent, str_children, + " " * 2 * indent, tag) + return result + +x = "1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0" +print("Input: {}".format(x)) +print("Tokens: {}".format(tokenize(x))) +print("Parsed: {}".format(parse(x))) +print("{}".format(stringify_xml(parse(x)))) diff --git a/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py b/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py new file mode 100644 index 0000000000..69c2fc4312 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py @@ -0,0 +1,19 @@ +import random + +def find_pairs(xs, n): + """ + Return all pairs of integers in `xs` that sum to `n`. + """ + seeking = set() + result = set() + for x in xs: + if x in seeking: + result.add((n - x, x)) + else: + seeking.add(n - x) + return result + +xs = [random.randint(1, 10) for _ in range(10)] +n = random.randint(1, 10) + random.randint(1, 10) +print("Seeking all pairs in {} for {}...".format(xs, n)) +print(find_pairs(xs, n)) diff --git a/users/wpcarro/scratch/facebook/moderate/parser.py b/users/wpcarro/scratch/facebook/moderate/parser.py new file mode 100644 index 0000000000..57dfb058c0 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/parser.py @@ -0,0 +1,37 @@ +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 next(self): + return self.tokens[self.i + 1] + + def consume(self): + if not self.exhausted(): + self.i += 1 + return self.prev() + + def match(self, xs): + if not self.exhausted() and self.curr() in xs: + self.consume() + return True + return False + + def expect(self, xs): + if not self.match(xs): + raise Exception("Expected token \"{}\" but received \"{}\"".format(xs, self.curr())) + return self.prev() + + def expect_predicate(self, predicate): + if predicate(self.curr()): + return self.consume() + raise Exception("Expected token \"{}\" to pass predicate, but it did not".format(self.curr())) + + def exhausted(self): + return self.i >= len(self.tokens) diff --git a/users/wpcarro/scratch/facebook/moderate/rand7.py b/users/wpcarro/scratch/facebook/moderate/rand7.py new file mode 100644 index 0000000000..ed3a7cea80 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/rand7.py @@ -0,0 +1,25 @@ +# Define a function, rand7, that generates a random number [0,7), using only +# rand5, which generates a random number [0,5). + +import random +from collections import Counter + +# Returns [0,4] +def rand5(): + return random.randint(0,4) + +# Return [0,6] +def rand7_a(): + return sum(rand5() for _ in range(7)) % 7 + +# Return [0,6] +def rand7_b(): + x = 5 * rand5() + rand5() + if x < 21: + return x % 7 + return rand7_b() + +c = Counter([rand7_a() for _ in range(100000)]) +print(c) +c = Counter([rand7_b() for _ in range(100000)]) +print(c) diff --git a/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py b/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py new file mode 100644 index 0000000000..342c29be6b --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py @@ -0,0 +1,99 @@ +import random + +def print_board(board): + result = [] + for row in range(len(board)): + r = [] + for col in range(len(board[row])): + cell = board[row][col] + if not cell: + r.append("-") + else: + r.append(cell) + result.append(" | ".join(r)) + print("\n---------\n".join(result)) + +def init_board(): + result = [] + for row in range(3): + r = [] + for col in range(3): + r.append(None) + result.append(r) + return result + +def check(board, player): + print_board(board) + print() + if player not in "XO": + raise Exception("Only checking the board for Xs or Os. You supplied {}".format(player)) + dn, ax, ddg, udg = "DOWN", "ACROSS", "DOWN_DIAGONAL", "UP_DIAGONAL" + ways = [ + [[dn, ax, ddg], [dn], [dn, udg]], + [[ax], [], []], + [[ax], [], []], + ] + for row in range(len(board)): + for col in range(len(board[row])): + if board[row][col] == player: + xs = ways[row][col] + for x in xs: + if x == dn: + if {player} == {board[row+1][col], board[row+2][col]}: + return True + if x == ax: + if {player} == {board[row][col+1], board[row][col+2]}: + return True + if x == ddg: + if {player} == {board[row+1][col+1], board[row+2][col+2]}: + return True + if x == udg: + if {player} == {board[row+1][col-1], board[row+2][col-2]}: + return True + return False + +def op(player): + return "X" if player == "O" else "O" + +dn_win = lambda p: [ + [op(p), p, None], + [op(p), p, None], + [None, p, None], +] + +ax_win = lambda p: [ + [p, p, p], + [op(p), op(p), None], + [None, None, None], +] + +ddg_win = lambda p: [ + [p, None, None], + [op(p), p, None], + [op(p), None, p], +] + +udg_win = lambda p: [ + [op(p), None, p], + [op(p), p, None], + [p, None, None], +] + +# Down +p = random.choice(["X", "O"]) +assert check(dn_win(p), p) == True +assert check(dn_win(p), op(p)) == False +# Across +p = random.choice(["X", "O"]) +assert check(ax_win(p), p) == True +assert check(ax_win(p), op(p)) == False +# Down Diagonally +p = random.choice(["X", "O"]) +assert check(ddg_win(p), p) == True +assert check(ddg_win(p), op(p)) == False +# Down Diagonally +p = random.choice(["X", "O"]) +assert check(udg_win(p), p) == True +assert check(udg_win(p), op(p)) == False +# Success +print("Tests pass!") diff --git a/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py new file mode 100644 index 0000000000..de7326b058 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py @@ -0,0 +1,67 @@ +# Write a function that accepts an array of integers and returns the indices for +# the starting and ending integers that, if their elements were sorted, the +# entire array would be sorted. + +################################################################################ +# First Attempt +################################################################################ + +def unsorted_substring(xs): + ys = xs[:]; ys.sort() + m = 0 + while xs[m] == ys[m]: + m += 1 + if m >= len(xs): + return -1, -1 + n = len(xs) - 1 + while xs[n] == ys[n]: + n -= 1 + return m, n + +################################################################################ +# Second Attempt +################################################################################ + +def unsorted_substring_2(xs): + beg = 1 + while xs[beg - 1] <= xs[beg]: + beg += 1 + if beg >= len(xs): + return -1, -1 + end = len(xs) - 2 + while xs[end + 1] >= xs[end]: + end -= 1 + + min_mid = xs[beg] + max_mid = xs[beg] + i = beg + 1 + while i <= end: + min_mid = min(min_mid, xs[i]) + max_mid = max(max_mid, xs[i]) + i += 1 + + # beg -= 1 until max(lhs) <= min(mid) + while beg - 1 >= 0 and xs[beg - 1] >= min_mid: + beg -= 1 + + # end += 1 while max(mid) <= min(rhs) + while end + 1 < len(xs) and max_mid >= xs[end + 1]: + end += 1 + return beg, end + +################################################################################ +# Tests +################################################################################ + +xs = [ + [1,2,4,7,10,11,7,12,6,7,16,18,19], + [1,2,3,4], + [4,3,2,1], + [1,3,2,4], + [2,1,3,4], +] + +for x in xs: + print("Testing: {}".format(x)) + print("1) {}".format(unsorted_substring(x))) + print("2) {}".format(unsorted_substring_2(x))) |