1 files changed, 21 insertions, 0 deletions
diff --git a/finder.py b/finder.py
new file mode 100644
index 0000000..0a5fff3
--- /dev/null
+++ b/finder.py
@@ -0,0 +1,21 @@
+import sys
+
+def find_transformations(input_word, output_word, graph):
+    seen = set([input_word])
+    queue = [(input_word, ())]
+    while queue:
+        (i, parents) = queue.pop(0)
+        can_make = [j for j in graph[i] if j not in seen]
+        if output_word in can_make:
+            print ' '.join(parents), output_word
+            return True
+        new_parents = parents + (i,)
+        queue.extend([(w, new_parents) for w in can_make])
+        for w in can_make: seen.add(w)
+    return False
+
+if __name__ == '__main__':
+    assert len(sys.argv[1]) == len(sys.argv[2])
+    graph = __import__('graph_%d' % len(sys.argv[1])).graph
+    find_transformations(sys.argv[1], sys.argv[2], graph)
+