A Dynamic Programming Primer

Consider the problem of printing a paragraph neatly on a printer, with fixed width font. The input text is a sequence of n words of lengths \(l_1, l_2, \dots, l_n\) . The line length is \(M\) (the maximum number of characters per line). We expect that the paragraph is left justified, that all first words on a line start at the leftmost position and that there is exactly one space between any two words on the same line. We want the uneven right ends of all the lines to be together as neat as possible. Our criterion of neatness is that we wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of the lines. Note that if a printed line contains words \(i\) through \(j\), then the number of spaces at the end of the line is $$ f(i, j) = M - j + i - \sum_{k=i}^{j}{l_k} $$ This problem was sourced from http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/ , thanks Mr. Erickson!

How do we position the line breaks? A recursive approach immediately springs in mind: we put а line break at some, yet undecided, place and then optimally break into lines the rest of the words:

place_breaks (words[1..n]) 
   t = choose_break_position()
   place_breaks (words[1..t])

In a sequence of \(n\) words we may put a break before the first word, before the second word, before the third, ... and so on, for a total of \(n\) possible positions, as long as the words after the break fit on a single line, which is equivalent to the condition \(f(i,j) \gt 0\). Of all the allowed positions to place a break, we choose the position, which minimizes the cost of placing a break there. If we denote by \(C(k)\) the minimum cost of splitting words \(1\) through \(k\), we have for the cost function $$ C(k) = \min_{0 \le t < k, f(t,k-1) \ge 0} \lbrace C(t) + f(t, k-1)^3 \rbrace $$ However, note that the spaces at the end of our last line do not participate in evaluating neatness. Therefore, for the last line only, our cost function \(T(n)\) would look like $$ T(n) = \min_{0 \le t < n, f(t,n-1) \ge 0} \lbrace C(t) \rbrace $$ Boundary case for the cost function would be \(C(0) = 0\) and now we have all the ingredients for implementing an efficient and correct algorithm. The cost function can be evaluated bottom up (\(C(0), C(1), \dots , C(n)\)) using \(O(n)\) additional space for storing intermediate results and each time we choose a break position, we will record it.

class line_breaker {
public:
    void break_lines (size_t, const std::vector<std::string> &);

protected:
    long f (size_t, size_t);
    void calculate_C (size_t);
    size_t calculate_T (size_t);

    std::vector<size_t> S;
    struct solution {
        long cost;
        size_t pos;
    };
    std::vector<solution> C;
    size_t M;
};

This is how the implementation will look like: we encapsulate the functions and the additional space required in a class to avoid passing lots of parameters around. The member function f is our penalty function, according the definition above and the member functions calculate_T and calculate_C, well, calculate the cost function for the last line break and for all the other line breaks, respectively. To speed up the calculation of the penalty function, we use the well-known trick of keeping in the vector S the accumulated lengths of the words, so \(S_i = \sum_{k=0}^i{l_k}\). The implementation of the helper functions comes directly form the formulae above:

long
line_breaker::f (size_t i, size_t j) {
    long x;
    if (i >= j + 1)
        return -1;
    else {
        long y = i == 0 ? S[j] : S[j] - S[i-1];
        x = M - j + i - y;
        return x * x * x;
    }
}

void
line_breaker::calculate_C (size_t n) {
    C[0].cost = 0;
    C[0].pos = 0;

    for (size_t i = 1; i <= n; ++i) {
        size_t t, min_t = 0;
        long min = LONG_MAX;
        
        for (t = 0; t < i; ++t) {
            if (f (t, i-1) >= 0 && C[t].cost + f (t, i-1) < min) {
                min = C[t].cost + f(t, i-1);
                min_t = t;
            }
        }
        
        C[i].cost = min;
        C[i].pos = min_t;
    }
}

size_t
line_breaker::calculate_T (size_t n) {
    size_t t, min_t = 0;
    long min = LONG_MAX;

    calculate_C (n);
    for (t = 0; t < n; ++t) {
        if (f(t, n-1) >= 0 && C[t].cost < min) {
            min = C[t].cost;
            min_t = t;
        }
    }

    return min_t;
}

And now for the function, that performs the actual splitting of the text:

void
line_breaker::break_lines (size_t m, const std::vector<std::string> &text) {

We pass the length of a line in the parameter m and the text to format in the parameter text

    S.clear();
    C.clear();

Clean up whatever is left from a previous invocation.

    size_t s = 0, n;
    for (const auto &str : text) {
        n = str.size();
        if (n > m)
            return;
        s += n;
        S.push_back (s);
    }

    n = text.size();
    C.resize (n+1);
    M = m;

Prepare the various working areas. Note that we check that each word length is less than or equal to the line length - this will guarantee that a solution to the problem in fact exists.

    size_t t = calculate_T (n);

... and invoke the function to place the line breaks, starting from the last one.

    std::vector<size_t>div;
    div.push_back (n);
    while (t > 0) {
        div.push_back (t);
        t = C[t].pos;
    }
    std::reverse (div.begin(), div.end());

The member function calculate_T will return the index of the last break placed. The corresponding element of the vector C will give us the position of the previous break and so on, until we reach position zero. Now we have collected all the line breaks in vector div and have only to reverse it ...

    size_t i = 0;
    for (auto j : div) {
        while (i < j) {
            std::cout << text[i] << " ";
            ++i;
        }
        std::cout << "\n";
    }
        
    std::cout << std::endl;
}

... and output the formatted lines. And that's it. The source follows in its entirety.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm&gtl
#include <string>

