Search for the shortest way to turn a string to another string one character at a time in a given list

Question

Given a list of strings with the SAME length, search for a way to transform a start string to an end string one character at a time such that every transformed string is still present in the list of strings.

INPUTS!
Input starts with T for the number of test cases. Then, in another line comes m asking for the number of strings to put in the list. m lines follow asking for the strings of the same length, and then, the last line consists start and end separated by a space.

Example:

List: ["booster", "rooster", "roaster", "coaster", "coasted"] 
start: roaster
end: booster

Number of String Transformation: 3 (roaster -> rooster -> booster)


List: ["booster", "rooster", "roaster", "coaster", "coasted"] 
start: booster
end: coasted

Number of String Transformation: 3 (booster -> rooster -> roaster -> coaster -> coasted)


List: ["booster", "rooster", "roaster", "coaster", "coasted", "coastal"] 
start: roaster
end: coastal

Number of String Transformation: impossible (roaster -> coaster -> coasted -> x -> coastal)

Output impossible if there is no possible way. Otherwise, output the shortest way to transform.

I made a recursive approach but this cannot find every possible solution since it only tries to change indices that are not equal with the end string which skips some strings that are present in the list that could lead to a possible solution.

My code works for the first example but misses the second one because it does not try out (booster -> rooster -> etc...) since it only sees (booster -> cooster -> coaster -> coasted) as a possible solution. I'm kinda stuck and I don't know how to resolve this. Can someone show me a better approach?

def transformable(word_1, word_2):
    return len([i for i in range(len(word_1)) if word_1[i] != word_2[i]]) == 1

def shortest_transformation(start, end, words):
    queue = [[start]]
    available = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in available if transformable(path[-1], word))
        queue = [path + [word] for word in transformables] + queue
        available = available.difference(transformables)
    return None

T = int(input())

for case in range(T):
    m = int(input())
    words = []
    for inputs in range(m):
        words.append(input())
    
    start, end = input().split()
    
    result = shortest_transformation(start, end, words)
    print(len(result)) if result else print("none")

4
5
booster
rooster
roaster
coaster
coastal
booster coastal
6
booster
rooster
roaster
coaster
coasted
coastal
booster coastal
5
booster
rooster
roaster
coaster
coasted
booster coasted
5
booster
rooster
roaster
coaster
coasted
roaster booster

Output:
none
none
5
3

Answer 1

Here's a suggestion in case you haven't found a solution:

from collections import deque

def transformable(word_1, word_2):
    return len([i for i in range(len(word_1)) if word_1[i] != word_2[i]]) == 1

def shortest_transformation(start, end, words):
    queue = deque([[start]])
    words = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in words if transformable(path[-1], word))
        queue.extendleft(path + [word] for word in transformables)
        words = words.difference(transformables)
    return []

This is kind of a breadth first search (via a LILO/FIFO queue by using the .extendleft() method of deque), which is a good way to search for shortest routes.

For your examples

words = ["booster", "rooster", "roaster", "coaster", "coasted"] 
start = 'roaster'
end = 'booster'
print(shortest_transformation(start, end, words))

words = ["booster", "rooster", "roaster", "coaster", "coasted"] 
start = 'booster'
end = 'coasted'
print(shortest_transformation(start, end, words))

words = ["booster", "rooster", "roaster", "coaster", "coasted", "coastal"] 
start = 'roaster'
end = 'coastal'
print(shortest_transformation(start, end, words))

the output is

['roaster', 'rooster', 'booster']
['booster', 'rooster', 'roaster', 'coaster', 'coasted']
[]

If you don't want to use deque then this should be equivalent:

def shortest_transformation(start, end, words):
    queue = [[start]]
    available = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in available if transformable(path[-1], word))
        queue = [path + [word] for word in transformables] + queue
        available = available.difference(transformables)
    return None