Word-Ladder solver in Python 3 Follow-up to Python program to find a word ladder transforming &quot;four&quot; to &quot;five&quot;

I'm trying to write a program to solve a word ladder puzzle to brush up on my Python. For those who don't know:


  A word ladder puzzle begins with two words, and to solve the puzzle one must find a chain of other words to link the two, in which two adjacent words (that is, words in successive steps) differ by one letter. - Wikipedia


I've implemented breadth first search as opposed to depth first search for a big performance boost since my last question, as suggested in the answers.
I've also added a new mode, that can add and remove letters as well as just swapping them.
Additionally, the program now takes user input, and can take more than two words to link together (given a b c, it runs a b, and then runs b c).

The program now takes ~6 seconds on my machine to run with input of five four and 1. I'm still interested in making this faster, and also would like to know how to make it more Pythonic.

# -------- Data Structures --------
class Queue():
    """ FIFO Queue """
    def __init__(self, parent = None):
        self.list = []
        self.parent = parent
    def append(self, value):
        self.list.append(value)
    def pop(self):
        return self.list.pop(0)

class Node():
    """ Node of a Tree """
    def __init__(self, value, parent = None):
        self.value = value
        self.parent = parent

# -------- Distance Functions --------
def hamming(s1, s2):
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

def levenshtein(s1, s2):
    if len(s1) &lt; len(s2):
        return levenshtein(s2, s1)
    if len(s2) == 0:
        return len(s1)
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

# -------- IO --------

# Print sequence from root to node
def print_words(node):
    values = []
    while isinstance(node, Node):
        values.append(node.value)
        node = node.parent
    print(list(reversed(values)))

# Get all input
all_words = open("/usr/share/dict/words", "r").read().lower().splitlines()
input_words = input("Enter list of words, seperated by spaces: ").split()
input_mode = int(input("Enter 1 for swap-only mode, or 2 for swap-add-rem mode: "))

# Validate user input
if not 1 &lt;= input_mode &lt;= 2:
    raise ValueError("Invalid mode: " + input_mode)

for word in input_words:
    if word not in all_words:
        raise ValueError("Invalid word: " + word)

# Adapt to mode
distance = [hamming, levenshtein][input_mode - 1]
if input_mode == 1:
    all_words = [word for word in all_words if len(word) == len(input_words[0])]

# -------- Breadth First Search --------
def fill(node, to_check, checked):
    checked.add(node.value)
    for word in all_words:
        if 1 &gt;= len(word) - len(node.value) &gt;= -1 and distance(word, node.value) == 1:
            to_check.append(Node(word, node))

for i in range(len(input_words) - 1):
    root = Node(input_words[i])
    checked = set()
    to_check = Queue()

    fill(root, to_check, checked)
    while to_check.list:
        node = to_check.pop()
        if node.value == input_words[i + 1]:
            print_words(node)
            break
        if node.value not in checked:
            fill(node, to_check, checked)
I'm a little bit short on time at the moment, but I'ld like to share a few minor observations with you. Maybe I will also find time to look at performance related optimizations and expand it later.



You said you would like your code to be Pythonic. With that in mind you could replace print(list(reversed(values))) by print(values[::-1]) which uses slicing (nice explanation on Stack Overflow) to revert the list. Since you need the complete list nevertheless, there is no real advantage in using a reverse iterator instead of a list directly.

Also since "Explicit is better than implicit." (from Zen of Python) I would prefer to see 

distance = hamming if input_mode == 1 else levenshtein


or something similar instead of

distance = [hamming, levenshtein][input_mode - 1]


The proposed version would also allow you to drop the string to int conversion. It would even work if the user entered something else than the two values presented by the prompt. levenshtein would be assumed to be the default then. Change the if to your liking if you prefer hamming as default. Although this might not be something to think about, since you have an input validation in place (good). However, the way it is written could be improved since you have a really small range (read: two) values that are valid. That makes it possible to list them explicitly:

# Validate user input
if input_mode not in (1, 2):
    raise ValueError("Invalid mode: " + input_mode) 


This almost reads like normal language.