about summary refs log tree commit diff
path: root/scratch/data_structures_and_algorithms/norman.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-02-12T16·58+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-02-12T16·58+0000
commitfabf1c9334a86d55be133da851cafccc9e6319fe (patch)
treee5c07cbe676c4955d9a48742d00e0081b16b3446 /scratch/data_structures_and_algorithms/norman.py
parent5ec5a6da8cbfe3c35558fd2c17ef779b5d0ccb54 (diff)
Tidy up structure of briefcase
I had a spare fifteen minutes and decided that I should tidy up my
monorepo. The work of tidying up is not finished; this is a small step in the
right direction.

TL;DR
- Created a tools directory
- Created a scratch directory (see README.md for more information)
- Added README.md to third_party
- Renamed delete_dotfile_symlinks -> symlinkManager
- Packaged symlinkManager as an executable symlink-mgr using buildGo
Diffstat (limited to 'scratch/data_structures_and_algorithms/norman.py')
-rw-r--r--scratch/data_structures_and_algorithms/norman.py78
1 files changed, 78 insertions, 0 deletions
diff --git a/scratch/data_structures_and_algorithms/norman.py b/scratch/data_structures_and_algorithms/norman.py
new file mode 100644
index 000000000000..379ba92abba8
--- /dev/null
+++ b/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