Need help devising solution to calculating the "penalty" of a word wrap function

Question

I have a program that recursively computers a word wrap to a specified line length.

def wrap(input, lineSpaces):
    if len(input) <= lineSpaces: # Base case
        return input
    temp = input.rfind(" ", 0, lineSpaces - 1) # Parsing
    if temp == -1:
        return input
    else:
        prev = input[:temp+1]
        next = wrap(input[temp+1:], lineSpaces)
        wrap.penalty = (lineSpaces-len(prev)+1)**3 +(lineSpaces-len(next)+1)**3 # Penalty calculation
        return prev+'\n'+next


# I/O
list = []
penalties = []
M = int(raw_input())
for i in xrange(0, M):
    lineSpaces = int(raw_input())
    input = raw_input()
    list.append(wrap(input, lineSpaces))
    penalties.append(wrap.penalty)


for i in xrange(0, len(list)):
    print "penalty: ", penalties[i]
    print list[i]+"\n"

With the following input:

3
20
This is the first paragraph that you need to print
30
This is another paragraph that you need to print and it ends in a very long word onetwothreefourfivesixseven
36
This paragraph all fits on one line

I expect the output:

penalty: 35
This is the first
paragraph that you
need to print

penalty: 216
This is another paragraph
that you need to print and 
it ends in a very long word
onetwothreefourfivesixseven

penalty: 0
This paragraph all fits on one line

However, I actually get the output:

penalty:  -1701
This is the first 
paragraph that you 
need to print

penalty:  -148752
This is another paragraph 
that you need to print and 
it ends in a very long word 
onetwothreefourfivesixseven

penalty:  -148752
This paragraph all fits on one line

So as you can see, my penalty outputs are wrong. I want to calculate my penalties as the sum of (lineSpaces-len(line)+1)**3 for all lines in each paragraph, except for the final line of each, which has a penalty of 0. It seems that each call to (lineSpaces-len(prev)+1)**3 for every paragraph (except the last, which should be 0) returns the correct value. What is wrong in my logic?

Answer 1

Your calculation of the penalty is wrong in a few ways. First, you set next equal to the return value of the recursive call. This is still as long as the original, or longer, since all you did was add linebreaks to it. But you calculate the penalty on this. On every call, you are calculating the penalty of what that call fits onto one line to the penalty of everything else that is passed to the next recursive call.

In addition, because you store this value on wrap.penalty, you overwrite it after every call. Since you never do anything with the old values of wrap.penalty, you ignore all calculations except the last one.

Using function attributes to store data like this is a dangerous game. There is only one wrap, and so only one wrap.penalty, so it's not like each recursive call gets its own version of penalty; they are all stomping on the same one. Instead of storing the value in wrap.penalty, it is probably better to just return it along with the wrapped text, like this:

def wrap(instr, lineSpaces):
    if len(instr) <= lineSpaces: # Base case
        return instr, 0
    temp = instr.rfind(" ", 0, lineSpaces - 1) # Parsing
    if temp == -1:
        return instr, 0
    else:
        prev = instr[:temp+1]
        next, penalty = wrap(instr[temp+1:], lineSpaces)
        penalty += (lineSpaces-len(prev)+1)**3 # Penalty calculation
        return prev+'\n'+next, penalty

Then:

>>> wrap("This is the first paragraph that you need to print", 20)
('This is the first \nparagraph that you \nneed to print', 35)

On each call I add the penalty returned from the recursive call to the penalty calculated for the line I just parsed. You could also calculate the penalty in a separate step after the wrapping, as Pham Trung suggests in a comment.

I also changed your variable name from input to instr. You should avoid using the name input as there is a builtin function by that name. (For the same reason, list is not a good name for a variable either.)