Skip to content

Instantly share code, notes, and snippets.

@mcgrew
Created October 13, 2021 15:28
Show Gist options
  • Save mcgrew/d75234a51bb3dbc1fd6f142ce456bacf to your computer and use it in GitHub Desktop.
Save mcgrew/d75234a51bb3dbc1fd6f142ce456bacf to your computer and use it in GitHub Desktop.
Word ladder solver exercise
#!/usr/bin/env python3
from sys import argv
from collections import deque, defaultdict
DICTFILE = "/usr/share/dict/words"
def get_words(length):
words = []
with open(DICTFILE, 'r') as dictfile:
for i in dictfile:
i = i.strip()
if len(i) == length and i.isalpha() and i.islower():
words.append(i)
return words
def diffcount(s,t):
count = 0
for x,y in zip(s, t):
if x != y:
count += 1
return count
def find_shortest_path(graph, start, end):
dist = {start: [start]}
q = deque([start])
while len(q):
at = q.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = [dist[at], next]
q.append(next)
return flatten_result(dist.get(end))
def flatten_result(result):
while isinstance(result[0], list):
result = result[0] + result[1:]
return result
def main():
start = argv[1]
end = argv[2]
graph = defaultdict(lambda: [])
if len(start) != len(end):
print(f"{start}({len(start)}) and {end}({len(end)}) are not the same "
"length!")
return
wordlist = get_words(len(start))
if start not in wordlist:
print(f"{start} is not a word")
return
if end not in wordlist:
print(f"{end} is not a word")
return
graph[start] = [w for w in wordlist if diffcount(w, start) == 1]
fail = False
while not fail:
fail = True
for k,v in [*graph.items()]:
for word in v:
if word not in graph:
fail = False
graph[word] = [w for w in wordlist if diffcount(w, word) == 1]
if end in graph[word]:
print()
path = find_shortest_path(graph, start, end)
if path:
print(' -> '.join(path))
return
else:
fail = True
print("No path found")
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment