Skip to content

Instantly share code, notes, and snippets.

@mbrenig
Created August 9, 2018 16:28
Show Gist options
  • Save mbrenig/473f81c64c413b68ac1006d6dafb89b2 to your computer and use it in GitHub Desktop.
Save mbrenig/473f81c64c413b68ac1006d6dafb89b2 to your computer and use it in GitHub Desktop.
Word ladder solver (RK)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Copyright (C) Metaswitch Networks.
"""Picks two 5 letter words at random from a dictionary,
finds a route between the words by only changing one letter at a time"""
import random
import heapq
import time
ALPHA = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def read_words_file():
"""Reads 5 letter words in from file
:return: set
"""
read_set = set()
with open('words.txt', "r") as f:
for w in f.readlines():
w_stp_lwr = w.strip('\n').lower()
#Check each word is length 5 and has no punctuation
if len(w_stp_lwr) == 5 and w_stp_lwr.isalpha():
read_set.add(w_stp_lwr)
return read_set
#Idea: traverse graph. Words are nodes.
#Exists an edge between two nodes iff
# possible to transform one word into the other by changing only one letter
def breadth_first_search(root, dest):
"""Performs a BFS on the graph described above.
FIFO queue used
:param root: node to start from.
:type root: str
:param dest: destination node.
:type dest: str
:return: list
"""
visited = set()
q = list()
q.append(word_node(root, []))
while len(q) > 0:
current = q.pop()
print(current.word)
if current.word == dest:
return current.route
for neighbour in find_neighbours(current.word):
if neighbour not in visited:
visited.add(neighbour)
q.append(word_node(neighbour, current.route + [current.word]))
return []
class word_node():
"""
Node class for words. Keeps a route easily
"""
def __init__(self, word, route):
self.word = word
self.route = route
def word(self):
return word
def __lt__(self,other):
return other
def findroute(root, dest):
"""Performs a search on the graph described above.
Add heuristic - "number of letters away from target"
BFS with priority queue
:param root: node to start from.
:type root: str
:param dest: destination node.
:type dest: str
:return: list
"""
visited = set()
q = list()
#Heap elements type: tuple (int, word_node)
heapq.heappush(q, (word_diff(root, dest), word_node(root, [])))
while len(q) > 0:
current = heapq.heappop(q)[1]
if current.word == dest:
return current.route + [dest]
for neighbour in find_neighbours(current.word):
if neighbour not in visited:
visited.add(neighbour)
heapq.heappush(q, (word_diff(neighbour, dest), (word_node(neighbour, current.route + [current.word]))))
return []
def find_neighbours(word):
"""Finds the neighbours of a word.
i.e. change of one letter results in a valid English word
:param word:
:type word: str
:return: list
"""
neighbours = list()
for place in range(0,len(word)):
for l in ALPHA:
new_word = word[:place] + l + word[place+1:]
if new_word != word and new_word in SET_OF_WORDS:
neighbours.append(new_word)
return neighbours
def word_diff(word1, word2):
"""
Outputs number of characters differing.
Assume words are of same length
:param word1:
:param word2:
:return: int
"""
count = 0
for i in range(0, len(word1)):
if word1[i] != word2[i]:
count += 1
return count
start_time = time.time()
SET_OF_WORDS = read_words_file()
word_1 = ""
word_2 = ""
while word_1 == word_2:
word_1 = random.sample(SET_OF_WORDS,1)[0]
word_2 = random.sample(SET_OF_WORDS,1)[0]
print("Random words: '" + word_1 + "' and '" + word_2 + "'")
route = findroute(word_1, word_2)
end_time = time.time()
if not route:
print("Impossible")
else:
print(route)
print("Length of route: %s" % len(route))
time_taken = end_time - start_time
print("Found in time: ")
print(time_taken)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment