[ajug-members] Geek Challenge
rkischuk at gttx.org
Sat Oct 22 16:27:05 EDT 2005
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.
Dan Glauser wrote:
>Are there any computer scientists in the house?
>Mathematicians? Hard core geeks? I know you are out
>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
>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
>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.
>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!
>danglauser at yahoo.com
>ajug-members mailing list
>ajug-members at ajug.org
More information about the ajug-members