'''Line break penalties minimized. simple version only giving penalties.
An important elaboration, lineBreakList.py, would recover linebreaks.
'''
def linePenalties(w, W):
    '''word list w, line width W, return total penalty.'''
    n = len(w)
    p = [0]*n # p[i] is penalty for remaining lines if a line starts at i
    i = n-1
    width = 0
    while i>= 0 and width + w[i] <= W: # keep p[i]=0 while width to end <= W
        width += w[i]
        i = i-1
    # now i is first index where not fit to end
    while i >= 0: # calc p[i] for all indices back to 0
        penalty = 2**64
        width = w[i]
        k = 1  #  k is the number of words on the line
        while width <= W: # try all lengths
            kPenalty = f(W- width, k) + p[i+k]
            if kPenalty < penalty:
                penalty = kPenalty
            width += w[i+k]
            k += 1
        p[i] = penalty
        i -= 1
    print('penalty list:', p)
    return p[0]

def f(x, k): # simple cubic penalty function, ignore k
    return x*x*x

print('best:', linePenalties([6, 4, 7, 9, 4, 5, 4, 10, 3, 7, 4], 17))
s = '''((17 - (6+4))**3 +
       (17 - (7+9))**3 +
       (17 - (4+5+4))**3 +
       (17 - (10+3))**3)'''
g = '''((17 - (6+4+7))**3 +
       (17 - (9+4))**3 +
       (17 - (5+4))**3 +
       (17 - (10+3))**3)'''

print(s, '=', eval(s), 'shows best')
print(g, '=', eval(g), 'greedy')