Doc/Articles/Play204
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
37. Jacob’s Ladder
. By Eugene McDonnell. First published in Vector, 20, 4, (April 2004), 84-97.
And he dreamed, and behold a ladder set up on the earth, and the top of it reached to heaven: and behold the angels of God ascending and descending on it.
Genesis 28:12
Dedicated to my grandson Jacob (15 months old).
The Name of the Game
Lewis Carroll invented a game he called Doublets in 1879. He used doublet to describe two words of the same length, which were to be connected by a chain of other words, called links. Two words are linked if they use the same letters in every position but one, like rota and iota. As an example, he gave as a doublet the words head and tail, and for the links the words heal, teal, tell and tall, so that the entire chain was head, heal, teal, tell, tall and tail. The word Doublet hasn't stuck, however, and the game is now usually called Word Ladders.
The Word Ladder game can be played mentally, and many people enjoy playing in their head, sometimes making it a game for two or more people, to see who can find a ladder quickest. This article, however, treats computer solutions to the problem, which now asks that the chain be as short as possible. There may be more than one shortest solution. For example,
+----+----+ |head|head| |heal|heal| |teal|heil| |taal|hail| |tail|tail| +----+----+
are two solutions shorter by one link than Carroll's. Carroll would probably point out that taal is usually capitalized, in phrases like the Taal ; it is a name for a language, like English or Italian, and is another name for Afrikaans, one of the official languages of South Africa; and heil is a German interjection used infamously by the Nazis in phrases like Heil Hitler. These words let me point out that all the words in my word tables are in lower case, even names like Hugo and Clive ; and that they include numerous words from foreign languages that have gained currency in English, like Russian dvor and Spanish amigo. Different word lists will give different results.
Some doublets give rise to eight or more solutions ' here are the solutions for the doublet white and black.
+-----+-----+-----+-----+-----+-----+-----+-----+-----+ |white|white|white|white|white|white|white|white|white| |whine|whine|whine|whine|whine|whine|whine|whine|whine| |chine|chine|chine|chine|chine|chine|chine|chine|chine| |chink|chink|chink|chink|chink|cline|cline|cline|cline| |chick|clink|clink|clink|clink|clink|clink|clink|clink| |click|blink|clank|clank|click|blink|clank|clank|click| |clack|blank|blank|clack|clack|blank|blank|clack|clack| |black|black|black|black|black|black|black|black|black| +-----+-----+-----+-----+-----+-----+-----+-----+-----+
Later on I'll bring to your attention the ladders for the doublet dvor and lade: there are eighty solutions to it, each nine words long!
My word tables have a history. Many years ago, in our IPSA office in Palo Alto, Joey Tuttle acquired a tape from Houghton Mifflin, the publishers of The American Heritage Dictionary, that contained an alphabetical listing of all the words in their dictionary. Joey extracted a number of files, each file giving all of the words having the same length, and mounted these on the I. P. Sharp computer in Toronto. I found the list useful in a number of ways, and one of the things I did was to write an APL program to form Word Ladders, of which more later. I have these word files now on my personal computer.
Structure of the Game
Looked at from the point of view of the game, a table of words is seen as an undirected graph, where the nodes are the words, and the edges are the links for each word. Linkness is symmetric: if iota is a link of rota, then vice-versa. This being the case, the graph is also symmetric, and the counterdiagonal is all zero - a word is not a link of itself. A word may have many links. For example, bare has 26, using my table. They are:
+----+----+----+----+----+----+----+----+----+----+----+----+----+ |babe|bake|bale|bane|base|bate|barb|bard|bari|bark|barm|barn|bars| +----+----+----+----+----+----+----+----+----+----+----+----+----+ |care|dare|fare|hare|mare|pare|rare|tare|vare|ware|yare|bore|byre| +----+----+----+----+----+----+----+----+----+----+----+----+----+
A word may have no links, as well. Some four-letter hermits are agog, ecru, idol, ugly, xmas, yeti and zarf.
I've adopted some naming conventions. A word list - actually a character table - is called Tn, where n is the length of the words in the table. Thus my four-letter word table is T4. A link list, one that gives the links for each word, is called En. Thus, the link list for four-letter words is E4. Later on, in the discussion of J functions, I'll introduce some more conventions.
The Link List
There's a story to do with the creation of link lists from a word table. I wrote one for myself that took a Tn as argument, and produced the corresponding En. I showed this to Roger Hui, who noted that it had quadratic time. He thought it would be possible to make one that had linear time. At the time of this message we were still calling link lists neighbor lists.
From: rhui000@shaw.ca
Subject: Re: Word Ladders
Date: February 14, 2004 8:10:30 AM PST
To: eemcd@mac.com
There is indeed a much faster, linear, method for generating the neighbors list. The idea is this: for each word, blank out successive letters, and use these blanked out words to match for neighbors. e.g. if the words are abba and abbe,
_bba _bbe
a_ba a_be
ab_a ab_e
abb_ abb_
So if you have a (m,n) matrix of words, in the matching you'd be dealing with a ((n*m),n) matrix and doing linear operations on it, rather than the (m,m,n) outer product.
mlx =: <@I.@(<:@#@[ = +/@|:@:="1)"1 2~ NB. eemcd
mlx1=: [: <@I."1 <:@{:@$ = +/ @: ="1 / ~ NB. eemcd
mlx2=: 3 : 0 NB. hui
'm n'=. $y NB. # of words, # letters
i=. n (* + i.@[ *"1 -.@])=i.n NB. indices for blanking successive positions
t=. ,/ i{"_ 1 y,.'_' NB. blanked words
p=. ,/@:(([ ,. -.~)"0 1)~ NB. verb for pairing
j=. ; t <@p/. n#i.#y NB. group word indices per blanked words
h=. ({."1 </. {:"1) j NB. unordered neighbors
k=. ~. {."1 j NB. word indices corresp. to h
(m{.h-.&.>k) /: k,(i.m)-.k NB. reorder
)
mlx and mlx1 give identical results. mlx2 gives neighbor indices that are unordered, but is otherwise identical. The improved efficiency in mlx2 is more pronounced as the number of words gets large.
alp=: a.{~97+i.26
x=: ~. alp {~ 4000 4 ?@$ #alp NB. table of 4000 'words'
$x NB. 3980 after duplicates removed
3980 4
(mlx -: /:~&.>@mlx2) x
1
(mlx1 -: /:~&.>@mlx2) x
1
ts=: 6!:2 , 7!:2@] NB. to find time and space used
ts 'mlx x'
81.9158 608640
ts 'mlx1 x'
12.1867 8.3887e7
ts 'mlx2 x'
0.490401 1.47846e6
As you can see, for a table of 3980 words, Hui's program is about 160 times faster. That's a lot. It does use twice the space, but it's worth it. I've been happily using mlx2 since to form my link lists. It's always a joy to get instant results rather than "start the process, go out and mow the lawn, then come back and maybe it will be done."
Two Schools of Thought
I'll discuss two different ways of building ladders, given a table Tn, and a links list En. The first way is the standard approach to finding paths in a graph: search forward from one of the words, the starting word, and work one's way through until the other word, the goal word is reached, or it is found that there is no path. This is the approach used in Edsgar Dijkstra's well-known algorithm. The function that uses this forward search I call FL, for 'forward ladders'.
The second way, one I used a quarter-century ago, started searching from both ends of the problem. This can be done because of the problem's symmetry: if I find the shortest path from white to black, I've also found the shortest path from black to white. My intuition told me that a forward search algorithm would take significantly more space, and possibly more time, than a two-way search. Somewhat fortuitously, the two-way search can be identified with the biblical ladder in Jacob's dream, with angels going up and down. Because of this, and in honor of my grandson Jacob, I'll call the two-way search the Jacob's Ladder way, and the associated function JL, for "Jacob's Ladder".
My reasoning was this: Suppose we use FL, starting with a one-by-one matrix, and that there are three links in every item of En. After one step, we have at most a three-by-two matrix; after two a nine-by-three ... and after eight we have at most a 6561-by-9 matrix. Suppose that we have now found the goal. We've looked at 6561 nodes.
If, on the other hand, we use JL, after four iterations forward and backward, we have at most two 81-by-5 matrices, meaning that we have, at most, 162 nodes. In each case we've taken eight steps. The backward steps begin with a node that is necessarily one of the 6561. The next backward step continue with 3 nodes, one of which is in that of the 2187 of the forward search. Likewise, the next backward step finds 9 nodes, one of which is in the 729 of the forward search. Next 27, one included in the 243. By the next step, finding 81 nodes, the forward search has also found 81, and one of the backward 81 nodes must be among the 81 in the forward search. Thus the forward search has worked with 40 times more nodes than the forward and backward search. I had to conclude that it would take less time and less space for the two-way search.
The Case of the Mysterious Test
I wrote FL and JL, tested them, and found that my reasoning was correct, and communicated the results to Roger Hui. His response was dumbfounding. Earlier I had sent Roger a copy of the first fifty words in T4. He generated a two-column table called pairs giving all 1225 combinations of two out of fifty, and used this as the right argument in a timing test. He made the left argument E using mlx2 on the first fifty words. This is what he saw:
$pairs=: 2 comb 50 1225 2 ts 'E FL"1 pairs' 0.94485 1.1991e6 ts 'E JL"1 pairs' 0.90665 1.1991e6
I tried this test on my machine and got the same kind of result: the forward search had essentially the same speed and the same use of space as Jacob's Ladder. This was completely contrary to all the earlier measurements I had made, but I couldn't deny what my own senses told me. For several days I was at a standstill - I had no idea what was wrong with my earlier measurements - or, less likely, whether there was anything wrong with Roger's measurements that I didn't understand.
The Case Solved
There was to be a happy ending however. Roger had earlier told me that he knew a way to do pathfinding that was yards better than mine, and not only that, but would find the shortest paths for all possible pairs. I asked him if he had experimented with this yet. Then this message came:
A few minutes of experimentation with the 4-letter words reviews the fallacy of my approach. The transitive closure of that neighbors list took so long that I interrupted it after about 10 minutes. Further investigation reveals that most words are reachable from most other words. Starting from every way possible generates too much information (and too much redundant information).
If I had to choose, I'd choose the your original FL approach. JL is not sufficiently faster enough to warrant the extra complications.
This was interesting, but still left me baffled by the anomalous timing we both had seen. But then, the same day, came a new message:
Further ... The up-and-down approach is enough faster after all...
ts 'i=: E FL 704 1407' 11.9041 3.04531e6 ts 'i=: E FL2 704 1407' 2.27514 1.66336e6 ts 'i=: E JL 704 1407' 0.881336 515264
The test he now used, timing for the pair 704 1407, was one that had eighty(!) nine-node solutions. The first test above used my original FL; the second used FL2, his rewriting of FL; the third used my original JL. This was very welcome news, but what about those anomalous timings? How explain them? I looked at all aspects of the data and I believe I can now explain it. The anomalous results occurred because the 1st 50 words had no link list longer than 5, and most were 3 or less; the average number of links per node was 1.8; 18 out of the 50 link lists were empty, a very large percentage; thus the timings reflected an atypical set, one in which the up-and-down program couldn't show itself better than the forward search. The best demonstration is to compare the results of a test using E which has only 50 items, with tests using E4, which has 2962 items. Here are the tests using E, showing FL and JL essentially equal in time and space:
ts 'E FL"1 pairs' 0.94485 1.1991e6 ts 'E JL"1 pairs' 0.90665 1.1991e6
The only change in the next tests is using the E4 of 2962 nodes. This averages 8.1 links per node, as many as 31; 91 are empty, only 3.2%. The distribution of links in the first 50 items of E4 is also quite different from that of E. There are 155 links, an average of 3.1 per item, and one has as many as thirteen. Only seven are empty. Here are the tests using E4:
ts 'E4 FL"1 pairs' 674.971 6.14182e6 ts 'E4 JL"1 pairs' 24.1225 2.28742e6
To me, this is conclusive. With this one change, JL is 28 times faster than FL, instead of being equal. It uses less space, less than half as much as FL.
675%24 NB. time ratio 28.125 6.142%2.287 NB. space ratio 2.69
Just for the purpose of this paper I've made some more tests, using both E4 and E5, with right argument 100 random pairs of nodes, with no node repeated. The results are what I have come to expect to get.
Tests of 100 random pairs from T4 and T5, no node repeated,
2004 03 05
$E4 2962 pr4=: 100 2$200?#E4 NB. 200 distinct numbers from i. 2962 f4 =: ts 'E4 FL"1 pr4' j4 =: ts 'E4 JL"1 pr4' f4,:j4 58.3915 4.19264e6 NB. FL numbers 4.08996 2.68454e6 NB. JL numbers f4%j4 NB. ratio of test numbers 14.2768 1.56177 NB. JL 14 times faster, 1.5 times less space $E5 5604 pr5=: 100 2$200?#E5 NB. 200 distinct numbers from i. 5604 f5 =: ts 'E5 FL"1 pr5' j5 =: ts 'E5 JL"1 pr5' f5,:j5 69.0011 2.84186e6 NB. FL numbers 4.43224 843456 NB. JL numbers f5%j5 NB. ratio of test numbers 15.568 3.3693 NB. JL 16 times faster. 3.4 times less space
Function Syntax and Use
The versions of FL and JL I wrote were gone over and tightened up by Roger Hui. Their syntax is:
R =: En FL a,b R =: En JL a,b
Where a and b are indices of words in some Tn. The result is an integer table, where each row is distinct, and the successive values in a row are pairwise links, with first item a and last item b.
] R =: E4 JL 2182 861 2182 628 617 616 589 810 859 861 2182 1505 1483 1455 812 810 859 861 2182 2619 2608 2573 812 810 859 861
To obtain the desired word ladder, use this result as an index to T4:
<"2 T4 {~ R
For example,
<"2 T4 {~ E4 JL 2182 861
+----+----+----+
|rips|rips|rips|
|dips|lips|tips|
|dies|lies|ties|
|died|lees|tees|
|deed|fees|fees|
|feed|feed|feed|
|fled|fled|fled|
|flew|flew|flew|
+----+----+----+
Forward March
The program FL is easier to explain than the more intricate JL.
FL =: 4 : 0
's e'=. y
u=.d=. ,s
c=. ,.s
while. -. e e. d do.
d=. ; v=. (d{x.) -. &.> < u
if. '' -: d do. _1 return. end.
u=. u , ~. d
c=. ((#&>v)#c) ,. d
end.
c #~ e=d
)
The two word indices are s and e. In FL, these signify start and end, but in JL they don't have that mnemonic significance, since they start separate chains. The variable x is the links list, some En.
Variable d is an integer list, initially ,s. It is used to select boxed lists of potential new links. The first time through it gets all the links of s. Next time it gets all the links of those links, and so forth. Variable u contains all of the links already seen. No link appears in u more than once. Initially it is ,s. It is used to ensure that no later use is made of a link that has already been used. This is because once a link is used in any step, there is no point to using it again in a new step - any chain with a later appearance of an earlier link must be longer than one with an earlier appearance.
Variable c is the table of chains, initially with s as its only value. Within the while. loop it will be extended. Each of its rows represents a potential shortest path.
The while. loop continues until d contains e as an item; when it does, it means that one or more shortest paths have been found.
Variable d is used to select boxed lists of links from x . Before further use, each box has removed from it all links that have already been used. These cleaned-up boxes are assigned to v, the raze of which becomes the new link selector list d.
If d is empty, there are no new links, and since e hasn't been found, we'll have to admit that there are no paths between s and e. When this happens, the scalar _1 is returned.
Variable u is updated with all the new links, by appending d to it. Because u should never contain two appearance of the same link, duplicates are removed from d before appending it.
Table c is updated by adding a new column, with the items of d.
When the while. loop ends, a selecting mask is formed by the equality of scalar e and list d, and this mask is used to remove from c all those rows not ending in e. This gives the desired result.
The Angels of God Ascending and Descending
Since JL goes forwards and backwards, there are separate variables for the forward and backward sequences. Instead of c we have sc and ec - two chains; instead of u and d we have su and eu, sd and ed.
The while. is different - it says, effectively, "while forever", since the loop continues as long as the value of the while. phrase is 1. The exiting from the loop will take place by way of if. statements.
JL =: 4 : 0
sc=. ,. su=.sd=. ,{.y
ec=. ,. eu=.ed=. ,{:y
while. 1 do.
if. +./ sd e. ed do. break. end.
if. '' -: sd=. ; v=. (sd{x.) -.&.> <su do. _1 return. end.
su=. ~.su,sd [ sc=. sd ,.~ (#&>v)#sc
if. +./ sd e. ed do. break. end.
if. '' -: ed=. ; v=. (ed{x.) -.&.> <eu do. _1 return. end.
eu=. ~.eu,ed [ ec=. ed ,. (#&>v)#ec
end.
sc join ec
)
The variables ending in u, d and c have the same functions as the u, d and c variables in FL. The first and the last three statements in the while. loop have almost identical structure. With two path tables being built in the same loop, the test for termination is by finding that the same item or items appear in sd and ed. The test for "no path found" is essentially the same as in FL, but there are separate ones for sd and ed. An important difference is that sc is built from left to right, but ec is built from right to left. This makes joining the two easier.
Linking the Chains
When the while. of JL terminates, the fitting together of the two path tables requires some agility. It is complicated enough so that a special join function has been made. It was written by Roger Hui as a rewrite of a joinends function provided to me by R. E. Boss when I sent a message to the J forum explaining the problem and asking for a solution.
join=: 4 : 0
x=. x#~ ({:"1 x) e. {."1 y
y=. y#~ ({."1 y) e. {:"1 x
(({."1 i){}:"1 x) ,. ({:"1 i){y [ i=. (0,#y)#:I.,({:"1 x)=/{."1 y
)
The variables x and y are the forward and backward chains, respectively. We have reached this point because one or more items of the last column of x and the first column of y match. We want to keep only those rows containing these matching items. The first two lines remove from x and y all the rows that don't have matching values in them. I'll invent an x and a y and go slowly through the steps that lead to the desired result.
Here are the two:
x 200 300 400 0 1 130 2 3 120 4 5 130 6 7 120 8 9 130 500 600 700 y 500 600 700 800 130 2 1 0 120 5 4 3 120 8 7 6 120 11 10 9 120 14 13 12 130 17 16 15 900 1000 1100 1200
Only five rows of x and six of y match. First we remove the rows of x that don't end in one of the matching values:
] x=. x#~ ({:"1 x) e. {."1 y
0 1 130
2 3 120
4 5 130
6 7 120
8 9 130
And similarly, remove the rows of y that don't begin with one of the matching values.
] y=. y#~ ({."1 y) e. {:"1 x
130 2 1 0
120 5 4 3
120 8 7 6
120 11 10 9
120 14 13 12
130 17 16 15
Now we have to maneuver to get the rows of x ending in 120 in line with those of y beginning with 120, and similarly for 130. First we compare for equality the tail of each row of x with the head of each row of y:
({:"1 x)=/{."1 y
1 0 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
This is raveled and the indices of 1s found:
I.,({:"1 x)=/{."1 y
0 5 7 8 9 10 12 17 19 20 21 22 24 29
We convert this into their base #y representation.
] i=. (0,#y)#:I.,({:"1 x)=/{."1 y
0 0
0 5
1 1
1 2
1 3
1 4
2 0
2 5
3 1
3 2
3 3
3 4
4 0
4 5
It's another Magical Matrix^[1]^. The first column of i is used to select rows from x and the second to select rows from y.
Use the second column to select rows from y in the right quantity and in the right order:
({:"1 i){y
130 2 1 0
130 17 16 15
120 5 4 3
120 8 7 6
120 11 10 9
120 14 13 12
130 2 1 0
130 17 16 15
120 5 4 3
120 8 7 6
120 11 10 9
120 14 13 12
130 2 1 0
130 17 16 15
and use the first column to select rows of x, at the same time removing the last column; it merely repeats the first column of y.
(({."1 i){}:"1 x)
0 1
0 1
2 3
2 3
2 3
2 3
4 5
4 5
6 7
6 7
6 7
6 7
8 9
8 9
Lastly, stitch these together, and we have the desired result:
(({."1 i){}:"1 x) ,. ({:"1 i){y [ i=. (0,#y)#:I.,({:"1 x)=/{."1 y
0 1 130 2 1 0
0 1 130 17 16 15
2 3 120 5 4 3
2 3 120 8 7 6
2 3 120 11 10 9
2 3 120 14 13 12
4 5 130 2 1 0
4 5 130 17 16 15
6 7 120 5 4 3
6 7 120 8 7 6
6 7 120 11 10 9
6 7 120 14 13 12
8 9 130 2 1 0
8 9 130 17 16 15
And we've matched the three 130s in the last column of x with the two 130s in the first column of y, giving six rows; and matched the two 120s in the last column of x with the four 120s in the first column of y, giving eight rows, which makes fourteen rows altogether. This contrived example shows a solution where there are fourteen different ladders with six links each, giving the links we can use to select the words that make Word Ladders.
Acknowledgements
R.E. Boss provided a workable joining function on the same day that I sent a message to the J forum asking for one. Norman Thompson gave me many ideas about finding paths in graphs. Roger Hui took my ugly ducklings and turned them into beautiful swans, and, by jumping to a conclusion, made it possible for me to understand better the structure of the problem.
Reference
^[1]^ McDonnell, E. E., The Magical Matrix. Vector 20, 2, (2003-08), 122-126.
Errata
The verb comb is used in the article but not defined. Below is a suitable definition, for others see Essays/Combinations
comb=: 4 : 0
c=. 1 {.~ - d=. 1+y-x
z=. i.1 0
for_j. (d-1+y)+/&i.d do. z=. (c#j) ,. z{~;(-c){.&.><i.{.c=. +/\.c end.
)
The list of 50 words from Eugene's word table T4 that he sent to Roger Hui was:
T4=: _4]\ (' ',LF)-.~ ]0 : 0
'tis abba abbe abed abel abet abib able ably abut
ache acid acme acne acre acts acyl adak adam adar
adds aden adit aery afar afro agar aged ages agio
agni agog agra ague ahab ahem ahoy aide aids aims
ainu aire airs airt airy ajar ajax akee akin alai
)
Download all Eugene's zipped Tn files - courtesy of Joey Tuttle.