DP Text justification.

gistfile1.py

too_large  = 1e12
def violations(words, page_width):
    """
    The greater this is the worst the worst is the violation.
    TODO(Sid): abs??
    """
    cost = page_width - (sum(len(i) for i in words) + len(words) - 1)
    if cost < 0:
        return too_large
    else:
        return cost ** 2

def justify_text(words, L):
    """
    Dynamic programming
    """
    mins = {}
    m = {}
    m[0] = 0
    num_words = len(words)
    s = {}
    # O(n^2) total time:
    # O(n) space.
    for i in xrange(1, num_words + 1):  # Start at word 1
        mins = {}
        # 1, 2, 3, ... n subproblems to solve each time 
        for k in xrange(i, 0 , -1):
            violation = violations(words[k-1 : i], L)
            if violation is not too_large:
                mins[m[k-1] + violation] = k
            else:
                break
        m[i] = min(mins)
        s[i] = mins[min(mins)]  # Parent pointer at position i

    j = max(s)
    while j > 1:
        if s[j] > 1:
            print "Line breaks at word "+str(j + 1)+": "+" ".join(words[s[j]: j + 1])
        else:
            print "Line breaks at word "+str(j + 1)+": "+" ".join(words[0: j+1])
        j = s[j] - 1

    print sorted(s.iteritems())

if '__main__' in __name__:
    words = "Mary had a little lamb and he was white as snow".split()
    justify_text(words, 15)
    words = "Dynamic programming is essentially sacrificing space complexity for time complexity (but the extra space you use is usually very little compared to the time you save, making dynamic programming totally worth it if implemented correctly). You store the values from each recursive call as you go (e.g. in an array or a dictionary) so you can avoid computing for the second time when you run into the same recursive call in another branch of the recursion tree.".split()
    justify_text(words, 100)

Line breaks at word 12: as snow
Line breaks at word 9: he was white
Line breaks at word 6: lamb and
Line breaks at word 4: Mary had a little
[(1, 1), (2, 1), (3, 1), (4, 3), (5, 4), (6, 4), (7, 5), (8, 6), (9, 7), (10, 7), (11, 9)]
Line breaks at word 78: when you run into the same recursive call in another branch of the recursion tree.
Line breaks at word 62: as you go (e.g. in an array or a dictionary) so you can avoid computing for the second time
Line breaks at word 43: totally worth it if implemented correctly). You store the values from each recursive call
Line breaks at word 29: extra space you use is usually very little compared to the time you save, making dynamic programming
Line breaks at word 12: Dynamic programming is essentially sacrificing space complexity for time complexity (but the