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

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 000000000000..b22983ed7aff
--- /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 000000000000..69c2fc431296
--- /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 000000000000..57dfb058c037
--- /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 000000000000..ed3a7cea80e5
--- /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 000000000000..342c29be6bdb
--- /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 000000000000..de7326b05822
--- /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)))