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