A Random Walk Through Four Letter Words

I got the idea from the longstanding four-letter word display. The original, developed in the early seventies, of necesity uses a very simple algorithm for generating random words.  With modern technology, I felt that I could do something a bit more sophisticated: a random walk through four letter words. 

I started out by downloading an on-line spelling dictionary, and extracting the four letter words.  I wound up with 4776 of them.  Next, I computed which words were adjacent to each other: two words are adjacent if they differ by one letter (snap to knap), or if they are the reverse of each other (paws to swap).  I make my random walk by choosing the next word to display randomly from set of words adjacent to the current one (except that I never choose the next word to be the same one as the previous word). 

One problem is that I have no guarantee that a random walk over these words would be "interesting".  I might start at a word that has no other adjacent words at all.  So, I analyzed the set of words and their adjacencies to find an "interesting subset".  The set of words and their "adjacencies" is an example of a mathematical construct called a "graph".  Therefore I could use graph theory ideas and programs (i.e., the Graph module for Perl) to do my analysis.

First, I eliminated all words which were not adjacent to at least 2 other words.  I repeated this eight times: there were some dead-end paths in the word graph consisting of a string of eight words.  Each time I pruned the word set, I removed the last word in the dead-end path.  I was left with 4439 words.

Next, I wanted to ensure that I could eventually move from any one word to any other -- that is, that the graph is connected.  I found two connected components, one with 4436 words, and one consisting of (tyum, tium, tuum).  Still, I wanted to ensure that the random walk was nicely random, that the graph has "good mixing".  There are a lot of ways to analyze this, but I settled on something simple: there should be no word that seperates two halves of the graph.  That is, I wanted a single "bi-connected component".  I found that there is a big biconnected component with 4413 words, and nine smaller components.  I used the 4413 word component for the walk.

The displays are alphanumeric LED arrays.  I only need to write the character into a register on the module to display it.  I used an Atmel ATMega32 microcontroller to un the program.  There is one problem, though.  While the ATMega32 has 32 Kbytes of flash storage, the word adjacency information requires nearly 128 Kbytes of storage.  I use a 1 Mbit flash eeprom (the small chip) to store the adjacency lists.

New words enter from the top and scroll down, about once every 2 seconds. 

Here are some statistics about the word adjacencies.  The distribution of the number of adjacencies are:

# adjacent	2	3	4	5	6	7	8	9
# words	219	225	253	257	247	278	244	240
# adjacent	10	11	12	13	14	15	16	17
# words	243	233	220	208	187	175	175	164
#adjacent	18	19	20	21	22	23	24	25
#words	167	123	111	109	79	67	57	32
#adjacent	26	27	28	29	30	31	32	33
#words	25	28	19	10	7	3	6	2

The most connected words are

# adjacent	word
33	mins
33	bons
32	pale
32	line
32	bots
32	mine
32	cone
32	pins
31	mare
31	Male
31	lins
30	bare
30	Mars
30	care
30	bart
30	bars
30	core
30	ware