-
Notifications
You must be signed in to change notification settings - Fork 3
/
main.py
79 lines (68 loc) · 2.3 KB
/
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import collections
import words
import words2
import pickle
import networkx as nx
names = words2.dictionary
def binarySearch(nameSearch):
global names, found, lower_bound, middle_pos, upper_bound
lower_bound = 0
upper_bound = len(names)-1
found = False
while lower_bound <= upper_bound and not found:
middle_pos = (lower_bound+upper_bound) // 2
if names[middle_pos] < nameSearch:
lower_bound = middle_pos + 1
elif names[middle_pos] > nameSearch:
upper_bound = middle_pos - 1
else:
found = True
if found:
return True
else:
return False
def constructGraph(dictionary):
G=nx.Graph()
G.add_nodes_from(words2.dictionary)
letters=string.ascii_lowercase
for word in dictionary:
for i in range(len(word)):
remove=word[:i]+word[i+1:]
if binarySearch(remove):
G.add_edge(word,remove)
for char in letters:
change=word[:i]+char+word[i+1:]
if binarySearch(change) and change!=word:
G.add_edge(word,change)
for i in range(len(word)+1):
for char in letters:
add=word[:i]+char+word[i:]
if binarySearch(add):
G.add_edge(word,add)
return G
#Citation : transformWord function using BFS adopted from http://www.ardendertat.com/2011/10/17/transform-word/
def transformWord(graph, start, goal):
paths=collections.deque([ [start] ])
extended=set()
while len(paths)!=0:
currentPath=paths.popleft()
currentWord=currentPath[-1]
if currentWord==goal:
return currentPath
elif currentWord in extended:
continue
extended.add(currentWord)
transforms=graph[currentWord]
for word in transforms:
if word not in currentPath:
#avoid loops
paths.append(currentPath[:]+[word])
#no transformation
return []
print("First step")
dictionary = words2.dictionary
graph = constructGraph(dictionary)
print("second step")
nx.write_gpickle(graph,"test2.gpickle")
print("third step")
print(transformWord(graph , 'time' , 'space'))