Late to the party, here is some code to solve the path between each word, just requires numpy and a txt file of 4 letter words "words.txt" separated by lines
import numpy as np
with open("words.txt") as f:
words = f.read().splitlines()
f.seek(0)
chars = np.array(list(ord(c) for c in f.read() if c != '\n')).reshape((-1, 4))
word_to_index = dict(zip(words, range(len(words))))
char_flip = np.sum(chars[:, None, :] != chars[None, :, :], axis=2) == 1
chars_sorted = np.sort(chars, axis=1)
char_shuffle = np.all(chars_sorted[:, None, :] == chars_sorted[None, :, :], axis=2)
adj = char_flip | char_shuffle
np.fill_diagonal(adj, False)
# import itertools
def path_recursive(current, end, adj, path, depth):
if depth <= 0:
return []
if current == end:
return [[*path, end]]
# all_paths = []
for neighbor in adj[current]:
if neighbor in path:
continue
_path = path_recursive(neighbor, end, adj, [*path, current], depth - 1)
# all_paths.append(_path)
if _path:
return _path
# return list(itertools.chain(*all_paths))
return []
def binary_shortest_dist(start, end, adj):
depth = 1
adj_n = np.eye(adj.shape[0])
while depth < 20:
depth += 1
adj_n = adj_n @ adj
if adj_n[start, end]:
return depth
def path(start, end, adj):
start = word_to_index[start.upper()]
end = word_to_index[end.upper()]
depth = binary_shortest_dist(start, end, adj)
print(depth)
adj = [[i for i in np.nonzero(_adj)[0]] for _adj in adj]
paths = path_recursive(start, end, adj, [], depth)
return [[words[i] for i in path] for path in paths]
path("disc", "zero", adj)