[ajug-members] Geek Challenge

[Rob Kischuk]

I'm just thinking aloud (over email), but one solution I might hack 
around with if I were actually trying to build this is to define my 
entire dictionary in a tree, where the root node has 26 children - one 
for each letter.  From there, each child node has a child node for each 
character that can follow that letter and still form a word, each node 
has a link to its parent node, and a flag indicating whether it can be a 
terminal node (does following the path from the root down to this point 
spell a word?).

The other structure would be a solution tree, where the root node has N 
children, each child representing a word that can be formed starting 
with the first letter of the phrase. 

It would begin by walking the dictionary tree for all possible initial 
words (or for a single solution search, search deeper into the tree as 
each initial word is found).  Then for each possible initial word, it 
would start over from the top of the dictionary tree for the next 
subsequent characters in the phrase, repeating this until you get to the 
end of the phrase.  If you're walking down the dictionary tree and run 
out of letters before arriving at a completed word, the parent node 
should be removed.  As you are walking back up the solution tree, if you 
find a node that has no children, remove it.  Once you've tried this for 
all parts of the tree, you'll have a completed solution set.

An easy optimization would be to keep a short list of dead indexes - 
positions where if we start there, we can't create a valid sequence of 
words.  A better optimization would be to ensure that you only walk the 
tree from a given position in the string once, such that for a phrase 
godisnowhere<followed by additional letters/words>, both initial 
solutions "god is now here" and "god is nowhere" point to the same 
subsequent solution tree.  A possible

This will give you a result tree that covers the entire set of possible 
solutions.  If you just want a solution, you could just stop at the 
first complete solution.  It would be interesting (if not 
time-consuming) to see if a reverse dictionary (start the search from 
the end of the string over a dictionary tree that spells words 
backwards) is more effective than a forward dictionary.

Maybe it's a bad idea, maybe there's something better.  It's just one 
thought.  Feel free to poke holes in it.

-Rob

Dan Glauser wrote:

>Are there any computer scientists in the house? 
>Mathematicians?  Hard core geeks?  I know you are out
>there.....
>
>I'm looking to discover, devise, or some how come up
>with an algorithm to find ideal full decomposition of
>a non delimited string into words.  Some simple
>examples:
>
>ariverrunsthroughit   =>  a river runs through it
>
>cookinguniversity  =>  cooking university
>
>p1ecesofpie    =?  ?????? of pie =>  no match
>
>8675rarara   =?  ???? ra ra ra  => no match, must
>completely break down the string into words
>
>Some more interesting examples:
>
>booksugar  =>  book sugar
>This is interesting because we don't want to make the
>mistake of:
>
>booksugar =?  books ????  =>  no match
>
>This is a common issue with the algorithms I've been
>trying so far.
>
>goodstart  =?  good start || goods tart
>Which is it?
>Please note for the problem I am trying to solve it is
>more important to get the total number of words that
>fully fit the string so in this case it doesn't as
>much matter which strings are picked as long as the
>ones picked cover the entire string.
>
>Make sense?
>
>There are tons of more difficult examples that I've
>been feeding into different algorithms, I hesitate to
>cloud the AJUG list with them.  If you like this type
>of challenge and/or are good with computer
>science/math then I would appreciate taking the
>discussion offline hearing your input.  Once a
>solution is found I'd be happy to post the results to
>the list.  This probably mirrors a classic CS problem
>used to solve xxxx, I'm just not seeing it and would
>like another set of eyes and someone to discuss
>different approaches with.
>
>If your help leads to a solution then I see a free
>dinner in your future......
>
>Come on, algorithms are fun!
>
>:)
>
>--
>Dan
>danglauser at yahoo.com 
>_______________________________________________
>ajug-members mailing list
>ajug-members at ajug.org
>http://www.ajug.org/mailman/listinfo/ajug-members
>  
>