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

diff --git a/users/wpcarro/scratch/facebook/edit-distance.py b/users/wpcarro/scratch/facebook/edit-distance.py
new file mode 100644
index 000000000000..a5b744f30f27
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/edit-distance.py
@@ -0,0 +1,47 @@
+def print_grid(grid):
+    result = []
+    for row in grid:
+        result.append(" ".join(str(c) for c in row))
+    return print("\n".join(result))
+
+def edit_distance(a, b):
+    """
+    Compute the "edit distance" to transform string `a` into string `b`.
+    """
+    grid = []
+    for row in range(len(a) + 1):
+        r = []
+        for col in range(len(b) + 1):
+            r.append(0)
+        grid.append(r)
+
+    # left-to-right
+    # populate grid[0][i]
+    for col in range(len(grid[0])):
+        grid[0][col] = col
+
+    # top-to-bottom
+    # populate grid[i][0]
+    for row in range(len(grid)):
+        grid[row][0] = row
+
+    for row in range(1, len(grid)):
+        for col in range(1, len(grid[row])):
+            # last characters are the same
+            if a[0:row][-1] == b[0:col][-1]:
+                grid[row][col] = grid[row - 1][col - 1]
+            else:
+                # substitution
+                s = 1 + grid[row - 1][col - 1]
+                # deletion
+                d = 1 + grid[row - 1][col]
+                # insertion
+                i = 1 + grid[row][col - 1]
+                grid[row][col] = min(s, d, i)
+    print_grid(grid)
+    return grid[-1][-1]
+
+result = edit_distance("pizza", "pisa")
+print(result)
+assert result == 2
+print("Success!")