Maximizing the number of lines finishing with the letter r

Question

I was just wondering about a question I had during a previous algorithm test. The question was about a boy writing and essay. He wanted to maximize the number of lines ending in 'r' because he felt that would result in a higher grade on his essay (what...).

Anyways, the essay constraint was that the last 72-80 characters of each line needs to have a letter in it unless including the next word would exceed 80 characters on a line (eg. we can have a line without a letter in 72-80 character spots if adding the next word would make the line have 80+ characters) or it is the last line (last line can have less than 72 characters).

For example, if the constraint was 10-15 instead of 72-80, the formatting would look like this:

123456789012345

The slow blue  
dog is  
entertaining

Is there an efficient algorithm to maximize the number of lines ending in the letter 'r' while maintaining the 72-80 letter constraint? We cannot cut whole words in order to make lines that end in "r".

The algorithm I tried to use did this:

1. Check 72-80 of the current line for letter "r" starting at 72.
2. If there is no letter "r" in 72-80, we just try to fill up the line as much as possible and go to the next line.
3. If there is a letter "r" in 72-80, we would end the line.
4. Repeat 1 until there are no more lines.

The main issue of I have with this greedy algorithm is step 2. Filling up the line as much as possible has the possibility of perventing a future line of ending in "r".

Using this algorithm with a 10-15 constraint would get:

123456789012345
The man was in 
the backgarden  
or the yard

But the optimal solution would be:

123456789012345
The man was 
in the 
backgarden or 
the yard

:(

Answer 1

This can be done with a dynamic programming solution.

Give each word in the text a score, which is the maximum number of lines ending with 'r' possible if the text started with that word (i.e. if you removed everything before it).

So for example, the last word's score would be 0 or 1 (depending if it ends with 'r'). The first word's score is the answer you need.

Calculate the scores by going over the words from last to first. For a given word, analyze all possibilities to create the first line. For a given possibility, the score will be the score of the first word in the second line, plus 1 if the first line ends in 'r'. The given word's score will be the score of the best possibility.

Using the example text, "The man was in the backgarden or the yard":

yard: score 0
the: score 0
or: score 0 (only possibility for first line is "or the yard")
backgarden: score 1 (there are two possibilities for first line, the better one
                     is "backgarden or" which gives the score of "the" plus 1).
the: score 0 (only possibility for first line is "the backgarden")
in: score 1 (first line is "in the" which gives the score of "backgarden")
was: score 1
man: score 1 (first line is either "man was in" or "man was in the". The second
              option gives the score of "backgarden" which is 1.
The: score 1 (best first line is "The man was" which gives the score of "in").

After having calculated the scores, to construct the best line-separated text, you start at the first word, choose the best possibility for the first line (as above), and repeat with the first word of the next line.