Just committed and uploaded a new version of PADS, where I greatly improved my Sudoku solver's ability to explain in English the deductions it makes. As part of this text generation capability, I needed to wrap lines of text to fit within a console window, and rather than doing it with the obvious (and perfectly adequate) greedy algorithm, I decided to make more work for myself by incorporating a more flexible and powerful TeX-like system (in Wrap.py) in which one assigns penalties to different possible lines in a paragraph depending on e.g. how much they fall short of the optimal target width, and searches for the partition of the paragraph into lines that minimizes the sum of the penalties.

This is an example of a class of programs called concave one-dimensional dynamic programming, studied by myself and others in the late 1980's when I was in grad school due to their connections with DNA sequence comparison and RNA secondary structure prediction. More formally, the problem is to compute

\[ E[j] = \min_{i\lt j} E[i] + w(i,j), \]

where \( w(i,j) \) is the penalty function for a line that stretches from breakpoint \( i \) to breakpoint \( j \), and \( E[j] \) is the total cost of the best sequence of breaks up to breakpoint \( j \). The problem is "concave" if, roughly speaking, as we increase \( j \), the position \( i \) that forms the best previous breakpoint also increases. The function \( w \) is independent of the computed best breakpoints, but more generally, the algorithms for this sort of problem can compute

\[ E[j] = \min_{i\lt j} f(i,j), \]

as long as \( f(i,j) \) depends only on \( E[i] \) and not on later values of \( E \).

TeX itself uses a relatively naive dynamic programming algorithm to solve the problem in time quadratic in the number of possible breakpoints, developed by Knuth and Plass. My advisor Zvi Galil and fellow student Raffaele Giancarlo found an \( O(n\log n) \) algorithm, which Robert Wilber improved to \( O(n) \). Wilber's algorithm had the drawback, however, of not being fully online; it could solve the line-breaking problem, but could not be used in certain algorithms that involved multiple one-dimensional dynamic programs being run in an interleaved fashion. One of my early papers solved this interleaving problem, and was then simplified by Galil and another of his students, Kunsoo Park. The algorithm I implemented in PADS is the Galil-Park one.

No doubt this is severe overkill for what I needed, but I had fun doing it...