Word ladder solver (RK)

words.py

#!/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)