basic bridge

1 files changed, 56 insertions, 0 deletions

diff --git a/cli/commands/bridge/words.py b/cli/commands/bridge/words.py
index 277b069..5ebb078 100644
--- a/cli/commands/bridge/words.py
+++ b/cli/commands/bridge/words.py
@@ -19,6 +19,7 @@ def cli(ctx, opt_word_a, opt_word_b):
   thesaurus = Thesaurus()
   print(f"Starting word: {opt_word_a}")
   print(f"Ending word: {opt_word_b}")
+  visited = set()
   results_a = thesaurus.search(opt_word_a)
   results_b = thesaurus.search(opt_word_b)
   # use sets
@@ -28,3 +29,58 @@ def cli(ctx, opt_word_a, opt_word_b):
   #   search for first word in results_a
   #   loop over results...
   # print(json.dumps(results, indent=2))
+
+  dist = 0
+  marked = {}
+  queue = [opt_word_a]
+  found = False
+  # First compute distance to each node to find a path
+  while len(queue):
+    dist = dist + 1
+    print(f"Iteration: distance {dist}, {len(queue)} items in queue")
+    newqueue = []
+    for word_q in queue:
+      word_result = thesaurus.search(word_q)
+      for cat in word_result['categories']:
+        catid = cat['catid']
+        if catid in marked:
+          continue
+        marked[catid] = dist
+        category_result = thesaurus.category(catid)
+        for word_c in category_result['words']:
+          word_n = word_c['word']
+          if word_n in marked:
+            continue
+          marked[word_n] = dist
+          if word_n == opt_word_b:
+            thesaurus.search(word_n)
+            found = True
+            break
+          newqueue.append(word_n)
+    queue = newqueue
+
+  if not Found:
+    print(f"No path found, distance of {dist} reached, {len(marked)} nodes checked")
+    return
+
+  # Then follow the chain of shortest distance to follow the path
+  word_n = opt_word_b
+  while word_n != opt_word_a:
+    dist = 999999
+    next_catid = ""
+    next_word = ""
+    word_result = thesaurus.search(word_n)
+    print(f"-> {word_result['word']}")
+    for cat in word_result['categories']
+      catid = cat['catid']
+      if catid in marked and marked[catid] < dist:
+        dist = marked[catid]
+        next_catid = catid
+    cat_result = thesaurus.category(catid)
+    print(f"-> {cat_result['category']}")
+    for word_c in category_result:
+      word_n = word_c['word']
+      if word_n in marked and marked[word_n] < dist:
+        next_word = word_n
+    word_n = next_word
+  print(f"-> {word_n}")