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

diff --git a/users/wpcarro/scratch/deepmind/part_two/mesh-message.py b/users/wpcarro/scratch/deepmind/part_two/mesh-message.py
new file mode 100644
index 000000000000..a265296ab066
--- /dev/null
+++ b/users/wpcarro/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)