Re: [FWP] A heftier challenge for y'all

["Bernie Cosell" <bernie@fantasyfarm.com>]

On 20 Jul 99, at 10:01, John Porter wrote:

> You've probably seen the word puzzles that involve transforming one
> word into another by changing one letter at a time, e.g. 'solar' into
> 'oasis' in 12 steps (single-letter changes).  Considering the words of
> a lexicon as nodes, and single-letter changes between pairs of words
> as edges, the general problem is to find all the graphs; each graph
> is a network of words which can be transformed into each other in
> some number of steps.  The distance between any two words in a graph
> is the number of changes required to transform one into the other.
> If there is more than one path -- as there will be, for example, if
> there are any cycles in the graph -- then for the purposes of this
> puzzle we only consider the shortest one.  So, in general, for any
> two words in the lexicon, if there is a "shortest path distance" between
> them -- or no path at all.  The specific problem, then, is this: to find
> the pair of words with the *longest* such "shortest path".

Well, this proved to be a fairly hard problem!!  I have a program to do 
the search and it is about 150 lines long [including comments, white 
space, etc].  And it isn't hardly 'fun' at all..:o)

> Of course, you can consider words of length 6 instead; you may even wish
> to make this number parametric to your program.

My program does that.

A followup to this [forget who it was from] said that they had a solution 
that is O(n^2).  I wonder how they managed that...  Ignoring access times 
[e.g., whether the time to access an element of a hash is linear, a 
constant, or some other function of the length of the hash], I have a 
solution that is slower than n^2 but ought to be a good deal faster than 
n^3:  If there's a trick for doing the search that doesn't involve 
checking EACH from->to pair [which is o(n^2) all by itself!] I'd love to 
hear about it!!  [once you have to search all n^2 pairs, you only have 
time for a _constant_ amount of work [e.g., no list-chasing or anything 
like that] if you're going to stay o(n^2), so either you have to find 
some faster way to do the outer loops, or you need to do some REALLY 
clever pre-computing so that the innermost loop doesn't have to 
search...]

My program runs in two phases, with the key junction between them being a 
hash-of-arrays giving the "immediate precedence" for the wordlist:        

    $words{wd}[]  is an array of every word you get get to from
                  word 'wd' by changing a single letter

The first phase builds it, the second uses it to chase out the ladder 
between each possible pair of words.  So the running time is 
O(n^2)*<average ladderlength>.  I haven't a *CLUE* how to evaluate that, 
other than to guess that it is some lower-order power of the length of 
the list.

I'll be happy to post the program here, if anyone wants to see it, 
although it is sort of the antithesis of the "can you squeeze out one 
more char" one-liners we usually play with...

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com     Pearisburg, VA
    -->  Too many people, too few sheep  <--          


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe