[ajug-members] Geek Challenge
jtalafous at lycos.com
Mon Oct 24 16:33:41 EDT 2005
>From a theoretical CS perspective, we are writing a very general compiler. This problem is well-researched by academics. Essentially, we are defining a Language with a Grammar which can be represented with a Parse Tree. The Parse Tree can be constructed top-down or bottom-up, depending on your Production rules. Our compiler will determine whether the input string is a member of our Language; if it is in the Language, then we can count the Words meaningfully.
Given a string of length N, how many non-overlapping substrings of at least length one exist? How many ways can we partition a string of length N? This function is non-polynomial, but how fast is it going to shoot up into intractibility?
As momma said, algorithms are fun... until someone loses their eye. ;o
----- Original Message -----
From: "Dan Glauser" <danglauser at yahoo.com>
To: ajug-members at ajug.org
Subject: [ajug-members] Geek Challenge
Date: Fri, 21 Oct 2005 12:28:00 -0700 (PDT)
> 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
> 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!
> danglauser at yahoo.com
> ajug-members mailing list
> ajug-members at ajug.org
Search for businesses by name, location, or phone number. -Lycos Yellow Pages
More information about the ajug-members