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, 78 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/norman.py b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py
new file mode 100644
index 000000000000..379ba92abba8
--- /dev/null
+++ b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py
@@ -0,0 +1,78 @@
+
+
+
+# Write a function with the following type signature:L
+# equal? :: String -> String -> Bool
+#
+# Determine equality between two inputs with backspace characters encoded as
+# "<".
+
+################################################################################
+# Solution 1
+################################################################################
+
+# from collections import deque
+
+# def equal(a, b):
+#     sa = deque()
+#     sb = deque()
+
+#     for c in a:
+#         if c == '<':
+#             sa.pop()
+#         else:
+#             sa.append(c)
+
+#     for c in b:
+#         if c == '<':
+#             sb.pop()
+#         else:
+#             sb.append(c)
+
+#     return sa == sb
+
+################################################################################
+# Solution 2
+################################################################################
+
+def handle_dels(num_dels, i, xs):
+    if i < 0:
+        return -1
+
+    while xs[i] == '<':
+        num_dels += 1
+        i -= 1
+
+    while num_dels > 0 and xs[i] != '<':
+        num_dels -= 1
+        i -= 1
+
+    if xs[i] == '<':
+        return handle_dels(num_dels, i, xs)
+    else:
+        return i
+
+def update_index(i, xs):
+    # TODO: Indexing into non-available parts of a string.
+    if xs[i] != '<' and xs[i - 1] != '<':
+        return i - 1
+
+    elif xs[i - 1] == '<':
+        return handle_dels(0, i - 1, xs)
+
+def equal(a, b):
+    ia = len(a) - 1
+    ib = len(b) - 1
+
+    while ia >= 0 and ib >= 0:
+        if a[ia] != b[ib]:
+            return False
+        ia = update_index(ia, a)
+        ib = update_index(ib, b)
+
+    if ia != 0:
+        return update_index(ia, a) <= -1
+    if ib != 0:
+        return update_index(ib, b) <= -1
+
+    return True