about summary refs log tree commit diff
path: root/users/wpcarro/scratch/facebook/mesh-message.py
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2021-12-13T22·51+0300
committerVincent Ambo <mail@tazj.in>2021-12-13T23·15+0300
commit019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch)
tree76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/facebook/mesh-message.py
parent464bbcb15c09813172c79820bcf526bb10cf4208 (diff)
parent6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff)
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
Diffstat (limited to 'users/wpcarro/scratch/facebook/mesh-message.py')
-rw-r--r--users/wpcarro/scratch/facebook/mesh-message.py40
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 000000000000..8438b059d843
--- /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))