class line_breaker {
public:
    void break_lines (size_t, const std::vector<std::string> &);

protected:
    long f (size_t, size_t);
    void calculate_C (size_t);
    size_t calculate_T (size_t);

    std::vector<size_t> S;
    struct solution {
        long cost;
        size_t pos;
    };
    std::vector<solution> C;
    size_t M;
};

long
line_breaker::f (size_t i, size_t j) {
    long x;
    if (i >= j + 1)
        return -1;
    else {
        long y = i == 0 ? S[j] : S[j] - S[i-1];
        x = M - j + i - y;
        return x * x * x;
    }
}

void
line_breaker::calculate_C (size_t n) {
    C[0].cost = 0;
    C[0].pos = 0;

    for (size_t i = 1; i <= n; ++i) {
        size_t t, min_t = 0;
        long min = LONG_MAX;
        
        for (t = 0; t < i; ++t) {
            if (f (t, i-1) >= 0 && C[t].cost + f (t, i-1) < min) {
                min = C[t].cost + f(t, i-1);
                min_t = t;
            }
        }
        
        C[i].cost = min;
        C[i].pos = min_t;
    }
}

size_t
line_breaker::calculate_T (size_t n) {
    size_t t, min_t = 0;
    long min = LONG_MAX;

    calculate_C (n);
    for (t = 0; t < n; ++t) {
        if (f(t, n-1) >= 0 && C[t].cost < min) {
            min = C[t].cost;
            min_t = t;
        }
    }

    return min_t;
}

void
line_breaker::break_lines (size_t m, const std::vector<std::string> &text) {
    S.clear();
    C.clear();
    
    size_t s = 0, n;
    for (const auto &str : text) {
        n = str.size();
        if (n > m)
            return;
        s += n;
        S.push_back (s);
    }

    n = text.size();
    C.resize (n+1);
    M = m;

    size_t t = calculate_T (n);

    std::vector<size_t> div;
    div.push_back (n);
    while (t > 0) {
        div.push_back (t);
        t = C[t].pos;
    }
    std::reverse (div.begin(), div.end());

    size_t i = 0;
    for (auto j : div) {
        while (i < j) {
            std::cout << text[i] << " ";
            ++i;
        }
        std::cout << "\n";
    }
        
    std::cout << std::endl;
}

std::vector<std::string> text = {
    "Lorem", "Ipsum", "is", "simply", "dummy", "text", "of", "the",
    "printing", "and", "typesetting", "industry.", "Lorem", "Ipsum",
    "has", "been", "the", "industry's", "standard", "dummy", "text",
    "ever", "since", "the", "1500s", "when", "an", "unknown", "printer",
    "took", "a", "galley", "of", "type", "and", "scrambled", "it", "to",
    "make", "a", "type", "specimen", "book.", "It", "has", "survived",
    "not", "only", "five", "centuries,", "but", "also", "the", "leap",
    "into", "electronic", "typesetting,", "remaining", "essentially",
    "unchanged.", "It", "was", "popularised", "in", "the", "1960s",
    "with", "the", "release", "of", "Letraset", "sheets", "containing",
    "Lorem", "Ipsum", "passages,", "and", "more", "recently", "with",
    "desktop", "publishing", "software", "like", "Aldus", "PageMaker",
    "including", "versions", "of", "Lorem", "Ipsum" };

int
main () {
    line_breaker br;
    br.break_lines (30, text);
}

Non-recursive inorder and postorder tree traversal

Depth-first traversal using a stack, is a well-known technique for traversing large trees, when the process stack may not be large enough. For reference, here is one simple implementation:

#include <stack>

struct tree {
    int value;
    tree *left;
    tree *right;
};

void preorder (tree *t, void (*visit) (tree *)) {
    std::stack<tree *> work;

    if (t == nullptr)
        return;

    work.push (t);
    while (! work.empty ()) {
        t = work.top ();
        work.pop ();

        visit (t);

        if (t->right)
            work.push (t->right);
        if (t->left)
            work.push (t->left);
    }
}

However, this algorithm does a pre-order traversal, i.e. the root of each subtree is visited before its children. But how about a post-order or an in-order traversal? When we pop a node from the stack, we are in two different situations: we may need to visit the node now or we may need to push its children and visit it later. The insight is to use a secondary stack, in which to keep track of the parent nodes, which have to be visited later. When a node comes out of the stack for the first time, we put it back, together with its children, in the appropriate order, but we also put it on the secondary stack. After we have processed all of the node's children (or all of the left subtree, for an in-order traversal), the node pops off the primary stack again, but this time it's also at the top of the secondary stack! Now we know the time has come to process it. The following two functions implement this idea for in-order and post-order traversals:

void inorder (tree *t, void (*visit) (tree *)) {
    std::stack<tree *> parents;
    std::stack<tree *> work;
    
    if (t == nullptr)
        return;

    work.push (t);

    while (! work.empty ()) {
        t = work.top ();
        work.pop ();

        if (! parents.empty () && t == parents.top()) {
            parents.pop ();
            visit (t);
        } else {
            parents.push (t);
            if (t->right)
                work.push (t->right);
            work.push (t);
            if (t->left)
                work.push (t->left);
        }
    }
}

void postorder (tree *t, void (*visit)(tree *)) {
    std::stack<tree *> parents;
    std::stack<tree *> work;
    
    if (t == nullptr)
        return;

    work.push (t);

    while (! work.empty ()) {
        t = work.top ();

        if (! parents.empty () && t == parents.top ()) {
            work.pop ();
            parents.pop ();
            visit (t);
        } else {
            parents.push (t);
            if (t->right)
                work.push (t->right);
            if (t->left)
                work.push (t->left);
        }
    }
}