Results

Code

Straightforward BFS

# Problem data
with open('sgb-words.txt') as f: S=set(x.strip() for x in f.readlines())
entries=[ ["stone", "money"], ["bread", "crumb"], ["smile", "giant"], ["apple", "zebra"], ["other", "night"], ["bread", "blood"], ["black", "white"]]
alphabet=[chr(x) for x in range(ord('a'), ord('z'))]

# BFS
def path(word, target):
    l=[(word,)] # Words to explore
    visited=set() # Already explored words
    while len(l)>0:
        p=l.pop(0) # Try to start from the closest to the start (BFS)
        w=p[-1]
        visited.add(w) # mark it visited
        # For all successors
        for i in range(5):
            for c in alphabet:
                nw = w[:i] + c + w[i+1:]
                # If it is the target, end here (BFS should guarantee that it is the shortest possible path)
                if nw==target: return p+(nw,)
                # If it is a word and we haven't treated it yet, add to todo list
                if nw in S and nw not in visited:
                    l.append(p+(nw,))

# Generate solution in markup (forum) format
print("| Start | End | Number of steps | Path |")
print("| - | - | - | - |")
for e in entries:
    p=path(*e)
    if p:
        print(f"| {e[0]} | {e[1]} | {len(p)} | {p} |")
    else:
        print(f"| {e[0]} | {e[1]} | ∞ | No solution |")

Remarks

Successor

There are two direct ways to search a successor of a word W: I could iterate each word X of the list of words and see if there is only one letter different between W and X. Or I can replace each of the 5 letters of W by one of the 25 possible letters, and see if the result is in the list of words.

1st one implies 5757 candidates 2nd 5×25=125. One could argue that verifying the candidates is just the matter of 5 letter comparison in 1st case (verifying that only 1 letter is different), while in 2nd case it implies verifying that the word is in the list of 5757 words. So, that in both case we have 5757×5 operations to do. But I trust that set in operator is faster than a pure python 5757 iteration loop (I haven't timed it to be sure, tho).

Optimisation if the challenge could be longer.

There are 7 questions in the challenge. So it is not worth taking too much time building a structure.

But if we wanted to build zillions of word ladder from the same dictionnary, it could be worth building once for all a successor graph (in the form of an adjacency matrix, or using dedicated modules such as networkx), and then just call a (probably very fast BFS algorithm) directly on those graph.

Each call should be fast (again, I haven't timed it), because the graph is probably not very dense (there are way less than 5756, or even 125 successors per word on average).

Even more, we could compute once for all a word/word connection matrix, using a modified Roy-Warshall algorithm (modified to keep paths). It cost a O(n³) times at first, but then it is instantaneous to reply to any challenge.

But well, I am mentioning here ideas that I haven't applied