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

diff --git a/users/wpcarro/scratch/facebook/mesh-message.py b/users/wpcarro/scratch/facebook/mesh-message.py
new file mode 100644
index 0000000000..8438b059d8
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/mesh-message.py
@@ -0,0 +1,40 @@
+from heapq import heappush, heappop
+import random
+
+def shortest_path(a, b, graph):
+    seen = set()
+    h = []
+    heappush(h, (0, a, [a]))
+    while h:
+        km, x, path = heappop(h)
+        if x == b:
+            return path
+        for c in graph[x]:
+            if c not in seen:
+                heappush(h, (km + 1, c, path + [c]))
+    raise Exception("We were unable to find a path from {} to {}".format(a, b))
+
+graph = {
+    'Min'     : ['William', 'Jayden', 'Omar'],
+    'William' : ['Min', 'Noam'],
+    'Jayden'  : ['Min', 'Amelia', 'Ren', 'Noam'],
+    'Ren'     : ['Jayden', 'Omar'],
+    'Amelia'  : ['Jayden', 'Adam', 'Miguel'],
+    'Adam'    : ['Amelia', 'Miguel', 'Sofia', 'Lucas'],
+    'Miguel'  : ['Amelia', 'Adam', 'Liam', 'Nathan'],
+    'Noam'    : ['Nathan', 'Jayden', 'William'],
+    'Omar'    : ['Ren', 'Min', 'Scott'],
+    'Liam'    : ['Ren'],
+    'Nathan'  : ['Noam'],
+    'Scott'   : [],
+}
+
+result = shortest_path('Jayden', 'Adam', graph)
+print(result)
+assert result == ['Jayden', 'Amelia', 'Adam']
+print('Success!')
+
+beg = random.choice(list(graph.keys()))
+end = random.choice(list(graph.keys()))
+print("Attempting to find the shortest path between {} and {}".format(beg, end))
+print(shortest_path(beg, end, graph))