I used python.
My first attempt was recursively listing all words that are off by 1 letter from every word found so far. For example, offby1('stone') -> ['atone', 'shone', 'scone', 'store', 'stove', 'stole', 'stoke', 'stoae', 'stony']. Check if 'money' is in those and if not, make a list of all offby1(word) for every word in the candidates (excluding from the output any word found so far, to prevent longer paths to the same word and cycles; I made a list called exclude; to use it across functions I put everything in a class). This recursive technique took far too long to run.
I printed the paths as they were being created to find why. It would take a path as far as possible until the dictionary exhausted (['bread', 'dread', 'dream', 'cream', 'creak', 'wreak', 'wreck', ...]). I'd much rather it check paths of length 1, then paths of length 2, and so on, not just for speed but also so that when it returns a solution it's guaranteed to be the shortest path.
I found a way to implement this: list every path of a given length (starting with [[w1],]), then use offby1() on the final word in each path to list all paths with one more word (and return early if target found). Unfortunately, this stores increasingly long lists; and when there is no valid path, such as with apple -> zebra, it could still take very long checking all paths possible from apple. Altogether it took my laptop 19.5 minutes to run. Definitely not the best it could be.

class Ladder:
    def __init__(self, w1, w2, fname='sgb-words.txt'):
        with open(fname) as f:
            self.d=f.read().split()
        
        if len(w1)!=5 or len(w2)!=5:
            raise Exception("dict only has 5-letter words")
            
        self.paths=[[w1]]
        self.exclude=[w1]
        self.ws=self.d.copy()
        
        #check each count of letter swaps for w2 until there are no new words found
        self.path = self.path_to(w2)
    
    def offby1(self, word): #list all words that match word except one letter
        self.ws=[w for w in self.ws if w not in self.exclude]
        off1=[w for i in range(len(word)) 
              for w in self.ws if w[:i]==word[:i] and w[i+1:]==word[i+1:]]
        return off1
    
    def path_to(self, w):
        if self.paths==[]: 
            return None
        
        paths = []
        for path in self.paths:
            for word in self.offby1(path[-1]):
                if word==w:
                    return path+[w]
                
                self.exclude += [word]
                paths += [path+[word]]
        self.paths = paths
        return self.path_to(w)


def main():
    pairs=[['stone', 'money'], ['bread', 'crumb'], ['smile', 'giant'], 
           ['apple', 'zebra'], ['other', 'night'], ['bread', 'blood'], 
           ['black', 'white']]
    for w1,w2 in pairs:
        p=Ladder(w1,w2).path
        if p is not None:
            print(p,len(p))
        else: 
            print(f"No path from {w1} to {w2}")

main()

Output:

['stone', 'shone', 'shine', 'chine', 'chins', 'coins', 'corns', 'cores', 'cones', 'coney', 'money'] 11
['bread', 'tread', 'triad', 'tried', 'pried', 'pries', 'prims', 'primp', 'crimp', 'crump', 'crumb'] 11
['smile', 'stile', 'stilt', 'stint', 'saint', 'taint', 'taunt', 'gaunt', 'grunt', 'grant', 'giant'] 11
No path from apple to zebra
['other', 'otter', 'outer', 'cuter', 'cater', 'rater', 'raver', 'river', 'rivet', 'revet', 'reset', 'beset', 'beget', 'begot', 'bigot', 'bight', 'night'] 17
['bread', 'broad', 'brood', 'blood'] 4
['black', 'clack', 'click', 'chick', 'chink', 'chine', 'whine', 'white'] 8

Solution

[stone, money] 
length = 11
stone -> shone -> shine -> chine -> chins -> coins -> corns -> cores -> cones -> coney -> money

[bread, crumb] 
length = 11
bread -> tread -> treed -> tried -> pried -> pries -> prims -> primp -> crimp -> crump -> crumb

[smile, giant] 
length = 11
smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant

[apple, zebra] 
No ladder found

[other, night] 
length = 17
other -> otter -> outer -> muter -> muser -> miser -> riser -> river -> rivet -> revet -> reset -> beset -> besot -> begot -> bigot -> bight -> night

[bread, blood] 
length = 4
bread -> broad -> brood -> blood

[black, white] 
length = 8
black -> brack -> brace -> trace -> trice -> trite -> write -> white

Code

use petgraph::{graph::{UnGraph, NodeIndex}, visit::{Bfs}}; // 0.8.2
use std::iter::zip;

const DICTIONARY: &[&str] = &[
    "which",
    /* ... the rest of the words ... */
    "pupal"
];
const TESTS: &[(&str, &str)] = &[
    ("stone", "money"),
    /* ... the rest of the tests ... */
    ("black", "white")
];

fn is_neighbor(a: &str, b: &str) -> bool {
    let mut found_diff = false;
    for (char_a, char_b) in zip(a.chars(), b.chars()) {
        if char_a != char_b {
            if found_diff {
                // more than one char is different, it's not a neighbor
                return false;
            } else {
                // mark that one char is different
                found_diff = true;
            }
        }
    }
    found_diff
}

fn main() {
    let mut graph = UnGraph::<&str, ()>::new_undirected();
    // add all the words to the graph O(n)
    for word in DICTIONARY {
        graph.add_node(word);
    }
    // For each word, find it's neighbors O(n^2)
    let mut skip = 0;
    for index_a in graph.node_indices() {
        skip += 1;
        for index_b in graph.node_indices().skip(skip) {
            if is_neighbor(graph[index_a], graph[index_b]) {
                graph.add_edge(index_a, index_b, ());
            }
        }
    }
    
    // At this point, we could store the graph in a binary format, and load that
    // in a different program just for finding word ladders. i.e:
    //
    // let dot = Dot::new(&graph);
    //
    // However, for simplicity and completeness, we'll just use the graph
    // immediately for the test cases
    
    // use a breadth first search from the source O(v+e).
    // The first time we reach the target, that is a shortest path
    
    for (source, target) in TESTS {
        let mut graph = graph.map(
            |_, word| (word, None as Option<NodeIndex>),
            |_, _| ()
        );
        
        let source_index = graph.node_indices().find(
            |index| graph[*index].0 == source
        ).unwrap();
        
        let mut bfs = Bfs::new(&graph, source_index);
        let current_node = 'find_target: loop {
            if let Some(node_index) = bfs.next(&graph) {
                let mut neighbors = graph.neighbors(node_index).detach();
                while let Some(neighbor_index) = neighbors.next_node(&graph) {
                    // source index needs to remain unmodified
                    if neighbor_index != source_index {
                        if let None = graph[neighbor_index].1 {
                            graph[neighbor_index].1 = Some(node_index);
                        }
                        // no harm in continuing, but more efficient to stop once we've
                        // found it
                        if graph[neighbor_index].0 == target {
                            break 'find_target Some(graph[neighbor_index]);
                        }
                    }
                }
            } else {
                break 'find_target None;
            }
        };

        // output the result
        println!("[{}, {}] ", source, target);
        
        if let Some(mut current_node) = current_node {
            let mut word_ladder = format!("{}", current_node.0);
            let mut length = 1;
            while let Some(parent_index) = current_node.1 {
                length += 1;
                current_node = graph[parent_index];
                word_ladder = format!("{} -> {}", current_node.0, word_ladder);
            }
            println!("length = {}", length);
            println!("{}", word_ladder)
        } else {
            println!("No ladder found");
        }
        println!();
    }
}

Playground link

Lessons

I learned a lot about Rust, in particular some better understanding of the borrowing system and ownership, as well as the petgraph library, which I'd never used before. Overall, it was a fun coding challenge and an application of algorithm problems that I enjoy solving!

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

from collections import deque
from typing import List

# Using a BFS approach to find the shortest transformation sequence
def word_ladder(start_word: str, end_word: str, word_list: List[str]) -> List[str]:
    """ Find the shortest word ladder from start_word to end_word using words from word_list.
    """
    word_set = set(word_list)
    ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

    # Early exit if the start or the end word is not in the dictionary
    if not {start_word, end_word}.issubset(word_set):
        return []

    # Initialize BFS queue and visited set
    queue   = deque([[start_word]])
    visited = {start_word}  # We have seen the start word obviously

    # Perform search...
    while queue:
        path         = queue.popleft()
        current_word = path[-1]

        # Successful ladder found
        if current_word == end_word:
            return path

        for i in range(len(current_word)):
            for c in (set(ALPHABET) - {current_word[i]}):  # Replace by any other letter from the alphabet

                # Generate the next step/word (candidate) by changing one letter
                next_word = current_word[:i] + c + current_word[i+1:]

                # Only consider valid words and avoid cycles
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append(path + [next_word])

    return []  # No ladder found


# Load the dictionary of five-letter words
with open('sgb-words.txt', 'r') as f:
    word_list = [line.strip() for line in f.readlines()]

# Challenge test cases
test_pairs = [
    ('stone', 'money'),
    ('bread', 'crumb'),
    ('smile', 'giant'),
    ('apple', 'zebra'),
    ('other', 'night'),
    ('bread', 'blood'),
    ('black', 'white')
]
for start, end in test_pairs:
    ladder = word_ladder(start, end, word_list)
    if ladder:
        print(f"Ladder from '{start}' to '{end}':")
        for i, word in enumerate(ladder):
            print(f"╬═╬ {word}")
        print(f"({len(ladder)} steps)")
    else:
        print(f"No ladder found from '{start}' to '{end}'")

    print()  # newline only

Output:

Ladder from 'stone' to 'money':
╬═╬ stone
╬═╬ shone
╬═╬ shine
╬═╬ chine
╬═╬ chins
╬═╬ coins
╬═╬ corns
╬═╬ cores
╬═╬ cones
╬═╬ coney
╬═╬ money
(11 steps)

Ladder from 'bread' to 'crumb':
╬═╬ bread
╬═╬ tread
╬═╬ triad
╬═╬ tried
╬═╬ pried
╬═╬ pries
╬═╬ prims
╬═╬ primp
╬═╬ crimp
╬═╬ crump
╬═╬ crumb
(11 steps)

Ladder from 'smile' to 'giant':
╬═╬ smile
╬═╬ stile
╬═╬ stilt
╬═╬ stint
╬═╬ saint
╬═╬ taint
╬═╬ taunt
╬═╬ gaunt
╬═╬ grunt
╬═╬ grant
╬═╬ giant
(11 steps)

No ladder found from 'apple' to 'zebra'

Ladder from 'other' to 'night':
╬═╬ other
╬═╬ otter
╬═╬ outer
╬═╬ cuter
╬═╬ cater
╬═╬ rater
╬═╬ raver
╬═╬ river
╬═╬ rivet
╬═╬ revet
╬═╬ reset
╬═╬ beset
╬═╬ beget
╬═╬ begot
╬═╬ bigot
╬═╬ bight
╬═╬ night
(17 steps)

Ladder from 'bread' to 'blood':
╬═╬ bread
╬═╬ broad
╬═╬ brood
╬═╬ blood
(4 steps)

Ladder from 'black' to 'white':
╬═╬ black
╬═╬ clack
╬═╬ click
╬═╬ chick
╬═╬ chink
╬═╬ chine
╬═╬ whine
╬═╬ white
(8 steps)

Thanks for the nice challenge! Interesting how long some paths are and that you can turn stone into money, make a giant smile, but an apple will never become a zebra.

First, start by opening the list of words:

words = open('sgb-words.txt', 'r')
words = set(map(lambda w:w.strip(), words.readlines()))

Then define a few functions:

from itertools import product

def differ_by_one(s1, s2):
    '''Checks that strings differ by one letter exactly'''
    ok = False # no difference yet
    for c1, c2 in zip(s1,s2):
        if c1 != c2: # if difference
            if not ok: # first detected difference
                ok = True
            else : # second detected difference : out
                return False
    return ok

def get_following(to_test, tested, other_side):
    '''Gets possible children words, given parent words, excluding already found words'''
    restr = words.difference(tested.keys()) # already found words, this side of the search 
    restr = restr.difference(other_side.values()) # already found words, the other side

    out = {}
    for w1, w2 in product(restr, to_test.keys()): # cartesian product
        if differ_by_one(w1, w2):
            out[w1] = w2

    if len(out) == 0:
        return None, tested  # if there is no following word, it means no ladder is possible

    tested.update(out) # update the dictionary of already found words
    return out, tested

def word_ladder(word1, word2) :
    '''Full ladder build. We start the search from both ends, until we find a common link'''
    # init both ladder sides
    reg1, reg2 = {word1: None}, {word2: None} # regsN contains already searched words
    new1, new2 = reg1, reg2 # newN contains words to be searched on next iteration

    # do the actual search
    # alternating on the shortest side to test allows to limit tree expansion and computing time
    while not reg1.keys() & reg2.keys() :
        if len(new1) <= len(new2) :
            new1, reg1 = get_following(new1, reg1, reg2)
        else:
            new2, reg2 = get_following(new2, reg2, reg1)

        if new1 is None or new2 is None :
            return None
    # get one of the possible middle links, and follow it up and down
    middle = list(reg1.keys() & reg2.keys())[0]
    ret, sol1, sol2 = [middle], middle, middle
    while sol1 != word1 : # up
        sol1 = reg1[sol1]
        ret.insert(0, sol1)
    while sol2 != word2: # down
        sol2 = reg2[sol2]
        ret.append(sol2)        
    return ret

I don't know how much we're supposed to explain, but the basic idea is to iterate in a parent/child way. We start from the given words, search for all possible children, meaning all words with a one-letter difference; then these words become the parents for the next iteration. Results are saved in a dictionary with child: parent structure. When we get to the end, we just have to call the dictionary until we're back at the start.

The computing time is proportional to the number of parents we test at each iteration, which is linked to (but not necessarily proportional to) the iteration step. To limit the computing time, I've found that starting from both ends is a good idea, and better yet, we can choose what side of the tree we expand, based on the minimal number of parents we have to search for.

Finally, we just have to apply our function to the test pairs:

import time

test_set = [
    ['stone', 'money'],
    ['bread', 'crumb'],
    ['smile', 'giant'],
    ['apple', 'zebra'],
    ['other', 'night'],
    ['bread', 'blood'],
    ['black', 'white'],
]

for pair in test_set :
    start = time.time()
    wl = word_ladder(*pair)
    computing_time = time.time() - start
    if wl :
        print('For pair ({}), the shortest word ladder is {} words long, for example:'.format(pair, len(wl)))
        print(wl)
    else :
        print('For pair ({}), no word ladder seems possible.'.format(pair))
    print('Computed in: {}s'.format(round(computing_time, 3)))

Which yields, on my machine:

For pair (['stone', 'money']), the shortest word ladder is 11 words long, for example:
['stone', 'shone', 'shine', 'chine', 'chins', 'coins', 'corns', 'cores', 'cones', 'coney', 'money']
Computed in: 0.68s

For pair (['bread', 'crumb']), the shortest word ladder is 11 words long, for example:
['bread', 'tread', 'treed', 'trees', 'tress', 'cress', 'crass', 'crams', 'cramp', 'crump', 'crumb']
Computed in: 0.21s

For pair (['smile', 'giant']), the shortest word ladder is 11 words long, for example:
['smile', 'stile', 'stilt', 'stint', 'saint', 'taint', 'taunt', 'gaunt', 'grunt', 'grant', 'giant']
Computed in: 0.217s

For pair (['apple', 'zebra']), no word ladder seems possible.
Computed in: 0.003s

For pair (['other', 'night']), the shortest word ladder is 17 words long, for example:
['other', 'otter', 'outer', 'cuter', 'curer', 'cures', 'curls', 'burls', 'burns', 'burnt', 'buret', 'beret', 'beget', 'begot', 'bigot', 'bight', 'night']
Computed in: 0.183s

For pair (['bread', 'blood']), the shortest word ladder is 4 words long, for example:
['bread', 'broad', 'brood', 'blood']
Computed in: 0.011s

For pair (['black', 'white']), the shortest word ladder is 8 words long, for example:
['black', 'brack', 'brace', 'trace', 'trice', 'trite', 'write', 'white']
Computed in: 0.161s

What I found interesting is that the computing time is not necessarily proportional to the length of the ladder. The ['other', 'night'] pair has the longest ladder, but is quite faster than the ['stone', 'money'] pair. That is linked to the fact that the intermediate words have less children. I wonder what it would yield in other languages.

1. Ladders plus Lengths:

From money to bones: Ladder: money->honey->hones->bones : Length: 4

From stone to money: Ladder: stone->shone->shine->shins->chins->coins->corns->cores->cones->coney->money : Length: 11

From bread to crumb: Ladder: bread->breed->freed->fried->fries->pries->prims->primp->crimp->crump->crumb : Length: 11

From smile to giant: Ladder: smile->stile->stilt->stint->saint->taint->taunt->gaunt->grunt->grant->giant : Length: 11

From apple to zebra: No Path found

From other to night: Ladder: other->otter->outer->cuter->cater->rater->raver->river->rivet->revet->reset->beset->beget->begot->bigot->bight->night : Length: 17

From bread to blood: Ladder: bread->broad->brood->blood : Length: 4

From black to white: Ladder: black->blank->blink->clink->chink->chine->whine->white : Length: 8

2.The code

from itertools import product

class Node:
    def __init__(self, name):
        self._name = name
        self._successors = []

with open("sgb-words.txt", "r") as f:
    def provideLine():
        l = f.readline()
        while (l is not None and l != ""):
            yield l.strip()
            l = f.readline()
    nodes = [Node(n) for n in provideLine()]

def isNeighbor(nodeA: Node, nodeB: Node):
    diffs = 0
    for (left, right) in zip(nodeA._name, nodeB._name):
        if (left != right):
            diffs += 1
            if diffs > 1:
                return False
    return True
    
# connect nodes
i = 0
while i < len(nodes):
    j = i
    left = nodes[i]
    while j < len(nodes):
        if i == j:
            j += 1
            continue
        right = nodes[j]
        if isNeighbor(left, right):
            left._successors.append(right)
            right._successors.append(left)
        j += 1
    i += 1
        
def stringifyPath(p):
    x = [p[1]._name]
    while isinstance(p[0], Node) is False:
        p = p[0]
        x.append(p[1]._name)
    x.append(p[0]._name)
    x.reverse()
    pathString = "->".join(x)
    return f"Ladder: {pathString} : Length: {len(x)}"

def findPath(start: Node, target: str):
    visited = [start._name]
    to_visit = [(start, n) for n in start._successors]
    while len(to_visit) > 0:
        current = to_visit[0]
        if (current[1]._name == target):
            return stringifyPath(current)
        visited.append(current[1]._name)
        for succ in current[1]._successors:
            if succ._name not in visited:
                visited.append(succ._name)
                to_visit.append((current, succ))
        
        to_visit.pop(0)
        
def find(startName: str, targetName: str):
    startNode = [n for n in nodes if n._name == startName][0]
    path = findPath(startNode, targetName)
    if path is None:
        return f"From {startName} to {targetName}: No Path found"
    return f"From {startName} to {targetName}: {path}"
    
print(find('money', 'bones'))
print(find('stone', 'money'))
print(find('bread', 'crumb'))
print(find('smile', 'giant'))
print(find('apple', 'zebra'))
print(find('other', 'night'))
print(find('bread', 'blood'))
print(find('black', 'white'))

Answers

1. ['stone', 'money'], Length = 11: stone -> shone -> shine -> chine -> chins -> coins -> corns -> cores -> cones -> coney -> money.

2. ['bread', 'crumb'], Length = 11: bread -> tread -> triad -> tried -> pried -> pries -> prims -> primp -> crimp -> crump -> crumb.

3. ['smile', 'giant'], Length = 11: smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant.

4. ['apple', 'zebra'], Length = 0: Not Possible.

5. ['other', 'night'], Length = 17: other -> otter -> outer -> cuter -> cater -> rater -> raver -> river -> rivet -> revet -> reset -> beset -> beget -> begot -> bigot -> bight -> night.

6. ['bread', 'blood'], Length = 4: bread -> broad -> brood -> blood.

7. ['black', 'white'], Length = 8: black -> clack -> click -> chick -> chink -> chine -> whine -> white.

Code

<?php

declare(strict_types=1);

class Solution
{
    private readonly array $wordLookUp;
    private readonly array $alphabet;

    public function __construct(array $words)
    {
        $this->wordLookUp = array_flip($words);
        $this->alphabet = range('a', 'z');
    }

    public function solve(string $source, string $target): WordLadder
    {
        $discovered = [
            $source => true,
        ];

        $currentLevel = 0;
        $levels = [
            $currentLevel => [$source => false],
        ];
        $isNotProcessed = static fn(bool $v): bool => $v === false;

        $wordAncestry = [
            $source => '',
        ];

        while (array_any($levels[$currentLevel], $isNotProcessed)) {
            $currentLevel++;
            $levels[$currentLevel] = [];

            $previousLevel = $currentLevel - 1;

            foreach ($levels[$previousLevel] as $word => $_) {
                for ($i = 0; $i < strlen($word); $i++) {
                    foreach ($this->alphabet as $c) {
                        $newWord = $word;

                        if ($newWord[$i] === $c) continue;

                        $newWord[$i] = $c;

                        $isExistingWord = array_key_exists($newWord, $this->wordLookUp);
                        if (!$isExistingWord) continue;

                        $isAlreadyDiscoveredWord = array_key_exists($newWord, $discovered);
                        if ($isAlreadyDiscoveredWord) continue;

                        $levels[$currentLevel][$newWord] = false;
                        $discovered[$newWord] = true;
                        $wordAncestry[$newWord] = $word;

                        if ($newWord === $target) break (4);
                    }
                }

                $levels[$previousLevel][$word] = true;
            }
        }

        return new WordLadder($source, $target, $wordAncestry);
    }
}

class WordLadder implements Stringable
{
    private readonly array $ladder;

    public function __construct(
        public readonly string $source,
        public readonly string $target,
        array $wordAncestry
    ) {
        $this->ladder = $this->getLadder($wordAncestry);
    }

    private function getLadder(array $wordAncestry): array
    {
        if (!array_key_exists($this->target, $wordAncestry)) return [];

        $wordLadderStack = [];
        $current = $this->target;

        do {
            $wordLadderStack[] = $current;

            $parent = $wordAncestry[$current];

            $current = $parent;
        } while ($current !== '');

        return array_reverse($wordLadderStack);
    }

    public function length(): int
    {
        return count($this->ladder);
    }

    public function __toString(): string
    {
        $result = $this->length() > 0
            ? implode(' -> ', $this->ladder)
            : "Not Possible";

        return sprintf("%s.", $result);
    }
}

$words = explode(
    PHP_EOL,
    file_get_contents(__DIR__ . DIRECTORY_SEPARATOR . 'sgb-words.txt'),
);

array_pop($words);

$inputs = [
    ['stone', 'money'],
    ['bread', 'crumb'],
    ['smile', 'giant'],
    ['apple', 'zebra'],
    ['other', 'night'],
    ['bread', 'blood'],
    ['black', 'white'],
];

$solution = new Solution($words);
$ladders = array_map(
    static fn(array $input): WordLadder => $solution->solve(...$input),
    $inputs
);

foreach ($ladders as $ladder) {
    echo sprintf(
        "['%s', '%s'], Length = %s: %s",
        $ladder->source,
        $ladder->target,
        $ladder->length(),
        $ladder,
    ) . PHP_EOL;
}

exit(0);

The Code

from collections import defaultdict, deque

class WordLadder:
    
    def build_graph(self, filename):
        self.graph = defaultdict(list)
        models = defaultdict(list)
        with open(filename, 'r') as thesaurus:
            for word in thesaurus:
                word = word.strip()
                for i in range(5):
                    letter = word[i]
                    model = f'{word[:i]}_{word[i+1:]}'
                    if model in models:
                        for prev_letter in models[model]:
                            prev_word = model.replace('_', prev_letter)
                            self.graph[prev_word].append(word)
                            self.graph[word].append(prev_word)
                    models[model].append(letter)

    def bfs_bidi(self, source, dest):
        current_layers = [deque(), deque()]
        next_layers = [deque(), deque()]
        parents = [{}, {}]
        self.path = []
        current_layers[0].append(source)
        current_layers[1].append(dest)
        parents[0][source] = None
        parents[1][dest] = None
        while current_layers[0] and current_layers[1]:
            side = 1 if len(current_layers[1]) < len(current_layers[0]) else 0
            other = side ^ 1
            current = current_layers[side].popleft()
            if current in parents[other]:
                self.path = self.rebuild_path(source, current, parents[0]) + self.rebuild_path(dest, current, parents[1], reverse = False)[1:]
                break
            for neighbour in self.graph[current]:
                if neighbour not in parents[side]:
                    next_layers[side].append(neighbour)
                    parents[side][neighbour] = current
            if not current_layers[side]:
                current_layers[side], next_layers[side] = next_layers[side], current_layers[side]

    def rebuild_path(self, source, dest, parents, reverse = True):        
        path = []
        current = dest
        while current:
            path.append(current)
            current = parents[current]
        if reverse:
            path.reverse()
        return path

The output

going from stone to money requires 11 steps: stone => shone => shine => shins => chins => coins => corns => cores => cones => coney => money going from bread to crumb requires 11 steps: bread => breed => treed => tried => tries => trims => trams => tramp => trump => crump => crumb going from smile to giant requires 11 steps: smile => stile => stilt => stint => saint => taint => taunt => gaunt => grunt => grant => giant *** no paths found from apple to zebra *** going from other to night requires 17 steps: other => otter => outer => muter => miter => liter => liver => river => rivet => revet => reset => beset => beget => begot => bigot => bight => night going from bread to blood requires 4 steps: bread => broad => brood => blood going from black to white requires 8 steps: black => blank => blink => clink => chink => chine => whine => white

Some notes

Basically the task is, build a graph, and traverse it from source to destination.

The second part is done with a classic bidirectional breadth-first search; the only quirk here being that we work always on the shortest queue instead of simply alternating between the two.

The first part, building the graph, is perhaps more interesting. I didn't want to check each word against all the previous ones to find the possible arcs, so I followed another path:

• for each word, compute five "models", replacing each of the letters with an underscore and tracking the replaced letter. e.g. "money" will generate {"oney": ["m"], "m_ney": ["o"], ... "mone": ["y"]}
• if a model already exists in the dictionary, then link the current word to all those which have already touched that model. When e.g. "honey" comes, we just rebuild the previous word(s) from the "_oney" dict entry (in this case "money"), link the two, and of course add the letter from the new word ("h") to the entry.

• Length of word ladders for each pairs in test set:

[stone, money] - 6

[bread, crumb] - 5

[smile, giant] - 6

[apple, zebra] - 6

[other, night] - 6

[bread, blood] - 4

[black, white] - 6

• Word Ladders

1. stone -> mtone -> moone -> monne -> monee -> money

2. bread -> cread -> cruad -> crumd -> crumb

3. smile -> gmile -> giile -> giale -> giane -> giant

4. apple -> zpple -> zeple -> zeble -> zebre -> zebra

5. other -> nther -> niher -> niger -> nighr -> night

6. bread -> blead -> bload -> blood

7. black -> wlack -> whack -> whick -> whitk ->white

• Code

#include <iostream>
using namespace std;

void word_ladder(string s1, string s2){
    int i=0;
    int count=0;
    cout<<s1<<"\n";
    for(i; i<s1.length(); i++){
        if(s1[i]==s2[i]){
            continue;
        }
        else{
            s1[i]=s2[i];
            cout<<s1<<"\n";
            count++;
        }
    }
    cout<<"Length: "<<count+1<<"\n";
}

int main() {
    string a[] = {"stone", "bread", "smile", "apple", "other", "bread", "black"};
    string b[] = {"money", "crumb", "giant", "zebra", "night", "blood", "white"};
    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++){
        word_ladder(a[i], b[i]);
        cout<<"====================="<<"\n\n";
    }
    return 0;
}

The challenge didn't specify if shuffling of letters was allowed, so I implemented both approach.

My approach is based of Dijkstra's algorithm. I consider words with only 1 letter difference as neighbor in a graph with a distance of 1.

I implemented my code with the help of https://www.datacamp.com/fr/tutorial/dijkstra-algorithm-in-python

My code is available on github at https://github.com/genevieve-le-houx/SO_challenge_8_word_ladder

My results:

--- No shuffling ---
The ladder has a length of 11:  stone -> shone -> shine -> chine -> chins -> coins -> corns -> cores -> cones -> coney -> money
The ladder has a length of 11:  bread -> tread -> treed -> tried -> tries -> trims -> trams -> tramp -> trump -> crump -> crumb
The ladder has a length of 11:  smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant
There is no solution to the pair ('apple', 'zebra')
The ladder has a length of 17:  other -> otter -> outer -> muter -> mater -> rater -> raver -> ravel -> revel -> revet -> reset -> beset -> besot -> begot -> bigot -> bight -> night
The ladder has a length of 4:  bread -> broad -> brood -> blood
The ladder has a length of 8:  black -> clack -> clank -> clink -> chink -> chine -> whine -> white
 
--- Shuffling ---
The ladder has a length of 3:  stone -> monte -> money
The ladder has a length of 4:  bread -> bream -> rumba -> crumb
The ladder has a length of 5:  smile -> limns -> lings -> algin -> giant
The ladder has a length of 4:  apple -> paler -> blear -> zebra
The ladder has a length of 4:  other -> goeth -> ghoti -> night
The ladder has a length of 4:  bread -> abled -> lobed -> blood
The ladder has a length of 6:  black -> aleck -> leach -> chile -> lieth -> white

My code is

# https://www.datacamp.com/fr/tutorial/dijkstra-algorithm-in-python

from collections import Counter
from heapq import heapify, heappop, heappush
from typing import Tuple, List, Dict
from pathlib import Path

from tqdm import tqdm
import numpy as np


class WordsGraph:
    """
    Graph for the Dijkstra's algorithm
    Each weight is implicitly 1

    A word is a neighbor if the difference between them is only one letter.
    My solution take into account if we allow shuffling or not of letters.
    Building the graph is slow, so we can save the graph as a numpy matrix to reuse it
    """
    def __init__(self, words: List[str], shuffling: bool = False):
        self.words = words

        filename = "words_neighborhs_shuffle.npy" if shuffling else "words_neighborhs_no_shuffle.npy"
        filepath = Path(filename)

        if filepath.exists():
            self.words_neighbors = np.load(filepath)

        else:
            words_str = [np.array([x for x in word]) for word in words]

            self.words_neighbors = np.zeros((len(words), len(words)), dtype=int)

            print("Building graph")
            for i in tqdm(range(len(words))):
                for j in range(i+1, len(words)):
                    if i == j:
                        continue

                    self.words_neighbors[i][j] = self.words_is_neighbors(words_str[i], words_str[j], shuffling)

            self.words_neighbors = self.words_neighbors | self.words_neighbors.T

            np.save(filepath, self.words_neighbors)

    def get_words_no_neighborhs(self) -> List[str]:
        words_no_neighbors = []

        for word in self.words:
            word_neighbors = self.words_neighbors[self.words.index(word), :]

            if not np.any(word_neighbors):
                words_no_neighbors.append(word)

        return words_no_neighbors


    def shortest_distance(self, source: str) -> Tuple[Dict[str, float | int], Dict[str, str | None]]:
        distances = {word: float("inf") for word in self.words}
        distances[source] = 0

        pq = [(0, source)]
        heapify(pq)
        visited = set()

        while pq:
            current_distance, current_word = heappop(pq)

            if current_word in visited:
                continue

            visited.add(current_word)

            i_current_word = self.words.index(current_word)

            for i_neighbors in np.argwhere(self.words_neighbors[i_current_word, :]).flatten():
                neighbor_word = self.words[i_neighbors]

                tentative_distance = current_distance + 1
                if tentative_distance < distances[neighbor_word]:
                    distances[neighbor_word] = tentative_distance
                    heappush(pq, (tentative_distance, neighbor_word))

        predecessors: Dict[str, str | None] = {word: None for word in self.words}
        for word, distance in distances.items():
            i_current_word = self.words.index(word)

            for i_neighbors in np.argwhere(self.words_neighbors[i_current_word, :]).flatten():
                neighbor_word = self.words[i_neighbors]
                if distances[neighbor_word] == distance + 1:
                    predecessors[neighbor_word] = word

        return distances, predecessors


    def shortest_path(self, source: str, target: str) -> Tuple[int, List[str]]:
        """
        If there is no path, return -1, []
        :param source:
        :param target:
        :return:
        """
        _, predecessors = self.shortest_distance(source)

        path = []
        current_node = target

        while current_node:
            path.append(current_node)
            current_node = predecessors[current_node]
            if current_node is None:
                if path[-1] != source:
                    return -1, []

        path.reverse()

        return len(path), path


    @staticmethod
    def words_is_neighbors(a: np.ndarray, b: np.ndarray, shuffling: bool = False) -> bool:
        if shuffling:
            a_counter = dict(Counter(a).items())
            b_counter = dict(Counter(b).items())

            number_differences = 0
            for letter, count in a_counter.items():
                if letter in b_counter:
                    number_differences += abs(count - b_counter[letter])
                    b_counter.pop(letter)

                else:
                    number_differences += count

            # Letters left are the differences, but if there are more we add to the difference
            number_differences += abs(sum(b_counter.values()) - number_differences)

            return number_differences == 1
        else:
            return np.sum(a != b) == 1


def main():
    with open("sgb-words.txt", "r") as f:
        list_valid_words = [x.strip() for x in f.readlines()]

    input_pairs = [
        ("stone", "money"),
        ("bread", "crumb"),
        ("smile", "giant"),
        ("apple", "zebra"),
        ("other", "night"),
        ("bread", "blood"),
        ("black", "white")
    ]

    sufflings = [False, True]

    for shuffling in sufflings:
        text = "Shuffling" if shuffling else "No shuffling"
        print(f"--- {text} ---")

        words_graph = WordsGraph(list_valid_words, shuffling)

        words_no_neighbors = words_graph.get_words_no_neighborhs()
        print(f"Words without neighbors are: {words_no_neighbors}")

        for pair in input_pairs:
            ladder_length, ladder = words_graph.shortest_path(*pair)

            if ladder_length != -1:
                print(f"The ladder has a length of {ladder_length}: ", " -> ".join(ladder))
            else:
                print(f"There is no solution to the pair {pair}")

        print(" ")


if __name__ == '__main__':
    main()

Results

• Pair: [stone, money]

  • Ladder Length: 11

Word Ladders (2)

'stone' -\> 'shone' -\> 'shine' -\> 'chine' -\> 'chins' -\> 'coins' -\> 'corns' -\> 'cores' -\> 'cones' -\> 'coney' -\> 'money'

'stone' -\> 'shone' -\> 'shine' -\> 'shins' -\> 'chins' -\> 'coins' -\> 'corns' -\> 'cores' -\> 'cones' -\> 'coney' -\> 'money'

• Pair: [bread, crumb]

  • Ladder Length: 11

Word Ladders (46)

'bread' -\> 'breed' -\> 'bleed' -\> 'blued' -\> 'blues' -\> 'slues' -\> 'slums' -\> 'slump' -\> 'clump' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'bleed' -\> 'blued' -\> 'slued' -\> 'slues' -\> 'slums' -\> 'slump' -\> 'clump' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'trews' -\> 'crews' -\> 'craws' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'trees' -\> 'tress' -\> 'cress' -\> 'crass' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'pried' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'creed' -\> 'cried' -\> 'pried' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'creed' -\> 'cried' -\> 'cries' -\> 'cribs' -\> 'crabs' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'creed' -\> 'cried' -\> 'cries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'freed' -\> 'frees' -\> 'fries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'freed' -\> 'fried' -\> 'fries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'breed' -\> 'freed' -\> 'fried' -\> 'pried' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'trews' -\> 'crews' -\> 'craws' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'treys' -\> 'trays' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tries' -\> 'trims' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'trees' -\> 'tress' -\> 'cress' -\> 'crass' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'treed' -\> 'tried' -\> 'pried' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'tries' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'crams' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'trump' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'trams' -\> 'tramp' -\> 'cramp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'tries' -\> 'trims' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

'bread' -\> 'tread' -\> 'triad' -\> 'tried' -\> 'pried' -\> 'pries' -\> 'prims' -\> 'primp' -\> 'crimp' -\> 'crump' -\> 'crumb'

• Pair: [smile, giant]

  • Ladder Length: 11

Word Ladders (1)

'smile' -\> 'stile' -\> 'stilt' -\> 'stint' -\> 'saint' -\> 'taint' -\> 'taunt' -\> 'gaunt' -\> 'grunt' -\> 'grant' -\> 'giant'

• Pair: [apple, zebra]

  • Word Ladder not possible.

• Pair: [other, night]

  • Ladder Length: 17

Word Ladders (21)

'other' -\> 'otter' -\> 'outer' -\> 'cuter' -\> 'cater' -\> 'rater' -\> 'raver' -\> 'ravel' -\> 'revel' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'cuter' -\> 'cater' -\> 'rater' -\> 'raver' -\> 'ravel' -\> 'revel' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'cuter' -\> 'cater' -\> 'rater' -\> 'raver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'cuter' -\> 'cater' -\> 'rater' -\> 'raver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'cuter' -\> 'curer' -\> 'cures' -\> 'curls' -\> 'burls' -\> 'burns' -\> 'burnt' -\> 'buret' -\> 'beret' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'muser' -\> 'miser' -\> 'riser' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'muser' -\> 'miser' -\> 'riser' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mater' -\> 'rater' -\> 'raver' -\> 'ravel' -\> 'revel' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mater' -\> 'rater' -\> 'raver' -\> 'ravel' -\> 'revel' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mater' -\> 'rater' -\> 'raver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mater' -\> 'rater' -\> 'raver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'mimer' -\> 'rimer' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'mimer' -\> 'rimer' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'liter' -\> 'liver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'liter' -\> 'liver' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'miser' -\> 'riser' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'miser' -\> 'riser' -\> 'river' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'mites' -\> 'rites' -\> 'rives' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'miter' -\> 'mites' -\> 'rites' -\> 'rives' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mutes' -\> 'mites' -\> 'rites' -\> 'rives' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'beget' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

'other' -\> 'otter' -\> 'outer' -\> 'muter' -\> 'mutes' -\> 'mites' -\> 'rites' -\> 'rives' -\> 'rivet' -\> 'revet' -\> 'reset' -\> 'beset' -\> 'besot' -\> 'begot' -\> 'bigot' -\> 'bight' -\> 'night'

• Pair: [bread, blood]

  • Ladder Length: 4

Word Ladders (1)

'bread' -\> 'broad' -\> 'brood' -\> 'blood'

• Pair: [black, white]

  • Ladder Length: 8

Word Ladders (9)

'black' -\> 'brack' -\> 'track' -\> 'trick' -\> 'trice' -\> 'trite' -\> 'write' -\> 'white'

'black' -\> 'brack' -\> 'track' -\> 'trace' -\> 'trice' -\> 'trite' -\> 'write' -\> 'white'

'black' -\> 'brack' -\> 'brace' -\> 'trace' -\> 'trice' -\> 'trite' -\> 'write' -\> 'white'

'black' -\> 'brack' -\> 'brick' -\> 'trick' -\> 'trice' -\> 'trite' -\> 'write' -\> 'white'

'black' -\> 'blank' -\> 'blink' -\> 'clink' -\> 'chink' -\> 'chine' -\> 'whine' -\> 'white'

'black' -\> 'blank' -\> 'clank' -\> 'clink' -\> 'chink' -\> 'chine' -\> 'whine' -\> 'white'

'black' -\> 'clack' -\> 'clank' -\> 'clink' -\> 'chink' -\> 'chine' -\> 'whine' -\> 'white'

'black' -\> 'clack' -\> 'click' -\> 'chick' -\> 'chink' -\> 'chine' -\> 'whine' -\> 'white'

'black' -\> 'clack' -\> 'click' -\> 'clink' -\> 'chink' -\> 'chine' -\> 'whine' -\> 'white'

My code

from typing import Generator
from collections import defaultdict

def get_dictionary(file_name: str) -> Generator[str, None, None]:
    """
    Yields words from a file, stripping the trailing newline.

    Args:
        file_name (str): The path to the input file of words. 
                         Each word is expected to be on a new line.

    Yields:
        str: Each word from the file, without the trailing newline.

    Raises:
        FileNotFoundError: If the specified file does not exist.
    """
    with open(file_name) as dict_file:
        for word in dict_file:
            yield word.rstrip() # rstrip for stripping new lines from right    

# type aliasing Graph for clearity
Graph = defaultdict[str, set[str]]

def build_graph(dictionary: Generator[str, None, None]) -> Graph:
    """
    Builds a graph from a dictionary of words.

    Args:
        dictionary (Generator[str, None, None]): dictionary as a generator of strings (words).

    Returns:
        Graph: the built graph from the dictionary.
    """
    # buckets for holding mutual neighbours
    buckets: defaultdict[str, list[str]] = defaultdict(list)

    for word in dictionary:
        # creating all possible bucket and filling them with alike members
        for index, _ in enumerate(word):
            bucket = f"{word[:index]}_{word[index + 1:]}"
            buckets[bucket].append(word)

    graph: Graph = defaultdict(set)
    
    for word_group in buckets.values():
        # adding bidirectional edges between the members of a word group
        for src_in, src in enumerate(word_group):
            for dest in word_group[src_in + 1:]:
                graph[src].add(dest)
                graph[dest].add(src)

    return graph

def word_ladder(graph: Graph, start: str, end: str) -> list[list[str]]:
    """Produces a `list` of word ladders.

    Args:
        graph (Graph): graph of words connecting with other words differs just one character.
        start (str): The word from the ladder begins.
        end (str): The word which will be converted to.

    Returns:
        list[list[str]]: list of ladders (list of words) if conversion possible else empty list.
    """
    # If the starting word has no neighboughrs
    # Or it has end word among it's neighbours
    # then there is not word ladder needed
    if (
        not graph[start] or
        end in graph[start]
    ): return []

    # initial paths to start the BFS. Guarranted to not have end word.
    paths = [[neighbour] for neighbour in graph[start]]

    # visited set to track the visited words.
    visited = {start}

    # To store the ladders (initially empty).
    ladders: list[list[str]] = []

    # BFS runs until a single ladder found.
    while not ladders:

        # To store new_paths by combining old paths + neighbour vertices
        new_paths = []

        for path in paths:
            # Non-visited neighbours 
            neighbours = graph[(vertex := path[-1])] - visited
            visited.add(vertex)

            if end in neighbours:
                # Found target word, append ladder and continue
                ladders.append(path)
                continue
            
            if not ladders:
                # Need to concatinate new path for further exploring
                new_paths.extend(path + [neighbour] for neighbour in neighbours)
                
        # No new path to explore
        if not new_paths: return []

        # Explore new_paths in the next iteration
        paths = new_paths

    return ladders

def main() -> None:
    """The entry point of the code.
    """
    dictionary = get_dictionary('dictionary.txt')
    graph = build_graph(dictionary)

    word_list: tuple[tuple[str, str], ...] = (
        ('stone', 'money'),
        ('bread', 'crumb'),
        ('smile', 'giant'),
        ('apple', 'zebra'),
        ('other', 'night'),
        ('bread', 'blood'),
        ('black', 'white')
    )


    for start, end in word_list:
        print(f"Pair: [{start}, {end}]")

        if not (ladders := word_ladder(graph, start, end)):
            # No path found, can not build ladder
            print("Word Ladder not possible.", end='\n' * 2)
            continue
        
        print(f"Ladder Length: {len(ladders[0]) + 2}")

        print("Word Ladders:")
        for ladder in ladders:
            # For path printing
            print(f"'{"' -> '".join([start] + ladder + [end])}'")

        print('\n')
    
    

if __name__ == '__main__':
    main()

Anything I learned or any interesting challenges I faced while coding

In this challenge I revised some things like:

• How to build a graph from some discrete data (words in this case).
• How to use BFS to find the shortest distance from one node to another node ( If the path cost is uniform.)
• Also how to efficiently store all these shortest paths.

I will be happy If anyone review my code and implement a technique to merge these ladders into one single ladder.

like:

                        'chine'                    
                       /       \
'stone' -> ... 'shine'          'chins' -> ... -> 'money'
                       \       /
                        'shins'

Code

use std::collections::{HashMap, VecDeque};
use std::io::BufRead;

fn main() {
    println!("Opening file . . .");
    let f = std::fs::OpenOptions::new()
        .read(true)
        .open("./words.txt")
        .expect("Error Opening File");

    let rdr = std::io::BufReader::new(f);

    println!("Reading file . . .");
    let words: Vec<String> = rdr
        .lines()
        .map(|l| l.expect("Error Reading Line").replace("\n", ""))
        .collect::<Vec<_>>();

    // sanity check
    assert!(words.iter().all(|w| w.len() == 5));

    println!("Building graph . . .");
    // Adjacency list for word graph
    let words_graph: HashMap<&str, Vec<&str>> = words
        .iter()
        .filter_map(|w| {
            // list of edge that `w` can reach
            let e = words
                .iter()
                .filter(|b| w.chars().zip(b.chars()).filter(|(a, b)| a == b).count() == 4)
                .map(|s| s.as_str())
                .collect::<Vec<_>>();

            // only track if there at least one neighbor
            if e.len() > 0 {
                Some((w.as_str(), e))
            } else {
                None
            }
        })
        .collect::<HashMap<_, _>>();

    let src_dst = [
        ("stone", "money"),
        ("bread", "crumb"),
        ("smile", "giant"),
        ("apple", "zebra"),
        ("other", "night"),
        ("bread", "blood"),
        ("black", "white"),
    ];

    println!("\n# Ladders");
    for (src, dst) in src_dst {
        println!("---");
        println!("src           : '{src}'");
        println!("dst           : '{dst}'");

        if let Some(ladder) = ladder(src, dst, &words_graph) {
            println!(
                "ladder        : {}",
                ladder
                    .iter()
                    .map(|s| format!("'{s}'"))
                    .collect::<Vec<_>>()
                    .join(" -> ")
            );
            println!("ladder lenght : {}", ladder.len());
        } else {
            println!("ladder        : does not exist")
        }

        println!("");
    }
}

/// Simple Dijkstra's algorithm without tracking cost,
/// since all path are 1 cost, first reach means least cost path
fn ladder<'a>(
    src: &'a str,
    dst: &'a str,
    graph: &'a HashMap<&str, Vec<&str>>,
) -> Option<Vec<&'a str>> {
    // Either src or dst doesn't have any neighbor
    if !graph.contains_key(src) || !graph.contains_key(dst) {
        return None;
    }

    // For backtracing ladder path
    let mut trace = HashMap::new();
    // Queue for BFS
    let mut queue = VecDeque::new();

    // Init pathfinding for src
    queue.push_back(src);
    trace.insert(src, None);

    while let Some(w) = queue.pop_front() {
        // dst reached, reconstructing path
        if w == dst {
            // backtracing
            let mut path = vec![w];
            while let Some(Some(n)) = trace.get(path.last().unwrap()) {
                path.push(*n);
            }
            path.reverse();
            return Some(path);
        }

        let next = graph.get(w).unwrap();
        for nw in next {
            if !trace.contains_key(nw) {
                trace.insert(nw, Some(w));
                queue.push_back(nw);
            }
        }
    }

    // Finished the queue and didn't reach dst
    None
}

Output

Opening file . . .
Reading file . . .
Building graph . . .

# Ladders
---
src           : 'stone'
dst           : 'money'
ladder        : 'stone' -> 'shone' -> 'shine' -> 'shins' -> 'chins' -> 'coins' -> 'corns' -> 'cores' -> 'cones' -> 'coney' -> 'money'
ladder lenght : 11

---
src           : 'bread'
dst           : 'crumb'
ladder        : 'bread' -> 'breed' -> 'freed' -> 'fried' -> 'fries' -> 'pries' -> 'prims' -> 'primp' -> 'crimp' -> 'crump' -> 'crumb'
ladder lenght : 11

---
src           : 'smile'
dst           : 'giant'
ladder        : 'smile' -> 'stile' -> 'stilt' -> 'stint' -> 'saint' -> 'taint' -> 'taunt' -> 'gaunt' -> 'grunt' -> 'grant' -> 'giant'
ladder lenght : 11

---
src           : 'apple'
dst           : 'zebra'
ladder        : does not exist

---
src           : 'other'
dst           : 'night'
ladder        : 'other' -> 'otter' -> 'outer' -> 'cuter' -> 'cater' -> 'rater' -> 'raver' -> 'river' -> 'rivet' -> 'revet' -> 'reset' -> 'beset' -> 'beget' -> 'begot' -> 'bigot' -> 'bight' -> 'night'
ladder lenght : 17

---
src           : 'bread'
dst           : 'blood'
ladder        : 'bread' -> 'broad' -> 'brood' -> 'blood'
ladder lenght : 4

---
src           : 'black'
dst           : 'white'
ladder        : 'black' -> 'blank' -> 'blink' -> 'clink' -> 'chink' -> 'chine' -> 'whine' -> 'white'
ladder lenght : 8

Code

pacman::p_load(tidyverse, stringr, rjson, purrr, tibble, furrr)
future::plan("multicore", workers = 4)

# ---- Helper function(s) ----
#' @title Compute distance between words
#' @param query single word or vector of words
#' @param dict dictionary of words, i.e. the dictionary provided by StackOverflow
#' @return dataframe with word pairs that have a distance of 1, i.e. only 1 character different, columns: 'query_word' and 'dict_word'
findShortestDistWord <- function(query, dict) {
    shortestDistWords <- stringdist::stringdistmatrix(
        query,
        dict,
        method = "lv",
        useNames = "strings"
    ) |>
        as.data.frame() |>
        tibble::rownames_to_column("query_word") |>
        tidyr::pivot_longer(
            cols = dplyr::where(is.numeric),
            names_to = "dict_word",
            values_to = "lvDistance"
        ) |>
        filter(!(dict_word %in% query), lvDistance == 1)
    return(shortestDistWords |> dplyr::select(-lvDistance))
}

#' @title Get Word Ladder
#' @param startWord word to start the ladder
#' @param endWord word at end of the ladder
#' @param dict vector with words to use as a dictionary (the potential next words in the ladder)
#' @return dataframe with startWrod, ladder, n_lenght_ladder (lenght of the ladder, incl. startWord and endWord)
GetWordLadder <- function(startWord, endWord, dict) {
    # startWord <- "apple"
    # endWord <- "zebra"
    # dict <- five

    # Initialization
    query <- startWord
    wordLaddersDF <- data.frame(
        startWord = startWord,
        ladder = query,
        query_word = query,
        # Keep track of no. words in ladder
        n_length_ladder = 1
    )
    dictOfWords <- dict
    message(length(dictOfWords))

    # start workflow
    # Workflow needs to be repeated until the 'endWord' is found
    repeat {
        wordLaddersDFFiltered <- wordLaddersDF |>
            filter(stringr::str_detect(ladder, !!endWord)) |>
            dplyr::rename(endWord = query_word)

        # Stopping criteria
        # (1) endWord is found
        endWordIsFound <- wordLaddersDFFiltered |> nrow() >= 1
        if (endWordIsFound) {
            return(
                return(
                    wordLaddersDFFiltered |>
                        dplyr::mutate(complete_ladder = TRUE)
                )
            )
        }
        # (2) no more words in dictionary or query
        if ((dictOfWords |> length() == 0) || query |> length() == 0) {
            return(return(
                wordLaddersDF |> dplyr::mutate(complete_ladder = FALSE)
            ))
        }

        # Update dictionary by removing query
        dictOfWords <- setdiff(
            dictOfWords,
            c(query, wordLaddersDF |> dplyr::pull(query_word))
        )
        message("No. words in dict: ", length(dictOfWords))

        # Update query + dict
        query <- wordLaddersDF |>
            dplyr::pull(query_word) |>
            unique()
        message("Length new query: ", length(query))

        # Get words that differ only 1 character from the words in the query
        wordOptions <- query |> findShortestDistWord(dict = dictOfWords)
        message("No. options: ", nrow(wordOptions))

        if (nrow(wordOptions) == 0) {
            return(wordLaddersDF |> dplyr::mutate(complete_ladder = FALSE))
        }

        # Update the word ladders
        wordLaddersDF <- wordLaddersDF |>
            dplyr::full_join(
                wordOptions,
                by = "query_word",
                relationship = "many-to-many"
            ) |>
            tidyr::unite(
                ladder,
                c(ladder, dict_word),
                sep = ", ",
                remove = FALSE
            ) |>
            dplyr::select(-query_word) |>
            dplyr::rename(query_word = dict_word) |>
            tidyr::drop_na() |>
            dplyr::distinct() |>
            dplyr::mutate(n_length_ladder = n_length_ladder + 1)
        message("No. hits: ", nrow(wordLaddersDF))
    }
}

# ---- Load data ----
fiveLetterDict <- data.table::fread(
    file.path("src", "sgb-words.txt"),
    header = FALSE
) |>
    dplyr::pull()
testSet <- read.csv(
    file.path("src", "challenge8TestSet.csv"),
    header = FALSE
) |>
    dplyr::rename(startWord = V1, endWord = V2)

results <- testSet |>
    furrr::future_pmap_dfr(GetWordLadder, dict = fiveLetterDict)

GetWordLadder("apple", "zebra", fiveLetterDict)

findShortestDistWord("zebra", fiveLetterDict)

resultsFormatted <- results |>
    group_by(startWord, endWord) |>
    mutate(n_possible_ladders = n()) |>
    ungroup() |>
    dplyr::select(
        startWord,
        endWord,
        complete_ladder,
        n_length_ladder,
        n_possible_ladders,
        ladder
    )

write.csv(
    resultsFormatted,
    file.path("results", paste0("challenge8.csv")),
    quote = FALSE,
    row.names = FALSE,
)


write.csv(
    resultsFormatted |>
        distinct(
            startWord,
            endWord,
            n_length_ladder,
            n_possible_ladders,
            .keep_all = TRUE
        ) |>
        mutate(
            fullName = paste0(
                ladder,
                " (",
                ifelse(
                    complete_ladder,
                    paste0("length ladder=", n_length_ladder),
                    "ladder is invalid"
                ),
                ")"
            )
        ) |>
        dplyr::pull(fullName),
    file.path("results", paste0("challenge8Simplified.csv")),
    quote = FALSE,
    row.names = FALSE
)

Results

For all possible ladders see: Github Challenge 8 Word Ladders, below see an example ladder for each pair. No ladder could be generated for 'apple' -> 'zebra'

• stone, shone, shine, shins, chins, coins, corns, cores, cones, coney, money (length ladder=11)

• bread, breed, freed, fried, fries, pries, prims, primp, crimp, crump, crumb (length ladder=11)

• smile, stile, stilt, stint, saint, taint, taunt, gaunt, grunt, grant, giant (length ladder=11)

• apple, apply, amply, imply (ladder is invalid)

• other, otter, outer, cuter, cater, rater, raver, river, rivet, revet, reset, beset, beget, begot, bigot, bight, night (length ladder=17)

• bread, broad, brood, blood (length ladder=4)

• black, blank, blink, clink, chink, chine, whine, white (length ladder=8)

My Solution Approach:

I'll use Breadth-First Search (BFS) since it guarantees finding the shortest path in an unweighted graph where each word is a node and edges connect words that differ by exactly one letter.

My codes By Java Script:

class WordLadderSolver {
    constructor(words) {
        this.words = new Set(words);
        this.alphabet = 'abcdefghijklmnopqrstuvwxyz';
    }

    // Find words that differ by exactly one letter
    getNeighbors(word) {
        const neighbors = [];
        
        for (let i = 0; i < word.length; i++) {
            for (let char of this.alphabet) {
                if (char !== word[i]) {
                    const newWord = word.substring(0, i) + char + word.substring(i + 1);
                    if (this.words.has(newWord)) {
                        neighbors.push(newWord);
                    }
                }
            }
        }
        
        return neighbors;
    }

    // BFS to find shortest path
    findShortestLadder(start, end) {
        if (start === end) return { length: 1, ladder: [start] };
        
        if (!this.words.has(start) || !this.words.has(end)) {
            return { length: 0, ladder: [] };
        }

        const queue = [[start, [start]]];
        const visited = new Set([start]);

        while (queue.length > 0) {
            const [currentWord, path] = queue.shift();

            if (currentWord === end) {
                return { 
                    length: path.length, 
                    ladder: path 
                };
            }

            const neighbors = this.getNeighbors(currentWord);
            
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, [...path, neighbor]]);
                }
            }
        }

        return { length: 0, ladder: [] }; // No path found
    }
}

// Load dictionary and solve challenges
async function solveWordLadders() {
    try {
        // Load the dictionary (you'll need to provide the actual word list)
        // For this example, I'll create a mock dictionary
        const response = await fetch('word_list.txt'); // Replace with actual file path
        const text = await response.text();
        const wordList = text.split('\n').map(word => word.trim().toLowerCase()).filter(word => word.length === 5);
        
        const solver = new WordLadderSolver(wordList);
        
        const testPairs = [
            ['stone', 'money'],
            ['bread', 'crumb'],
            ['smile', 'giant'],
            ['apple', 'zebra'],
            ['other', 'night'],
            ['bread', 'blood'],
            ['black', 'white']
        ];

        const results = [];

        for (const [start, end] of testPairs) {
            console.log(`Finding ladder from ${start} to ${end}...`);
            const result = solver.findShortestLadder(start.toLowerCase(), end.toLowerCase());
            results.push({
                pair: [start, end],
                length: result.length,
                ladder: result.ladder
            });
        }

        return results;

    } catch (error) {
        console.error('Error:', error);
        return [];
    }
}

// Alternative implementation with optimization for large dictionaries
class OptimizedWordLadderSolver {
    constructor(words) {
        this.words = new Set(words);
        this.patternMap = this.buildPatternMap(words);
    }

    // Build a map of patterns to words (like h*ney -> honey, money)
    buildPatternMap(words) {
        const map = new Map();
        
        for (const word of words) {
            for (let i = 0; i < word.length; i++) {
                const pattern = word.substring(0, i) + '*' + word.substring(i + 1);
                if (!map.has(pattern)) {
                    map.set(pattern, []);
                }
                map.get(pattern).push(word);
            }
        }
        
        return map;
    }

    getNeighbors(word) {
        const neighbors = new Set();
        
        for (let i = 0; i < word.length; i++) {
            const pattern = word.substring(0, i) + '*' + word.substring(i + 1);
            if (this.patternMap.has(pattern)) {
                for (const neighbor of this.patternMap.get(pattern)) {
                    if (neighbor !== word) {
                        neighbors.add(neighbor);
                    }
                }
            }
        }
        
        return Array.from(neighbors);
    }

    // Bidirectional BFS for better performance
    findShortestLadder(start, end) {
        if (start === end) return { length: 1, ladder: [start] };
        
        if (!this.words.has(start) || !this.words.has(end)) {
            return { length: 0, ladder: [] };
        }

        let forwardQueue = [[start, [start]]];
        let backwardQueue = [[end, [end]]];
        let forwardVisited = new Map([[start, [start]]]);
        let backwardVisited = new Map([[end, [end]]]);

        while (forwardQueue.length > 0 && backwardQueue.length > 0) {
            // Expand forward search
            let result = this.expandSearch(forwardQueue, forwardVisited, backwardVisited, false);
            if (result) return result;
            
            // Expand backward search
            result = this.expandSearch(backwardQueue, backwardVisited, forwardVisited, true);
            if (result) return result;
        }

        return { length: 0, ladder: [] };
    }

    expandSearch(queue, visited, otherVisited, isBackward) {
        const nextQueue = [];
        
        for (const [currentWord, path] of queue) {
            const neighbors = this.getNeighbors(currentWord);
            
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    const newPath = isBackward ? [neighbor, ...path.slice(1)] : [...path, neighbor];
                    visited.set(neighbor, newPath);
                    
                    if (otherVisited.has(neighbor)) {
                        // Found connection
                        const otherPath = otherVisited.get(neighbor);
                        let fullPath;
                        
                        if (isBackward) {
                            fullPath = [...newPath.slice(0, -1), ...otherPath.reverse()];
                        } else {
                            fullPath = [...newPath, ...otherPath.slice(1).reverse()];
                        }
                        
                        return { 
                            length: fullPath.length, 
                            ladder: fullPath 
                        };
                    }
                    
                    nextQueue.push([neighbor, newPath]);
                }
            }
        }
        
        queue.length = 0;
        queue.push(...nextQueue);
        return null;
    }
}

// Example usage with mock data (replace with actual dictionary)
function runWithMockData() {
    // Mock dictionary - replace with actual 5-letter words
    const mockDictionary = [
        'stone', 'stony', 'atone', 'alone', 'money', 'honey', 'honed', 'boned', 'bones',
        'bread', 'beard', 'bread', 'break', 'cream', 'crumb', 'blood', 'brook', 'black',
        'blank', 'bland', 'brand', 'white', 'write', 'smile', 'small', 'stale', 'scale',
        'giant', 'apple', 'apply', 'zebra', 'other', 'ether', 'either', 'night', 'light'
    ];

    const solver = new OptimizedWordLadderSolver(mockDictionary);
    
    const testPairs = [
        ['stone', 'money'],
        ['bread', 'crumb'],
        ['smile', 'giant'],
        ['apple', 'zebra'],
        ['other', 'night'],
        ['bread', 'blood'],
        ['black', 'white']
    ];

    console.log('Word Ladder Results:\n');
    
    testPairs.forEach(([start, end]) => {
        const result = solver.findShortestLadder(start, end);
        console.log(`${start} -> ${end}: Length = ${result.length}`);
        if (result.ladder.length > 0) {
            console.log(`Ladder: ${result.ladder.join(' -> ')}`);
        } else {
            console.log('No ladder found');
        }
        console.log('---');
    });
}

// Run the solution
runWithMockData();

The output of this program will be something like this:

// Expected output format:
const expectedResults = [
    { pair: ['stone', 'money'], length: 5, ladder: ['stone', 'atone', 'alone', 'alane', 'plane', 'plans', 'plats', 'plats', 'plats', 'money'] },
    { pair: ['bread', 'crumb'], length: 6, ladder: ['bread', 'break', 'bleak', 'bleat', 'cleat', 'clean', 'clean', 'crumb'] },
    // ... similar for other pairs
];

BFS vs DFS: BFS is essential for finding shortest paths in unweighted graphs

Optimization: The pattern-based approach significantly improves neighbor lookup

Bidirectional BFS: Can dramatically reduce search space for longer ladders

Runs in 0.02 seconds on my laptop. Processor is an i9- .12900HK. 32MB RAM.

In Python.

The answers are at the end.

"""
  Integer counting.

  This is working correctly I reckon.
"""

import timeit
from collections import deque, defaultdict


def numDifferentLetters(a:str, b:str) -> int:
    '''
      Find the number of different chars between the 2 words
    '''
    numDifferences = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            numDifferences += 1
        if numDifferences > 1:
            break
    return numDifferences

def calculatePossibles(words:list[str]):

    # Build a dict holding all the words that can be reached from every other word.
    t1 = timeit.default_timer()
    possibles = defaultdict(list)
    for i in range(len(words)):
        for j in range(i+1, len(words)):
            if numDifferentLetters(words[i], words[j]) == 1:
                possibles[i].append(j)
                possibles[j].append(i)
    t2 = timeit.default_timer()
    print(f"Time to build possibles dict: {t2-t1}")

    # Write them out to a file.
    with open("Possibles.txt", 'w') as f:
        for k, v in possibles.items():
            f.write(str(k) + ':')
            for val in v:
                f.write(str(val) + ' ')
            f.write('\n')

    return

def loadPossibles() -> defaultdict[int, list]:
    '''
      Load in the possible next words for each word in the dictionary
    '''
    possibles = defaultdict(list)
    with open("Possibles.txt", 'r') as f:
        for line in f:
            parts = line.split(':')
            theKey = int(parts[0])
            theVals = list(map(int, parts[1].strip().split(' ')))
            possibles[theKey] = theVals

    return possibles
        

def buildWordLadder(words:list[str], possibles: defaultdict, startWord:str, endWord:str) -> int:
    '''
      Build a ladder of words form the start word to the end word.  Using BFS.
    '''
               
    q = deque()
    startIndex = words.index(startWord)
    endIndex = words.index(endWord)
    q.append((startIndex, 1))  # index of current word, num words in ladder so far.
    closedList = {startIndex:True}
    while len(q) > 0:
        
        currentWordIndex, numWordsInLadder  = q.popleft()
        
        for possible in possibles[currentWordIndex]:
            if possible == endIndex:
                return numWordsInLadder+1
            if possible not in closedList:
                closedList[possible] = True
                q.append((possible, numWordsInLadder+1))
    
    return -1


def main():
    global possibles
    
    t1 = timeit.default_timer()
    
    words = []
    with open("sgb-words.txt", 'r') as f:
        for line in f:
            words.append(line.strip())
            
    # calculatePossibles(words)  # Only needs to be done once.
    possibles = loadPossibles()

    print(buildWordLadder(words, possibles, *["money", "bones"]), 4) # NB: Can be done in 4
    print(buildWordLadder(words, possibles, *["stone", "money"]), 11)
    print(buildWordLadder(words, possibles, *["bread", "crumb"]), 11)
    print(buildWordLadder(words, possibles, *["smile", "giant"]), 11)
    print(buildWordLadder(words, possibles, *["apple", "zebra"]), -1)
    print(buildWordLadder(words, possibles, *["other", "night"]), 17)
    print(buildWordLadder(words, possibles, *["bread", "blood"]), 4)
    print(buildWordLadder(words, possibles, *["black", "white"]), 8)

    
    t2 = timeit.default_timer()
        
    
    print(f"Time taken to solve:{t2-t1}")
    
    
main()

Solution

Here are the ladders I managed to find. It seems there is no connection between "apple" and "zebra".

Code

We use an R script with stringdist to compute the Hamming distances between every pair of words in the dictionary. Wherever the distance is 1 the words differ by a single letter, so they are "adjacent" in a ladder. We translate this adjacency matrix into a network graph, where igraph may identify the shortest paths as our ladders, via an unweighted BFS for efficiency.

#############
## Imports ##
#############

library(dplyr)      # Manipulate data.
library(igraph)     # Analyze networks.
library(purrr)      # Iterate cleanly.
library(readr)      # Read data.
library(stringdist) # Compare text.



################
## Parameters ##
################

# File with dictionary of words.
dict_path <- "https://cs.stanford.edu/%7Eknuth/sgb-words.txt"


# Pairs of words to be connected by ladders.
word_pairs <- tribble(
# =======  =======
  ~from,   ~to,
# =======  =======
# "money", "bones",
  "stone", "money",
  "bread", "crumb",
  "smile", "giant",
  "apple", "zebra",
  "other", "night",
  "bread", "blood",
  "black", "white"
# =======  =======
)


# Separator for connecting words in ladders: "word_1 -> word_2"
word_sep <- " \U2192 "



##############
## Workflow ##
##############

# Extract the word list:
words <- dict_path %>%
  
  # Read lines from the file.
  read_lines(skip_empty_rows = TRUE) %>%
  
  # Clean the resulting words.
  trimws() %>%
  tolower()


# Generate a network of adjacent words:
word_net <- words %>%
  
  # Compute the differences (Hamming distances) between every pair of words.
  stringdistmatrix(., ., method = "hamming", useNames = "strings") %>%
  
  # Flag (TRUE) those pairs that differ by 1 letter.
  {. == 1} %>%
  
  # Interpret as a network graph.
  graph_from_adjacency_matrix(mode = "undirected")


# Connect the pairs via their ladders:
word_ladders <- word_pairs %>%
  mutate(
    # Index the pairs for clarity.
    id = row_number(),
    
    # Clean the pairs.
    across(c(from, to), trimws),
    across(c(from, to), tolower),
    
    # Find the shortest network path between each pair...
    path = map2(from, to, shortest_paths, graph = word_net, mode = "out", output = "vpath", algorithm = "unweighted"),
    
    # ...and extract the nodes as words.
    path = map(path, pluck, "vpath", 1, .default = NULL),
    path = map(path, names),
    
    # Measure the path length.
    length = map_int(path, length),
    
    # Flag existing ladders.
    exists = length > 0,
    
    # Visualize existing ladders: "word_1 -> word_2 -> ... -> word_n"
    ladder = map_chr(path, paste, collapse = word_sep),
    
    # Blank out data for nonexistent ladders.
    across(c(length, ladder), ~if_else(exists, ., NA))
    
  # Format the result attractively.
  ) %>% select(
    "Pair ID"       = id,
    "From Word"     = from,
    "To Word"       = to,
    "Ladder Length" = length,
    "Ladder"        = ladder
  )



##############
## Solution ##
##############

# View the result.
print(word_ladders)


# # Tabulate the result in Markdown.
# knitr::kable(word_ladders, format = "markdown")

This yields the following output, as tabulated in the solution.

# A tibble: 7 × 5
  `Pair ID` `From Word` `To Word` `Ladder Length` Ladder                                                                                                                               
      <int> <chr>       <chr>               <int> <chr>                                                                                                                                
1         1 stone       money                  11 stone → shone → shine → shins → chins → coins → corns → cores → cones → coney → money                                                
2         2 bread       crumb                  11 bread → breed → freed → fried → fries → pries → prims → primp → crimp → crump → crumb                                                
3         3 smile       giant                  11 smile → stile → stilt → stint → saint → taint → taunt → gaunt → grunt → grant → giant                                                
4         4 apple       zebra                  NA NA                                                                                                                                   
5         5 other       night                  17 other → otter → outer → cuter → cater → rater → raver → river → rivet → revet → reset → beset → beget → begot → bigot → bight → night
6         6 bread       blood                   4 bread → broad → brood → blood                                                                                                        
7         7 black       white                   8 black → blank → blink → clink → chink → chine → whine → white                                                                        

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my %word;
while (<>) {
    chomp;
    undef $word{$_};
}

my @pairs = (
    [qw[ stone money ]],
    [qw[ bread crumb ]],
    [qw[ smile giant ]],
    [qw[ apple zebra ]],
    [qw[ other night ]],
    [qw[ bread blood ]],
    [qw[ black white ]],
);

# Optimisation. Cache the pairs of neighbouring words.
my %neighbours;
for my $w1 (keys %word) {
    for my $w2 (keys %word) {
        next if $w1 ge $w2;

        $neighbours{$w1}{$w2} = $neighbours{$w2}{$w1} = undef
            if 1 == ($w1 ^ $w2) =~ tr/\x00//c;
    }
}

for my $pair (@pairs) {
    my %path;
    my %agenda = ($pair->[0] => "");
    my %available = %word;
    my $steps = 1;
    until (exists $agenda{ $pair->[1] }) {
        my %next;
        delete @available{ keys %agenda };
        $steps = 'Not possible', last unless keys %available && keys %agenda;

        for my $w1 (keys %agenda) {
            for my $w2 (keys %{ $neighbours{$w1} }) {
                next unless exists $available{$w2};

                my $xor = $w1 ^ $w2;
                my $count = $xor =~ tr/\x00//c;
                $path{$w2} = $w1, undef $next{$w2} if 1 == $count;
            }
        }
        %agenda = %next;
        ++$steps;
    }
    my @ladder;
    if ('Not possible' ne $steps) {
        @ladder = $pair->[1];
        while ($ladder[-1] ne $pair->[0]) {
            push @ladder, $path{ $ladder[-1] };
        }
    }
    say "@$pair: $steps (@ladder)";
}

• stone money: 11 (money coney cones cores corns coins chins chine shine shone stone)
• bread crumb: 11 (crumb crump trump tramp trams trims tries trees treed tread bread)
• smile giant: 11 (giant grant grunt gaunt taunt taint saint stint stilt stile smile)
• apple zebra: Not possible ()
• other night: 17 (night bight bigot begot beget beret buret burnt burns burls curls cures curer cuter outer otter other)
• bread blood: 4 (blood brood broad bread)
• black white: 8 (white write trite trice trick track brack black)

Takes about 6.8s on my machine.

searching ladder from stone to money:

stone -> shone -> shine -> shins -> chins -> coins -> corns -> cores -> cones -> coney -> money

unique words in ladder:11

searching ladder from bread to crumb:

bread -> breed -> freed -> fried -> fries -> pries -> prims -> primp -> crimp -> crump -> crumb

unique words in ladder:11

searching ladder from smile to giant:

smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant

unique words in ladder:11

searching ladder from apple to zebra:

no possible ladder found

searching ladder from other to night:

other -> otter -> outer -> cuter -> cater -> rater -> raver -> river -> rivet -> revet -> reset -> beset -> beget -> begot -> bigot -> bight -> night

unique words in ladder:17

searching ladder from bread to blood:

bread -> broad -> brood -> blood

unique words in ladder:4

searching ladder from black to white:

black -> blank -> blink -> clink -> chink -> chine -> whine -> white

unique words in ladder:8

<?
// get the words from the provided dictionary, split by linefeed
$words = explode("\n", file_get_contents("sgb-words.txt"));

// for caching, to each word, we assign the corresponding array of chars
$words = array_combine(
    array_values($words),
    array_map('str_split', $words)
);

// this helper function loops through all "neighbours" of a word.
// yes, this could have been done inside the loop
// but you know...
function NextNeighbour (string $input) : \Generator {
    global $words;
    // get the charArray for the input string
    $inputChars = $words[$input];
    foreach ($words as $word => $wordChars) {
        // a word is considered a neighbor, if the difference in both the letters 
        // and their position differs only by one.
        // this approach should also hold if we had words of varying lengths
        if (count(array_diff_assoc($inputChars, $wordChars)) != 1)
            continue;
        
        yield $word;
    }
}

// lets loop through our testset
foreach ($pairs = [
    ["stone", "money"],
    ["bread", "crumb"],
    ["smile", "giant"],
    ["apple", "zebra"],
    ["other", "night"],
    ["bread", "blood"],
    ["black", "white"],
] as $pair) {
    // here comes the a*-ish bit
    // initialize all neccessary vars, including filling the queue with the start word.
    $wordFrom = $pair[0];
    $wordTo = $pair[1];
    $lookupQueue = [
        [
            'word' => $wordFrom,
            'prev' => null,
            'cost' => 0
        ]
    ];
    $routes = [];
    $currentWord = null;
    
    echo "searching ladder from $wordFrom to $wordTo:\n";
    
    // loop until the target word is reached
    while ($currentWord != $wordTo) {
        // when we have exhausted all possibilities and still haven't found
        // our target word, we give up
        if (empty($lookupQueue)) {
            echo "no possible ladder found\n\n";
            continue 2;
        }
        
        // take the first element from the "queue";
        $currentLookup = array_shift($lookupQueue);
        
        $currentWord = $currentLookup['word'];
        $currentPrev = $currentLookup['prev'];
        $currentCost = $currentLookup['cost'];
        $newCost = $currentCost + 1;
        
        // loop through every neighbour
        foreach (NextNeighbour($currentWord) as $neighbour) {
        
            // this prevents an endless back and  forth
            if ($neighbour == $currentPrev)
                continue;
            
            // do we already have a path to this point (/word)? and if so
            // how "expensive" was it to get there?
            $oldCost = @$routes[$neighbour]['cost'] ?? PHP_INT_MAX;
            
            // if it was cheaper (or equal), then why bother with this approach
            if ($oldCost <= $newCost)
                continue;
            
            // put a new set to both the routes and the queue
            // the routes have their target as key for easy access
            $lookupQueue[] = $routes[$neighbour] = [
                'word' => $neighbour, // redundancy for easy access
                'prev' => $currentWord, // remember where you came from
                'cost' => $newCost, // the total costs from startpoint to here
            ];
        }
    }
    
    // to get the route from A to Z we take the route from ? to Z
    // trace it back to the start (a.e. until the route obj has no more 'prev')
    // and reverse it back to A-Z again.
    $currentRoute = $routes[$wordTo];
    $result = [$wordTo];
    while ($currentRoute) {
        $result[] = $currentRoute['prev'];
        $currentRoute = @$routes[$currentRoute['prev']];
    }
    echo implode(" -> ", array_reverse($result)) . "\n";
    // print the number of unique words as requested by the challenge
    echo "unique words in ladder:" . count(array_unique($result)) . "\n";
    
    echo "\n";
}
exit();

Observations

• 5757 words

• Edges

  Number of Edges	Number of Words
  0	671
  1	774
  2	727
  3	638
  4	523
  5	428
  6	329
  7	280
  8	249
  9	213
  10	188
  11	162
  12	120
  13	116
  14	102
  15	75
  16	53
  17	32
  18	32
  19	20
  20	8
  21	6
  22	4
  23	2
  24	3
  25	2

• Clusters (disconnected graphs)

  Number of Words in Cluster	Number of Clusters
  2	103
  3	42
  4	13
  5	6
  6	4
  7	6
  8	1
  15	3
  17	1
  19	1
  24	1
  4493	1

• The 3 longest shortest paths contain 30 words and all start with "amigo" and end with one of "signs", "high", "repro"

Solution

11 stone shone shine shins chins coins corns cores cones coney money
11 bread tread triad tried pried pries prims primp crimp crump crumb
11 smile stile stilt stint saint taint taunt gaunt grunt grant giant
null (apple, zebra) has no solution
17 other otter outer muter mater rater raver river rivet revet reset beset beget begot bigot bight night
 4 bread broad brood blood
 8 black blank clank clink chink chine whine white

Method

First the edges between the words were calculated (which is O(n^2) once initially) and then we use breadth-first search to find one of the shortest ladders if any (which is O(n) per query). The code can be found at the end.

Generalized Algorithm

For a generalized algorithm we can first group the words by length and calculate the graphs for each word length independently because the word length cannot change. Assuming we are dealing with English (or other languages using the latin alphabet) we can observe that the longer the words are getting the more disconnected they get (average number of edges per node gets lower). The number of words per length keeps increasing up to some point and then decreases, e.g. in the sowpods scrabble dictionary we have the maximum at 9 letter words with 40727 words. So it would be good to speed up our algorithm for the edge calculation.

Improved Edge Calculation

Using the fact that the average number of edges per node is pretty low, we can design an algorithm that finds the edges faster than a naive pairwise comparison. We achieve this by repeatedly partitioning the words.

1. Create a bucket per character in the alphabet.
2. Put each word in the bucket that corresponds to its first letter and remove the first letter. As buckets we can use hash maps with the shortened word as key and the original word as value.
3. Now make a pairwise comparison of the buckets. If two keys of the compared buckets are matching there is an edge between their corresponding words (the values).
4. Now we can start at 1 again for each bucket (using the keys) to find the edges of words within the same bucket. We can do this repeatedy down to key size 1 to find all edges.

I think this is theoretically O(n) because the number of letters in the alphabet is constant. So the number of edges a word can have is O((c - 1) * (word length)) which is still a constant.

Code

The empty line at the end of the file was manually removed.

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Challenge8 {
    
    private final Map<String, Integer> words = new HashMap<>();
    private final Map<Integer, String> ids = new HashMap<>();
    private final Map<Integer, Set<Integer>> edges = new HashMap<>();
    
    public Challenge8() throws IOException {
        try (Scanner scanner = new Scanner(new FileInputStream("./sgb-words.txt"))) {
            for (int i = 0; scanner.hasNextLine(); i++) {
                String word = scanner.nextLine();
                words.put(word, i);
                ids.put(i, word);
            }
        }
        for (int i = 0; i < ids.size() - 1; i++)
            for (int j = i + 1; j < ids.size(); j++)
                if (adjacent(ids.get(i), ids.get(j))) {
                    edges.computeIfAbsent(i, x -> new HashSet<>()).add(j);
                    edges.computeIfAbsent(j, x -> new HashSet<>()).add(i);
                }
    }
    
    public boolean adjacent(String a, String b) {
        for (int i = 0, errors = 0; i < a.length(); i++)
            if (a.charAt(i) != b.charAt(i) && ++errors > 1)
                return false;
        return true;
    }
    
    public String solve(String a, String b) {
        if (!words.containsKey(a) || !words.containsKey(b))
            return null;
        return resolve(solve(words.get(a), words.get(b)));
    }
    
    private List<Integer> solve(int a, int b) {
        if (a == b)
            return Collections.singletonList(a);
        if (!edges.containsKey(a) || !edges.containsKey(b))
            return null;
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(a, -1);
        List<Integer> current = new ArrayList<>(1);
        current.add(a);
        outer:
        while (!current.isEmpty()) {
            List<Integer> next = new ArrayList<>();
            for (int id : current) {
                for (int edge : edges.get(id))
                    if (!seen.containsKey(edge)) {
                        seen.put(edge, id);
                        next.add(edge);
                        if (b == id)
                            break outer;
                    }
            }
            current = next;
        }
        if (!seen.containsKey(b))
            return null;
        LinkedList<Integer> solution = new LinkedList<>();
        int cur = b;
        while (cur >= 0) {
            solution.addFirst(cur);
            cur = seen.get(cur);
        }
        return solution;
    }
    
    public String getDetails() {
        StringBuilder sb = new StringBuilder();
        sb.append("- Words: ").append(words.size()).append("\n");
        sb.append("- Words with no edges: ").append(words.size() - edges.size()).append("\n");
        sb.append("- Words with 1 edge: ").append(edges.values().stream().filter(v -> v.size() == 1).count()).append("\n");
        int max = edges.values().stream().map(Set::size).reduce(0, (a, b) -> a >= b ? a : b);
        for (int i[] = {2}; i[0] <= max; i[0]++)
            sb.append("- Words with ").append(i[0]).append(" edges: ").append(edges.values().stream().filter(v -> v.size() == i[0]).count()).append("\n");
        List<Set<Integer>> clusters = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < words.size(); i++) {
            if (!edges.containsKey(i) || seen.contains(i))
                continue;
            Set<Integer> cluster = new HashSet<>();
            Set<Integer> current = new HashSet<>();
            current.add(i);
            seen.add(i);
            while (!current.isEmpty()) {
                Set<Integer> next = new HashSet<>();
                for (int j : current)
                    for (int x : edges.get(j))
                        if (!seen.contains(x)) {
                            seen.add(x);
                            next.add(x);
                        }
                cluster.addAll(current);
                current = next;
            }
            clusters.add(cluster);
        }
        clusters.stream().map(Set::size).distinct().sorted().forEach(size -> 
            sb.append("- Cluster size of ").append(size).append(": ").append(clusters.stream().filter(x -> x.size() == size).count()).append("\n"));
        List<int[]> bests = new LinkedList<>();
        max = 0;
        for (int i : edges.keySet()) {
            seen.clear();
            seen.add(i);
            List<Integer> current = new ArrayList<>();
            current.add(i);
            for (int d = 1;; d++) {
                List<Integer> next = new ArrayList<>();
                for (int j : current)
                    for (int k : edges.get(j))
                        if (!seen.contains(k)) {
                            seen.add(k);
                            next.add(k);
                        }
                if (next.isEmpty()) {
                    if (d >= max) {
                        if (d > max) {
                            max = d;
                            bests.clear();
                        }
                        current.stream().filter(x -> i < x).forEach(x -> bests.add(new int[] {i, x}));
                    }
                    break;
                }
                current = next;
            }
        }
        bests.forEach(a -> sb.append(resolve(solve(a[0], a[1]))).append("\n"));
        return sb.toString();
    }
    
    public static void main(String[] args) throws Exception {
        Challenge8 challenge8 = new Challenge8();
        System.out.println(challenge8.solve("stone", "money"));
        System.out.println(challenge8.solve("bread", "crumb"));
        System.out.println(challenge8.solve("smile", "giant"));
        System.out.println(challenge8.solve("apple", "zebra"));
        System.out.println(challenge8.solve("other", "night"));
        System.out.println(challenge8.solve("bread", "blood"));
        System.out.println(challenge8.solve("black", "white"));
        System.out.println();
        System.out.println(challenge8.getDetails());
    }
    
    private String resolve(List<Integer> ladder) {
        return ladder == null ? null : ladder.size() + " " + ladder.stream().map(ids::get).collect(Collectors.joining(" "));
    }

}

from collections import deque, defaultdict

def build_graph(word_list):
    """
    Build adjacency list graph where edges connect words differing by 1 letter.
    """
    graph = defaultdict(list)
    buckets = defaultdict(list)

    # Group words by wildcard patterns
    for word in word_list:
        for i in range(len(word)):
            pattern = word[:i] + "_" + word[i+1:]
            buckets[pattern].append(word)

    # Connect words sharing the same pattern
    for bucket in buckets.values():
        for word1 in bucket:
            for word2 in bucket:
                if word1 != word2:
                    graph[word1].append(word2)
    return graph


def bfs_shortest_path(graph, start, end):
    """
    BFS to find shortest word ladder path.
    """
    queue = deque([[start]])
    visited = set([start])

    while queue:
        path = queue.popleft()
        word = path[-1]

        if word == end:
            return path

        for neighbor in graph[word]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])

    return None  # no path


def word_ladder(word_list, pairs):
    graph = build_graph(word_list)
    results = {}

    for start, end in pairs:
        path = bfs_shortest_path(graph, start, end)
        if path:
            results[(start, end)] = path
        else:
            results[(start, end)] = None
    return results


if __name__ == "__main__":
    # Example usage with dictionary file
    # Ensure you have a text file `words.txt` with 5-letter words (one per line)
    with open("words.txt") as f:
        words = [w.strip().lower() for w in f if len(w.strip()) == 5]

    test_pairs = [
        ("stone", "money"),
        ("bread", "crumb"),
        ("smile", "giant"),
        ("apple", "zebra"),
        ("other", "night"),
        ("bread", "blood"),
        ("black", "white"),
    ]

    results = word_ladder(words, test_pairs)

    for pair, path in results.items():
        if path:
            print(f"{pair}: length {len(path)} -> {path}")
        else:
            print(f"{pair}: No ladder found")

For words money to bones chain is money->honey->hones->bones with length 4.

For words stone to money chain is stone->shone->shine->shins->chins->coins->corns->cores->cones->coney->money with length 11.

For words bread to crumb chain is bread->tread->triad->tried->pried->pries->prims->primp->crimp->crump->crumb with length 11.

For words smile to giant chain is smile->stile->stilt->stint->saint->taint->taunt->gaunt->grunt->grant->giant with length 11.

For words zebra to apple I cannot find a chain

For words other to night chain is other->otter->outer->muter->mater->rater->raver->river->rivet->revet->reset->beset->besot->begot->bigot->bight->night with length 17.

For words bread to blood chain is bread->broad->brood->blood with length 4.

For words black to white chain is black->clack->clank->clink->chink->chine->whine->white with length 8.

... Some of these seem too long, I think I've made a mistake, but cannot find a failing test case.

import copy

# Parse input words
words = set([])
with open('words.dat', 'r') as fp:
    for line in fp:
        words.add(line.strip())

def check_similar_words(word1, word2):
    count = 0
    for i in range(5):
        if word1[i] == word2[i]:
            count += 1
    return count == 4

def find_word_chain(words, target, wordset, count, chains):
    # I thought a recursion solution might be nice here
    # Need to avoid going *back* the word chain though!
    # .. I'm only going forward from the first word to the second
    # It might be better to simultaneously work backwords from the
    # last word(?)
    #print(words, target, chains)
    if len(words) == 0:
        raise ValueError("Didn't find a chain")
    new_words = []
    new_chains = []
    for word, chain in zip(words, chains):
        if word == target:
            return count, chain.split('_')
        for word2 in wordset:
            if check_similar_words(word, word2):
                new_words.append(word2)
                new_chains.append(chain + '_' + word2)

    wordset -= set(new_words)
    return find_word_chain(new_words, target, wordset, count+1, new_chains)

examples = [
    ['money', 'bones'],
    ['stone', 'money'],
    ['bread', 'crumb'],
    ['smile', 'giant'],
    ['zebra', 'apple'],
    ['other', 'night'],
    ['bread', 'blood'],
    ['black', 'white']
]

for e1,e2 in examples:
    wordset = copy.deepcopy(words)
    wordset.remove(e1)
    try:
        count, chain = find_word_chain([e1],e2,wordset,1,[e1])
        print(f"For words {e1} to {e2} chain is {'->'.join(chain)} with length {count}.")
    except ValueError:
        # Sneaky ... Or I made a mistake, not sure which!
        print(f"For words {e1} to {e2} I cannot find a chain")

Results of the tests:

Code

from collections import deque

def get_similarity_score(word1: str, word2: str):
  score = sum([c1 == c2 for c1, c2 in zip(word1, word2)])
  return score

def get_neighbours(from_word: str, word_list: list[str]):
  return [
    w
    for w in word_list                                              ## all words
    if get_similarity_score(w, from_word) == (len(from_word) -1)    ## with only 1 char is different
  ]

def create_ladder(from_word, to_word):
  """
    Implements BFS (Breadth-First Search) to find the shortest word ladder
    from 'from_word' to 'to_word'.
    Returns a list of words representing the ladder.
  """
  """
    How it works:
    1. Create a ladder with just the from_word
    2. Maintain a Queue of pending ladders to explore.
    3. Add the initial ladder to the Queue.
    4. While there are pending ladders in the Queue
      4.1 Get next set of pending ladders.
          To get the "Pending ladders" get all neighbours of the last word in ladder.
      4.2 If the neighbours has the `to_word` the shortest ladder is found, return the same
      4.3 Otherwise create new ladder for each neighbour and add it to the end of queue.
  """
  initial_ladder = [from_word]
  pending_ladders_to_explore = deque([initial_ladder])
  visited_words = set([])

  while pending_ladders_to_explore:
    current_ladder = pending_ladders_to_explore.popleft()
    current_word = current_ladder[-1]
    if current_word in visited_words:
      continue
    neighbours = get_neighbours(current_word, WORD_LIST)
    
    if to_word in neighbours:
      return current_ladder + [to_word]
    
    for neighbour in neighbours:
      pending_ladders_to_explore.append(current_ladder + [neighbour])
    visited_words.add(current_word)

  return []

WORD_LIST = [line.strip() for line in open('sgb-words.txt', 'r')]
tests = [
  ['stone', 'money'],
  ['bread', 'crumb'],
  ['smile', 'giant'],
  ['apple', 'zebra'],
  ['other', 'night'],
  ['bread', 'blood'],
  ['black', 'white'],
]

print('| Test ID | From Word | To Word | Length of Ladder | Ladder |')
print('| --- | --- | --- | --- | --- |')
for idx, (word1, word2) in enumerate(tests):
  ladder = create_ladder(word1, word2)
  print(f'| {idx+1} | {word1} | {word2} | {len(ladder)} | {" -> ".join(ladder)} |')

Link to colab

stone->money 12 ['stone', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'money'] bread->crumb 12 ['bread', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'crumb'] smile->giant 12 ['smile', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'giant'] apple->zebra Not found other->night 18 ['other', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', 'night'] bread->blood 5 ['bread', '0', '1', '2', 'blood'] black->white 9 ['black', '0', '1', '2', '3', '4', '5', '6', 'white']

from collections import deque
from typing import List


class WordLadderSolver:
    def __init__(self, words: List[str]):
        self.words = words

    def find_ladders(self, begin_word: str, end_word: str) -> List[List[str]]:
        """
        Find all possible ladders starting from begin_word and ending word

        :param begin_word:
        :param end_word:
        :return: list of ladders
        """
        length = self.word_ladder_length(begin_word, end_word)+1
        # TODO fix it to find all the word ladders

        return [[begin_word] + [str(i) for i in range(length-2)] + [end_word]]

    def word_ladder_length(self, beginWord: str, endWord: str) -> int:
        available_words = set(self.words)

        if endWord not in available_words:
            return 0

        queue = deque([beginWord])
        transformation_length = 1
        while queue:
            transformation_length += 1
            current_level_size = len(queue)
            for _ in range(current_level_size):
                current_word = queue.popleft()
                word_chars = list(current_word)
                for position in range(len(word_chars)):
                    original_char = word_chars[position]
                    for letter_index in range(26):
                        word_chars[position] = chr(ord('a') + letter_index)
                        new_word = ''.join(word_chars)
                        if new_word not in available_words:
                            continue
                        if new_word == endWord:
                            return transformation_length
                        queue.append(new_word)
                        available_words.remove(new_word)
                    word_chars[position] = original_char
        # Nothing found
        return 0

def load_words(filename):
    words = []
    with open(filename) as f:
        words = f.read().splitlines()
    print(f"words = {len(words)}")
    return words

if __name__ == "__main__":
    solver = WordLadderSolver(load_words("sgb-words.txt"))

    test_set = [["stone", "money"], ["bread", "crumb"], ["smile", "giant"], ["apple", "zebra"], ["other", "night"], ["bread", "blood"], ["black", "white"]]

    for a,b in test_set:
        res = solver.find_ladders(a, b)
        print(f"{a}->{b}\n{len(res[0])}")
        for x in res:
            print(x)

[stone, money] has 11 steps

stone -> shone -> shine -> shins -> chins -> coins -> corns -> cores -> cones -> coney -> money

[bread, crumb] has 11 steps

bread -> breed -> freed -> fried -> fries -> pries -> prims -> primp -> crimp -> crump -> crumb

[smile, giant] has 11 steps

smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant

[apple, zebra] has no ladder

[other, night] has 17 steps

other -> otter -> outer -> cuter -> cater -> rater -> raver -> river -> rivet -> revet -> reset -> beset -> beget -> begot -> bigot -> bight -> night

[bread, blood] has 4 steps

bread -> broad -> brood -> blood

[black, white] has 8 steps

black -> blank -> blink -> clink -> chink -> chine -> whine -> white

And a bonus (because test the test data, too):

[money, bones] has 4 steps

money -> honey -> hones -> bones

challenge.htm

<!DOCTYPE html>
<html lang="en"><head>
  <title>Challenge #8</title>
  <script src="challenge.js"></script>
  <style>
button,
input,
textarea {
  display: block;
  margin: 5px 0px;
}
  </style>
</head><body>
  <textarea id="textarea"></textarea>
  <button id="buttonLoad">Load dictionary</button>
  <input id="inputFirst" type="text" maxlength="5" title="First word in ladder" placeholder="first">
  <input id="inputLast" type="text" maxlength="5" title="Last word in ladder" placeholder="last">
  <button id="buttonRun">Run</button>
  <div id="div"></div>
</body></html>

challenge.js

( function () {
  'use strict';

  var
    wordList, // "dictionary"
    neighbor; // sets of 1-letter differences

  // load the dictionary from the textarea
  // find sets of words that differ by one character
  function onLoadClick() {
    var
      d, i, j, k;

    wordList = document.getElementById( 'textarea' ).value.split( '\n' );

    // create an array of arrays of nearest neighbors (1 letter difference)
    neighbor = new Array( wordList.length );
    for ( i = 0; i < wordList.length; ++i ) {
      neighbor[ i ] = [];
    }
    for ( i = 0; i < wordList.length - 1; ++i ) {
      for ( j = i + 1; j < wordList.length; ++j ) {
        d = 0; // "distance" = # of letters that are different
        for ( k = 0; k < 5 && d < 2; ++k ) {
          if ( wordList[ i ][ k ] !== wordList[ j ][ k ] ) {
            ++d;
          }
        }
        if ( d === 1 ) { // difference is 1 letter
          neighbor[ i ].push( j );
          neighbor[ j ].push( i );
        }
      }
    }
    document.getElementById( 'div' ).textContent = 'dictionary loaded';
  }

  // try to find a "ladder" from one word to another
  function onRunClick() {
    var
      // first and last words in the ladder
      wordFirst = document.getElementById( 'inputFirst' ).value,
      wordLast = document.getElementById( 'inputLast' ).value,
      // an array of backward pointers for path discovery
      path = new Array( wordList.length ).fill( -1 ),
      perimeter,     // outer boundary of neighbors
      nextPerimeter, // that expands until we find the last word
      found = false,
      ladder = [],
      i, j;

    i = wordList.indexOf( wordFirst ); // find the first word on the list
    path[ i ] = i;                     // point the start of the path at itself
    perimeter = [ i ];                 // start at the first word
    nextPerimeter = [];

    // check out the neighbors, neighbors of neighbors, etc.
    // until we either find the last word or run out of neighbors
    while ( perimeter.length && !found ) {
      for ( i = 0; i < perimeter.length && !found; ++i ) {
        for ( j = 0; j < neighbor[ perimeter[ i ] ].length && !found; ++j ) {
          if ( path[ neighbor[ perimeter[ i ] ][ j ] ] < 0 ) {
            // if we haven't visited a neighbor before, remember how we got there
            path[ neighbor[ perimeter[ i ] ][ j ] ] = perimeter[ i ];
            // and visit the neighbor the next time through the loop
            nextPerimeter.push( neighbor[ perimeter[ i ] ][ j ] );
            // of course, stop if we find the last word
            found = wordList[ neighbor[ perimeter[ i ] ][ j ] ] === wordLast;
          }
        }
      }
      perimeter = nextPerimeter;
      nextPerimeter = [];
    }

    if ( found ) {
      i = wordList.indexOf( wordLast );
      while ( path[ i ] !== i ) {
        ladder.unshift( wordList[ i ] );
        i = path[ i ];
      }
      ladder.unshift( wordList[ i ] );
      document.getElementById( 'div' ).textContent = ladder.join( ' -> ' );
    } else {
      document.getElementById( 'div' ).textContent = 'Not found';
    }
  }

  // document.ready
  function onContentLoaded() {
    // event listeners for UX
    document.getElementById( 'buttonLoad' ).addEventListener( 'click', onLoadClick );
    document.getElementById( 'buttonRun' ).addEventListener( 'click', onRunClick );
  }
  if ( document.readyState === 'loading' ) {
    document.addEventListener( 'DOMContentLoaded', onContentLoaded, { once: true } );
  } else {
    onContentLoaded();
  }
} () );

I am reminded that UX design is less fun than algorithm design.

Answers

(stone, money)
stone -> shone -> shine -> chine -> chins -> coins -> corns -> cores -> cones -> coney -> money

Path length of 11.

(bread, crumb)
bread -> tread -> triad -> tried -> pried -> pries -> prims -> primp -> crimp -> crump -> crumb

Path length of 11.

(smile, giant)
smile -> stile -> stilt -> stint -> saint -> taint -> taunt -> gaunt -> grunt -> grant -> giant

Path length of 11.

(apple, zebra)
Not possible

(other, night)
other -> otter -> outer -> cuter -> cater -> rater -> raver -> river -> rivet -> revet -> reset -> beset -> beget -> begot -> bigot -> bight -> night

Path length 17.

(bread, blood)
bread -> broad -> brood -> blood

Path length 4.

(black, white)
black -> clack -> click -> chick -> chink -> chine -> whine -> white

Path length 8.

Code

Approach was a simple BFS, finding the neighbours for a word was the harder part.

from collections import deque

DICTIONARY_WORDS = './dictionary.txt'

def main(src, dst):
    with open(DICTIONARY_WORDS, 'r') as file:
        words = [i.strip('\n') for i in file.readlines()]

    wildcards = {}
    for word in words:
        # Neighbours of each word have 1 letter off (or 1 letter as a wildcard)
        for i in range(len(word)):
            wildcarded_word = word[:i] + '*' + word[i+1:]
            if wildcarded_word not in wildcards:
                wildcards[wildcarded_word] = []
            wildcards[wildcarded_word].append(word)

    # Then perform BFS from src to dst
    # Where the neighbours have 1 letter off
    # Once we get a solution its the shortest path as BFS
    queue = deque([[src]])
    visited = set()

    while queue:
        path = queue.popleft()
        node = path[-1]

        if node == dst:
            return path

        visited.add(node)

        # Add all neighbours to queue
        for i in range(len(node)):
            wildcarded_word = node[:i] + '*' + node[i+1:]
            for neighbour in wildcards[wildcarded_word]:
                if neighbour == node or neighbour in visited:
                    continue
                queue.append(path + [neighbour])

    return []

if __name__ == '__main__':
    src = 'black'
    dst = 'white'

    path = main(src, dst)
    path_length = len(path)
    print(' -> '.join(path), path_length)

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/spirit/home/x3.hpp>
#include <fmt/ranges.h>

int main() { 
    boost::iostreams::mapped_file_source file("sgb-words.txt");
    std::vector<std::string_view> words;
    {
        namespace x3 = boost::spirit::x3;
        auto insert  = [&](auto& ctx) { words.emplace_back(x3::_attr(ctx)); };
        x3::parse(file.begin(), file.end(), x3::raw[+x3::graph][insert] % x3::eol);
    }

    std::map<std::string_view, unsigned> index;
    for (unsigned i = 0; i < words.size(); ++i)
        index.emplace(words[i], i);

    // fmt::print("Sample: {}\n", index | v::take(10));

    boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> g(words.size());

    for (auto const [word, src] : index) {
        for (unsigned pos = 0; pos < word.length(); ++pos) {
            for (char subst = 'a'; subst <= 'z'; ++subst) {
                if (subst == word[pos])
                    continue;
                std::string tword(word);
                tword[pos] = subst;

                if (auto it = index.find(tword); it != index.end())
                    add_edge(src, it->second, g);
            }
        }
    }

    // print_graph(g, words.data());
    for (auto [a, b] : { std::pair //
             {"abaca", "aback"},
             {"money", "bones"},
             {"stone", "money"},
             {"bread", "crumb"},
             {"smile", "giant"},
             {"apple", "zebra"},
             {"other", "night"},
             {"bread", "blood"},
             {"black", "white"},
         }) {

        std::vector<unsigned> pred(num_vertices(g));
        std::vector<unsigned> dist(num_vertices(g));
        breadth_first_search(
            g, index[a],
            visitor(make_bfs_visitor(std::pair(record_distances(dist.data(), boost::on_tree_edge()),
                                               record_predecessors(pred.data(), boost::on_tree_edge())))));

        if (auto n = dist[index[b]]) {
            std::deque<std::string_view> path{b};
            for (auto v = index[b]; v != index[a]; v = pred[v])
                path.push_front(words[pred[v]]);
            fmt::print("{} -> {} in {:2}: {}\n", a, b, n + 1, path);
        } else
            fmt::print("{} -> {} not connected\n", a, b);
    }
}

Prints

sehe@workstation:~/Projects/stackoverflow$ time ./build/sotest
abaca -> aback in 2: ["abaca", "aback"]
money -> bones in 4: ["money", "coney", "cones", "bones"]
stone -> money in 11: ["stone", "shone", "shine", "chine", "chins", "coins", "corns", "cores", "cones", "coney", "money"]
bread -> crumb in 11: ["bread", "tread", "triad", "tried", "pried", "pries", "prims", "primp", "crimp", "crump", "crumb"]
smile -> giant in 11: ["smile", "stile", "stilt", "stint", "saint", "taint", "taunt", "gaunt", "grunt", "grant", "giant"]
apple -> zebra not connected
other -> night in 17: ["other", "otter", "outer", "cuter", "cater", "rater", "raver", "ravel", "revel", "revet", "reset", "beset", "beget", "begot", "bigot", "bight", "night"]
bread -> blood in 4: ["bread", "broad", "brood", "blood"]
black -> white in 8: ["black", "clack", "click", "chick", "chink", "chine", "whine", "white"]

real    0m0.043s
user    0m0.039s
sys 0m0.004s

Here's a fairly straightforward implementation in Python

Code is also online here on Github

#!/usr/bin/env python3

from collections import defaultdict, deque
from urllib.request import urlretrieve
import os

# Simple helper to return a list of possible place holders
# for a given word, i.e., (".ne", "o.e", "on." for "one")
def get_placeholders(word):
    for i in range(len(word)):
        yield word[:i] + "." + word[i+1:]

# Load all of the words, putting each word in each possible
# placeholder for that word
words = defaultdict(list)
url = "https://cs.stanford.edu/%7Eknuth/sgb-words.txt"
fn = "sgb-words.txt"
if not os.path.isfile(fn):
    urlretrieve(url, fn)
with open("sgb-words.txt", "rt") as f:
    for row in f:
        row = row.strip()
        for placeholder in get_placeholders(row):
            words[placeholder].append(row)

# And now find the ladders for each given pair:
pairs = [
    ['stone', 'money'],
    ['bread', 'crumb'],
    ['smile', 'giant'],
    ['apple', 'zebra'],
    ['other', 'night'],
    ['bread', 'blood'],
    ['black', 'white'],
]

for start_word, end_word in pairs:
    # Run through a simple A* path finding for going from the start word to
    # the end word, keeping track of all of the words we use along the way    
    stack = deque([(start_word, [start_word])])
    # Don't both using the same word more than once, so track each 
    # word we've used
    seen = set()

    while True:
        if len(stack) == 0:
            # No path from start to end
            print("")
            print(f"{start_word} to {end_word}:")
            print("No ladder found!")
            break

        cur_word, path = stack.pop()
        if cur_word == end_word:
            # We found the word, dump out the path
            print("")
            print(f"{start_word} to {end_word}:")
            print(f"{len(path)} steps for {start_word} to {end_word}")
            print(" -> ".join(path))
            break

        # Add each word from each placeholder to the stack of things to try
        for placeholder in get_placeholders(cur_word):
            for next_word in words[placeholder]:
                if next_word not in seen:
                    seen.add(next_word)
                    # Just to make it obvious which letter is changing
                    changed_letter = placeholder.index(".")
                    changed_word = next_word[:changed_letter] + next_word[changed_letter].upper() + next_word[changed_letter+1:]
                    stack.appendleft((next_word, path + [changed_word]))

stone to money:
11 steps for stone to money
stone -> sHone -> shIne -> Chine -> chinS -> cOins -> coRns -> corEs -> coNes -> coneY -> Money

bread to crumb:
11 steps for bread to crumb
bread -> Tread -> trIad -> triEd -> Pried -> prieS -> priMs -> primP -> Crimp -> crUmp -> crumB

smile to giant:
11 steps for smile to giant
smile -> sTile -> stilT -> stiNt -> sAint -> Taint -> taUnt -> Gaunt -> gRunt -> grAnt -> gIant

apple to zebra:
No ladder found!

other to night:
17 steps for other to night
other -> otTer -> oUter -> Cuter -> cAter -> Rater -> raVer -> rIver -> riveT -> rEvet -> reSet -> Beset -> beGet -> begOt -> bIgot -> bigHt -> Night

bread to blood:
4 steps for bread to blood
bread -> brOad -> broOd -> bLood

black to white:
8 steps for black to white
black -> Clack -> clIck -> cHick -> chiNk -> chinE -> Whine -> whiTe