gregr:: Discussion #3 Message : 2004-10-29 03.54.30 peter [Changes]   [Calendar]   [Search]   [Index]   
  [Back to discussion: Word Count]  

Discussion #3 Message: 2004-10-29 03.54.30 peter

Ok, Fred wanted me to give an explanation of the algorithm. Here it is in pseudocode:

countwords( string )  {
   grab a chunk of the string, from left to right, starting with just one character
       if the chunk is a word {
           return 1 + countwords( string without the chunk)
       }
       if there aren't any words that start with the chunk {
           return countwords( string without the first character)
       }
   get a new chunk of the string, adding more to the length of the chunk, unless it reaches the end of the string, in which case it starts over on the string without the first character
}

Yeah, that was harder than I thought it would be. At this point, the actual code is clearer than that, to me at least.

Here's a walkthrough of it working on a particular string:

vjkukurockovgzv

Check v:
        v is not a word, but words can start with v

check vj:
        vj is not a word, and there aren't any words that start with vj

check j:
        j is not a word, but...

check jk:
        jk is not a word, and...

check k:

[...]


check r:
        r is not a word, but words can...

[...]

check rock:
        rock is a word.

check o:
        o is not a word, but words can...

check ov:
        ov is not a word, and there aren't any words that...

[...]

check zv:
        zv is not a word, and there aren't any...

check v:
        v is not a word, but words can...

I'm at the end of the stream.
(last modified 2004-10-29)       [Login]
(No back references.)