Programming challenge from "Re: Word games!"

> Bored noblemen and women in my conculture like to sit around playing
> "cethimmethi" (word-mixing).  In cethimmethi, the first player
specifies
> a word, for example, 'raca' (wheel).  The next player must then say a
word
> that adds, deletes, or changes only one letter.  For example, 'rava'
(night)
> or 'traca' (stomach) would both be valid responses.  If a player cannot
think
> of a word, they are out of the game.
This got me wondering--How many words in English are linkable this way?
And how would you find out.  So now I have a project for any of the
programmers in our midst who'd like to help me satisfy my curiosity.
Write a program that, starting from a list of words, determines how many
of them can be linked by adding a letter anywhere (not just the beginning
or end), deleting any letter, or changing any letter.

The basic design of the program could be very simple with a fast database
program.  Start with the first word on the list and run through all of
the possible letter sequences that can be derived from it by adding,
deleting, or changing any letter, and check to see if they are elsewhere
on the list.  For a 5-letter word there are only 291 combinations, so
this wouldn't take too long.  Write down all of the words that are on the
list, and then go to the next word, and so on through the whole list.
Then go back to the beginning and arbitrarily mark the first word as 'A'.
 Then mark all of the words that you found could be derived from it as
'A', then mark all of the words that could be derived from them, etc.
When you're done go to the next unmarked item and mark it as "B", etc.
When you're done, count all of the A's, B's, etc. and you'll have a list
of all of the contiguous sets of words in English that can be derived
from each other.  Obviously there will be one very large set that
contains most of the words in the database, but the interesting thing
will be to see if there are any large sets that are *not* connected to
the main set.

Should be fairly easy to program, though it may take a couple of hours to
run.  I'm not a programmer, but is anyone up for it?


Jesse S. Bangs     Pelíran
jaspax @juno.com
"There is enough light for those that desire only to see, and enough
darkness for those of a contrary disposition."  --Blaise Pascal

Reply