blob: 0a5fff382d0fc1c4566e7aafb4a97ab1394609b9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
|
