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

diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py
new file mode 100644
index 000000000000..c9d7d9d74151
--- /dev/null
+++ b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py
@@ -0,0 +1,97 @@
+import unittest
+from collections import deque
+
+
+################################################################################
+# Solution
+################################################################################
+# get_path :: G(V, E) -> V -> V -> Maybe([V])
+def get_path(g, src, dst):
+    q = deque()
+    result = None
+    seen = set()
+    q.append(([], src))
+
+    if src not in g or dst not in g:
+        raise Exception
+
+    while q:
+        p, node = q.popleft()
+
+        seen.add(node)
+
+        if node == dst:
+            if not result:
+                result = p + [node]
+            elif len(p + [node]) < len(result):
+                result = p + [node]
+        else:
+            if node not in g:
+                raise Exception
+            for x in g.get(node):
+                if not x in seen:
+                    q.append((p + [node], x))
+
+    return result
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def setUp(self):
+        self.graph = {
+            'a': ['b', 'c', 'd'],
+            'b': ['a', 'd'],
+            'c': ['a', 'e'],
+            'd': ['a', 'b'],
+            '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)