Background

A word ladder is a sequence of words in which every word in the sequence shares exactly n-1 letters with the previous word (and in the same positions). For example,
road-read-reed-seed-weed
When I took Data Structures, our final project was to write a program to generate word ladders from words with 4 letters, and also from words with 5 letters. I realized it was a graph theory project and implemented the project using an Adjacency Matrix data structure. From my C++ text output code, I could print out the Adjacency Matrix as a sparse binary matrix; however, I later realized the potential of the Wolfram Language in better visualizing the underlying graph. In this post I introduce one implementation of word ladders in the wolfram language, as well as several ways of visualizing their underlying graphs.

Creating the word list

Variables in this program are in camelCase to avoid conflicts with WL's builtin symbols, which usually start with capital letters.
n is the number of letters in each word.
In[]:=
ClearAll["Global`*"]​​n=4;​​wordsNLetters=Select[WordList[],#==ToLowerCase[#]&&StringLength[#]==n&];​​Length[wordsNLetters]
Out[]=
1910
Since there are too many 4-letter words for this program to run on most systems in a reasonable amount of time, I created a new list "words" which takes every m-th word from wordsNLetters. If you have a supercomputer, feel free to set m=1, which will include every word.
In[]:=
m=6;​​words = wordsNLetters[[;; ;; m]];​​l=Length[words]
Out[]=
319

Distance between two words

Now we want to define some functions to determine how many letters are different in two words.
wordDist gives you Word Ladder distance between two words, the number of letters that need to be swapped out from word to get another. The word ladder distance of a word and itself is zero. An interesting future project might investigate the Manhattan Distance between two word vectors.
In[]:=
wordToVector[a_] := Flatten[ToCharacterCode /@ StringSplit[a, ""]] - 97​​wordDist[a_,b_]:=Total[(Boole[#1≥1]&)/@Abs/@(wordToVector[b]-wordToVector[a])]

Calculating the Adjacency Matrix

Here I am defining two matrices. matBool is the adjacency matrix which connects two words if and only if their word ladder distance is equal to 1. matDist is another matrix not used in the actual computation of word ladders, but which is a useful visualization tool which provides insight into the patterns we see in the ArrayPlot of matBool.
In[]:=
matBool = Table[If[wordDist[words[[x]],words[[y]]]==1,1,0],{y,1,l},{x,1,l}];​​matDist = Table[wordDist[words[[x]],words[[y]]],{y,1,l},{x,1,l}];
Looking at some sub-matrices of matBool and matDist, we can observe a few things. For one thing, each is a symmetric matrix that is equal to its transpose. This is because the wordDist function we defined is commutative / symmetric. i.e. wordDist(a, b) = wordDist(b, a). A symmetric adjacency matrix represents an undirected graph. Also if note is that there is a relatively low density of connections between the words as seen in the wordDist matrix.
In[]:=
Grid[{{​​matBool[[13 ;; 33, 13 ;; 33]] // MatrixForm,​​matDist[[13 ;; 33, 13 ;; 33]] // MatrixForm​​}}]
Out[]=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
2
2
2
2
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
2
0
2
1
2
2
3
3
3
3
2
3
3
2
3
3
3
3
3
3
3
2
2
0
2
2
2
3
3
1
3
3
3
3
3
3
2
3
3
3
3
3
2
1
2
0
2
2
3
3
3
3
2
3
3
2
3
3
3
3
3
3
3
2
2
2
2
0
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
0
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
0
1
2
2
3
2
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
1
0
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
1
3
3
3
2
2
0
2
3
3
3
3
3
2
3
3
3
3
3
2
3
3
3
3
3
2
2
2
0
3
3
3
3
3
3
3
3
3
3
3
3
2
3
2
3
3
3
3
3
3
0
3
3
2
2
3
3
3
3
3
2
3
3
3
3
3
3
2
3
3
3
3
0
2
3
3
3
3
3
2
3
2
3
3
3
3
3
3
3
3
3
3
3
2
0
3
3
3
2
3
3
3
3
3
2
3
2
3
3
3
3
3
3
2
3
3
0
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
2
0
2
2
2
3
3
2
3
3
2
3
3
3
3
3
2
3
3
3
3
2
2
0
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
0
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
1
0
3
3
3
3
3
3
3
3
3
2
3
3
3
3
2
3
3
3
3
3
3
0
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
0
3
3
3
3
3
3
3
3
3
3
3
2
2
3
3
2
3
3
3
3
3
0
Things get even more interesting when we make grayscale plots of the entire matrices. Of note is not only the diagonal symmetry, but also higher density of connections near (but not on) the diagonal. This is because words close together in alphabetical order are more likely to have a word ladder distance of 1. For example: fast and fact, or ward and wary. If words were allowed to connect to themselves (the only case of a word ladder distance of zero), then there would be a solid diagonal black line across the entire array plot of matBool.
​
In the array plot of matDist, we see the expected diagonal symmetry and density of low word ladder distances near the diagonal, but there are also some mysterious square and rectangle shapes on the diagonal and throughout the plot. The square shapes on the diagonal occur when consecutive words all have the same word ladder distance to each other, and the other rectangle shapes occur when a group of consecutive words all have the same distance to a certain other sequence of alphabetically consecutive words.
Future research might investigate what patterns appear in word ladder adjacency matrices when the vertices sorted by orders other than alphabetical.
In[]:=
ArrayPlot[matBool, ImageSizeLarge]​​ArrayPlot[matDist, ImageSizeLarge]
Out[]=
Out[]=

Graphs from Matrices

Now that we've seen what the adjacency matrix looks like, let's see what the graph it represents looks like! “graph” is the actual graph generated from the adjacency matrix matBool.
In[]:=
graph = AdjacencyGraph[matBool,VertexLabels"Name"];​​graph = VertexReplace[graph,Table[xwords[[x]],{x,1,l}], GraphLayout"SpringEmbedding"]
Out[]=
Yuck! The isolated vertices at the bottom of my graph are crowding the image and making it illegible. graphConnected is an attempt to make graph into a “more connected” graph . A connected graph is a graph in which at least one path exists between every two vertices. An attempt was made to use VertexDelete to remove vertices with 1 or 0 edges, which do not typically make for very interesting looking graphs .
Much better. As you can see there are still a few vertices which have zero neighbors, and a few sub-graphs which only have one edge. Removing these may be the subject of future word ladders research.
Out of curiosity, I made an ArrayPlot of graphConnected to see what it looked like, having fewer isolated vertices and thus a higher connection density. As expected, it looks similar to the original array plot of matBool, and furthermore, it shows that AdjacencyGraph and AdjacencyMatrix function as inverses of each other, as they should.

Graph layouts

The Wolfram language has many powerful tools for working with graphs, and drawing the same graph over and over again with different GraphLayout values is never a waste of time! I used VertexReplace[] to swap out the GraphLayout option in our final graph.
Paths in the graphs pictured below are all word ladders. Visualizing graphs is much easier in WL than in C++ text output, and you can see multiple instances of word-cycles, word-simplicies, word-trees and other mysterious graph varieties in the graphs generated.

CITE THIS NOTEBOOK

Generating word ladders using adjacency matrices​
by Chase Marangu​
Wolfram Community, STAFF PICKS, June 1 2023
​https://community.wolfram.com/groups/-/m/t/2928331