Solve InterviewCake.com's mesh-message problem

Write a function that returns the shortest path between nodes A and B in an
unweighted graph.

I know two algorithms for finding the shortest path in a *weighted* graph:
- Use a heap as a priority queue instead of the regular queue that you would use
  when doing a BFT. This is called Dijkstra's algorithm. You can also use
  Dijkstra's algorithm in an unweight graph by imaginging that all of the
  weights on the edges are the same value (e.g. 1).
- Map the weighted graph into an unweighted graph by inserting N nodes between
  each node, X and Y, where N is equal to the weight of the edge between X and
  Y. After you map the weighted graph into an unweighted graph, perform a BFT
  from A to B. A BFT will always find the shortest path between nodes A and B in
  an unweighted graph.

I had forgotten that a BFT in an unweighted graph will always return the
shortest path between two nodes. I learned two things from InterviewCake.com's
solution:
1. I remembered that a BFT in an unweighted graph will return the shortest
   path (if one exists).
2. I learned to use a dictionary to store the edge information and then
   back-tracking to reconstruct the shortest path.

2 files changed, 184 insertions, 1 deletions

diff --git a/scratch/deepmind/part_two/mesh-message.py b/scratch/deepmind/part_two/mesh-message.py
new file mode 100644
index 000000000000..a265296ab066
--- /dev/null
+++ b/scratch/deepmind/part_two/mesh-message.py
@@ -0,0 +1,183 @@
+import unittest
+from collections import deque
+from heapq import heappush, heappop
+
+
+################################################################################
+# InterviewCake.com
+################################################################################
+# construct_path :: Map String String -> String -> String -> [String]
+def construct_path(paths, beg, end):
+    """
+    Reconstruct the path from `beg` to `end`.
+    """
+    result = []
+    current = end
+
+    print(paths)
+    print(beg, end)
+    print('-----')
+    while current:
+        result.append(current)
+        current = paths[current]
+
+    result.reverse()
+    return result
+
+
+def get_path_ic(graph, beg, end):
+    """
+    InterviewCake uses a dictionary and back-tracking to store and reconstruct
+    the path instead of storing the path as state on each node.
+    This reduces the memory costs. See get_path_bft for an example of this less
+    optimal solution.
+    """
+    if beg not in graph:
+        raise Exception('Origin node absent from graph.')
+
+    if end not in graph:
+        raise Exception('Destination node absent from graph.')
+
+    q = deque()
+    q.append(beg)
+    paths = {beg: None}
+
+    while q:
+        node = q.popleft()
+
+        if node == end:
+            print(graph)
+            return construct_path(paths, beg, end)
+
+        for x in graph[node]:
+            if x not in paths:
+                paths[x] = node
+                q.append(x)
+
+    return None
+
+
+################################################################################
+# Per-node state
+################################################################################
+def get_path_bft(graph, beg, end):
+    """
+    Here we find the shortest path from `beg` to `end` in `graph` by doing a BFT
+    from beg to end and storing the path state alongside each node in the queue.
+    """
+    if beg not in graph:
+        raise Exception('Origin node absent from graph.')
+
+    if end not in graph:
+        raise Exception('Destination node absent from graph.')
+
+    q = deque()
+    seen = set()
+    q.append([beg])
+
+    while q:
+        path = q.popleft()
+        node = path[-1]
+        seen.add(node)
+
+        if node == end:
+            return path
+
+        for x in graph[node]:
+            if x not in seen:
+                q.append(path + [x])
+
+
+################################################################################
+# Dijkstra's Algorithm
+################################################################################
+def get_path(graph, beg, end):
+    """
+    Here we find the shortest path using Dijkstra's algorithm, which is my
+    favorite solution.
+    """
+    if beg not in graph:
+        raise Exception(
+            'The origin node, {}, is not present in the graph'.format(beg))
+
+    if end not in graph:
+        raise Exception(
+            'The origin node, {}, is not present in the graph'.format(end))
+
+    q = []
+    seen = set()
+    heappush(q, (1, [beg]))
+
+    while q:
+        weight, path = heappop(q)
+        node = path[-1]
+        seen.add(node)
+
+        if node == end:
+            return path
+
+        for x in graph[node]:
+            if x not in seen:
+                heappush(q, (weight + 1, path + [x]))
+
+    return None
+
+
+# Tests
+class Test(unittest.TestCase):
+    def setUp(self):
+        self.graph = {
+            'a': ['b', 'c', 'd'],
+            'b': ['a', 'd'],
+            'c': ['a', 'e'],
+            'd': ['b', 'a'],
+            'e': ['c'],
+            'f': ['g'],
+            'g': ['f'],
+        }
+
+    def test_two_hop_path_1(self):
+        actual = get_path(self.graph, 'a', 'e')
+        expected = ['a', 'c', 'e']
+        self.assertEqual(actual, expected)
+
+    def test_two_hop_path_2(self):
+        actual = get_path(self.graph, 'd', 'c')
+        expected = ['d', 'a', 'c']
+        self.assertEqual(actual, expected)
+
+    def test_one_hop_path_1(self):
+        actual = get_path(self.graph, 'a', 'c')
+        expected = ['a', 'c']
+        self.assertEqual(actual, expected)
+
+    def test_one_hop_path_2(self):
+        actual = get_path(self.graph, 'f', 'g')
+        expected = ['f', 'g']
+        self.assertEqual(actual, expected)
+
+    def test_one_hop_path_3(self):
+        actual = get_path(self.graph, 'g', 'f')
+        expected = ['g', 'f']
+        self.assertEqual(actual, expected)
+
+    def test_zero_hop_path(self):
+        actual = get_path(self.graph, 'a', 'a')
+        expected = ['a']
+        self.assertEqual(actual, expected)
+
+    def test_no_path(self):
+        actual = get_path(self.graph, 'a', 'f')
+        expected = None
+        self.assertEqual(actual, expected)
+
+    def test_start_node_not_present(self):
+        with self.assertRaises(Exception):
+            get_path(self.graph, 'h', 'a')
+
+    def test_end_node_not_present(self):
+        with self.assertRaises(Exception):
+            get_path(self.graph, 'a', 'h')
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index b767ecb3d4a0..5d296b9b5287 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -25,7 +25,7 @@
 ** DONE Binary Search Tree Checker
 ** DONE 2nd Largest Item in a Binary Search Tree
 ** DONE Graph Coloring
-** TODO MeshMessage
+** DONE MeshMessage
 ** TODO Find Repeat, Space Edition BEAST MODE
 * Dynamic programming and recursion
 ** TODO Recursive String Permutations