Re: Programming challenge from "Re: Word games!"

Jesse Bangs wrote:

> 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.
Done. It took about an hour to write the programs in Perl and about 2
minutes for the final run.

I used the Linux /usr/share/dict/words dictionary, which has
45424 words in my version. Stripping all non-common words
(those which contained anything other than a-z) left 38633 words.

The first program, onestep, determined all the valid one-letter
transitions (from a known word to another known word by adding,
deleting, or changing one letter): there were 93354 of these
(counting dump->jump and jump->dump separately), involving 26815
distinct words.  So already 11818 words cannot participate in
the game.

The chains program created the chains using your algorithm,
which BTW is called "topological sort". It is useful for
converting a partial ordering into a total one. (Actual
toposort algorithms complain if there is a loop, whereas
this version just ignores loops.) There were 5715 distinct
chains, of which the largest contained 11633 words.

The sizes of the remaining chains are indicated by this table:

Count   Size
=====   ====
1       11633
1       48
1       28
1       25
1       21
2       19
4       18
4       17
4       16
4       15
5       14
2       13
5       12
7       11
14      10
16      9
28      8
34      7
87      6
221     5
308     4
990     3
3975    2

Programs including a brute-force, non-shortest-path solver) and their
output available on request.
--
Not to perambulate             || John Cowan <jcowan@...>
    the corridors               || http://www.reutershealth.com
during the hours of repose     || http://www.ccil.org/~cowan
    in the boots of ascension.  \\ Sign in Austrian ski-resort hotel