[ajug-members] Geek Challenge

[J. Talafous]

>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.

http://en.wikipedia.org/wiki/Parsing
http://en.wikipedia.org/wiki/String_searching_algorithm

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
> 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


-- 
_______________________________________________

Search for businesses by name, location, or phone number.  -Lycos Yellow Pages

http://r.lycos.com/r/yp_emailfooter/http://yellowpages.lycos.com/default.asp?SRC=lycos10