As I always put below, the proper ways to respond to this are to make a GitHub issue or to tweet at me. (If you know my email address or bump into me on the street, I suppose that’s also okay…) My friend `@tjmcgrew` picked up the challenge and put together a solution that was much faster than the minutes that my solution had previously taken minutes to finish.

A skim of his code didn’t make it obvious to me what was going on, so of course I had to reimplement it in a language of my choice (Perl) to understand it.

His Code:

``````#!/usr/bin/env python3

from sys import argv
from collections import deque, defaultdict

DICTFILE = "/usr/share/dict/words"

def get_words(length):
words = []
with open(DICTFILE, 'r') as dictfile:
for i in dictfile:
i = i.strip()
if len(i) == length and i.isalpha() and i.islower():
words.append(i)
return words

def diffcount(s,t):
count = 0
for x,y in zip(s, t):
if x != y:
count += 1
return count

def find_shortest_path(graph, start, end):
dist = {start: [start]}
q = deque([start])
while len(q):
at = q.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = [dist[at], next]
q.append(next)
return flatten_result(dist.get(end))

def flatten_result(result):
while isinstance(result, list):
result = result + result[1:]
return result

def main():
start = argv
end = argv
graph = defaultdict(lambda: [])
if len(start) != len(end):
print(f"{start}({len(start)}) and {end}({len(end)}) are not the same "
"length!")
return
wordlist = get_words(len(start))
if start not in wordlist:
print(f"{start} is not a word")
return
if end not in wordlist:
print(f"{end} is not a word")
return

graph[start] = [w for w in wordlist if diffcount(w, start) == 1]
fail = False
while not fail:
fail = True
for k,v in [*graph.items()]:
for word in v:
if word not in graph:
fail = False
graph[word] = [w for w in wordlist if diffcount(w, word) == 1]
if end in graph[word]:
print()
path = find_shortest_path(graph, start, end)
if path:
print(' -> '.join(path))
return
else:
fail = True
print("No path found")

if __name__ == '__main__':
main()
``````

The great and wonderful win, I believe, is using `diffcount` instead of Levenshtein to count the differences between words. “yeah I started out with Levenshtein but I realized that I really only needed to know how many letters were different since we know both words are the same length.” This is true, except it could drop to boolean, returning `1` if the distance is `1` and `0` if not. Oh well, this is fine.

I believe, however, there’s a lot in there that isn’t necessary, because he’s doing something different with `graph`. In standard Shortest Path (by the algorithm I read), the graph has the child point to parent. If we’re going from `code` to `mood`, `mood` would point to `mold`, which would point to `mole`, to `mode` then to `code`. McGrew instead points `code` to every word one letter away from it, and so on. Then, when he finds that he has enough in his graph to solve the thing, he then passes the whole thing to `find_shortest_path` and solves it over again.

I mean, that’s a pretty cool way to limit the scope of the loop and remove a lot of “that’s never gonna work” entries, but it leaves the solution on the table. My “reimplementation” creates the parent graph, representing each individual edge on the graph.

``````    \$graph->{\$w}->@* =
grep { 1 == diffcount( \$w, \$_ ) } @wordlist;
map      { \$parent->{\$_} = \$w }
grep { \$_ ne \$start }
grep { !\$parent->{\$_} } \$graph->{\$w}->@*;
``````

Of course, if you’re not careful to keep out that starting word, you will end up with a loop.

Anyway, here’s my code:

``````#!/usr/bin/env perl

use strict;
use warnings;
use feature qw{ say signatures state };
no warnings qw{ experimental };

\$! = 1;
main();

sub get_words( \$length ) {
my \$file = "/usr/share/dict/words";
if ( -f \$file && open my \$fh, '<', \$file ) {
my @words =
sort { rand 1 <=> rand 1 }
grep { \$_ eq lc \$_ }
grep { !/\W/ }
grep { length \$_ == \$length }
map  { chomp \$_; \$_ } <\$fh>;
close \$fh;
return @words;
}
exit;
}

sub diffcount ( \$s, \$t ) {
my \$count = 0;
for my \$i ( 0 .. -1 + length \$s ) {
\$count++ if substr( \$s, \$i, 1 ) ne substr( \$t, \$i, 1 );
}
return \$count;
}

sub main {
my ( \$end, \$start ) = @ARGV;
my \$graph  = {};
my \$parent = {};
if ( length \$start != length \$end ) {
say q{Input lengths are not the same};
exit;
}
my @wordlist = get_words( length \$start );
if ( !grep { /\$start/ } @wordlist ) {
say qq{\$start not in wordlist};
exit;
}
if ( !grep { /\$end/ } @wordlist ) {
say qq{\$end not in wordlist};
exit;
}
\$graph->{\$start}->@* = grep { 1 == diffcount( \$start, \$_ ) } @wordlist;
map { \$parent->{\$_} = \$start } \$graph->{\$start}->@*;
my \$fail = 0;

while ( !\$fail ) {
\$fail = 1;
for my \$k ( keys \$graph->%* ) {
my @v = \$graph->{\$k}->@*;
for my \$w (@v) {
if ( !\$graph->{\$w} ) {
\$fail = 0;
\$graph->{\$w}->@* =
grep { 1 == diffcount( \$w, \$_ ) } @wordlist;
map      { \$parent->{\$_} = \$w }
grep { \$_ ne \$start }
grep { !\$parent->{\$_} } \$graph->{\$w}->@*;
if ( grep { /\$end/ } \$graph->{\$w}->@* ) {
say 'OK';
my \$x = \$end;
print qq{  \$x };
while ( \$parent->{\$x} ) {
\$x = \$parent->{\$x};
print qq{-> \$x };
}
say '';
exit;
}
}
}
}
}
say 'No Path Found'
}
``````

I think I could almost take out everything related to `\$fail` as well, but it’s working and not mission critical, so eh?

However:

`````` time ./mcgrew_solver.pl judge dread ; echo ;time ./mcgrew_l
OK
judge -> budge -> bulge -> bulgy -> bully -> dully -> dolly -> doily -> drily -> drill -> trill -> trial -> triad -> tread -> dread

real    0m20.991s
user    0m19.734s
sys     0m0.109s

judge -> budge -> bulge -> bulgy -> bully -> dully -> dally -> daily -> drily -> drill -> trill -> trial -> triad -> tread -> dread

real    0m10.210s
user    0m9.203s
sys     0m0.109s
``````

I’m way down from minutes, but my Perl runs twice as slow as his Python, so that needs work.