[ajug-members] Geek Challenge

[Bruce Goodwin]

What about words like "cabin"?
cabin => cab in

Then, of course, words that can be decomposed into valid smaller words
will inevitably appear in larger strings:

logcabin => log cabin
or
logcabin => log cab in

Do you want all possible results or just the first valid one?

On 10/21/05, Dan Glauser <danglauser at yahoo.com> 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
>