Better Form Design through Dynamic Programming
Applying Dynamic Programming to produce better layouts for Web Forms
Programming web forms is not usually associated with recursive algorithms or optimization techniques, but in this article we will show a problem that we faced, and how we managed to solve it with an efficient algorithm, by applying recursion and Dynamic Programming: building nice-looking forms!
The Problem: Building a nice form
Let’s talk about the problem. The client needed to be able to produce multiple forms onscreen, with different sets of fields. Since the number of forms would be growing all the time, a “form creator” was desired: it would take a “form description” (basically, a list of fields in a specified order) as input and produce the right screen form as output. For example, the form fragment shown below could be produced by our system.
However, there was a problem, an extra condition: the form had to “look nice”, applying justification to get even margins. But (there’s always a but) the widths of the fields were not necessarily such that all rows would be full, so you’d need to break rows and stretch fields to achieve the desired look.
If you know about the internal details of the TEX typesetting system, you may be aware of the Knuth-Plass algorithm line-breaking algorithm that tackles the question of splitting paragraphs “nicely”. What we are doing here is at heart the same problem (in fact we could have based our logic on the mentioned algorithm) but we want to focus on the path to arrive at a valid algorithm.
To better understand the problem, let’s imagine we had five fields, with widths 7, 2, 5, 3, and 6 respectively, to be displayed in rows with a width of 10.
How can we proceed? Some little experimentation shows that you cannot manage with fewer than 3 rows, and that 4 or more rows lead to too much wasted space. (Actually there won’t be “empty space” in the rows, since we won’t leave spaces around blocks, but rather make them wider to fit. In any case, we do have to know how much empty space will be left on each row, in order to then decide how to expand the blocks on it.)
So, how can we fit these blocks in three rows? The first possibility would be applying a “greedy” algorithm: fit as many blocks in a row as possible, before moving to a new row. With this approach, we’d get the following layout.
But this is not the only possibility! If we don’t include the 2-block in the first row, and move it to the next row instead, it leads to different alternatives. For example, we could totally fill the second row with the 2-, 5-, and 3-blocks, and get another layout.
And there’s one more layout: instead of filling the second row, we could move the 3-block to the last row, and this would be the result.
We can also look at solutions with 4 or 5 rows, but they require adding too much empty space — though we’ll qualify below what we mean by this.
What’s the preferred solution — which one should be considered best? We need to establish a metric to decide which layout is to be considered the optimum one. We have to define a formula to calculate a row-wise cost, in terms of how many extra padding we added. Given the option, we prefer adding smaller spaces in many rows, than adding bigger spaces in few rows. So, let’s define the cost per row as the added space but squared, and the total cost will then be the sum of all the row costs.
Why square the numbers? Imagine you had 2 spaces to add: if you add all of them in a single row, the cost would be 2²=4, but if you added 1 space to two lines, the cost would be just 1²+1²= 2. Squaring the numbers before adding them makes having many small numbers preferrable to having fewer larger ones. Obviously, squaring is not the only possible way to get numbers to behave the way we want (why not cubing? or exponentiating?) but it’s a simple solution that works well, so let’s use it.
With this definition, the cost for the first layout would be 1²+2²+4²= 1+4+16= 21, the second cost would be 3²+0²+4²= 9+0+16= 25, and the third cost 3²+3²+1²= 9+9+1= 19. Thus, we’d consider the latter to be the one our algorithm should produce… but how do we code that? Let’s turn to this.
The Solution: a Dynamic Programming algorithm
How can we solve find the appropriate row breaks for our form? A very obvious (and awful!) way to do is would be trying out all possible break points between blocks, and see which combination looks better — but the number of combinations to test grows exponentially with the number of blocks, so this approach is totally out of the question. We must do better!
Assume we have a list of block widths; in our case, [7, 2, 5, 3, 6]. We also have a maximum width to achieve in each row: MW. Let’s think recursively: what’s the best way of distributing padding among the blocks? Let’s make it general: if we want to distribute a fragment of the blocks from position p to position q in an optimal way, we can use the logic below — and applying it with p pointing to the first block and q to the last block would solve our original problem.
- sum the widths of all fields from p to q inclusive; call this sum s
- if s is not greater than MW, the cost of this fragment is (MW-s)², and there’s nothing more to be done; we cannot do any better by splitting the fragment in two or more rows.
- if s exceeds MW, we need to add some row breaks… but where? The solution is recursive: try splitting the fragment in two pieces in all possible ways (the first piece would go from p to r, and the second from r+1 to q) and see which split produces the lowest cost; that’s your solution.
Can we code this? Sure; in JavaScript, the following would do. (The code isn’t complete; for example, we’re neither recording what breaks we found, nor actually padding fields — let’s just focus on finding the best breaks, our main problem here.) Let’s assume we have a totalWidth(x,y) function that calculates the sum of the widths of blocks x through y.
const costOfFragment = (p, q) => {
const s = totalWidth(p, q); // fits in single row?
if (s <= MW) return (MW - s) ** 2; // no fit; try row breaks
let opt = Infinity;
for (let r = p; r < q; r++) {
const newTry = costOfFragment(p, r) + costOfFragment(r + 1, q);
if (newTry < opt) opt = newTry;
}
return opt;
};
If the fields fit in a single row, we return the cost without any further do. Otherwise, we start trying out different row breaks using r, and we calculate the cost of a possible line break in try, by recursively calling costOfFragment. The best (lowest) achieved total is stored in opt.
This logic works! Let’s see how we’d process our five blocks from above to make them fit in 10-width rows. Starting with the five blocks, we’d have to try four possible splits, since the blocks don’t fit in a single row.
The diagram above shows all the possible splits that would be attempted; let’s add the information about costs, to find what would be the best solution. Numbers in red are costs, calculated according to our squaring and summing definition.
Let’s recap the rules for costs:
- if you don’t have a split, to cost is the added space, squared: for instance, at the bottom left corner you have a single [5] which costs 25 (you need to add 5 spaces to get 10), a [3,6] which costs 1 (1 added space, squared), a [5,3] which costs 4 (2 added spaces, squared), and a [6] which costs 16 (4 added spaces, squared).
- the total cost of a series of rows is just the sum of the individual splits — for example, if you split [5,3,6] in two rows with [5] and [3,6], the cost is 26 (25 from the 5 and 1 from the 3+6), and if you split it in [5,3] and [6], the cost is 20 (16 plus 4).
- if you have a split, the cost is the minimum cost of all the possible splits in rows. As an example, again near the bottom left corner, the cost for splitting [5,3,6] is 20, the minimum cost of its two possible splits, with individual costs of 26 and 20
Our logic produces the result we discussed above, and the optimum solution for our five blocks costs 19, and requires three lines: one with the 7-block alone, other with the 2- and 5-blocks, and the last with the 3- and 6-blocks. Great!
But…
Optimizing through Dynamic Programming
There’s a problem with the process above… the algorithm is slow — mainly because it redoes several calculations over and over. The diagram below shows that; each colored block is calculated more than once.
We can do better, by applying Dynamic Programming: a technique to solve a complex problem by breaking it down into simpler versions of the same problem, whose solutions are stored somewhere, to avoid having to re-do calculations.
In our case, how can we skip repeating calls? We could obviously create and update a cache of results by hand, but we don’t need to do so, because this is a problem that we already know how to solve: memoizing! Basically, if you take a function and memoize it, you get a new one that behaves identically, except that it will cache calculated results; if you call the memoized function with parameters that you had already passed before, it won’t do any calculations and return the value from the cache instead.
We already saw another usage of memoizing to optimize API calls; check my Memoize JavaScript Promises for Performance article for that. We developed a memoizing function of our own there, but you can also opt for the very efficient fast-memoize library instead, among other possibilities.
How much work would we avoid? The diagram below shows the enhanced results: all grey blocks need no recalculation, and in particular the arrows point to places where no recursion was even needed, because the work had already been done.
In the diagram above, blocks in grey are those that do not need to be recomputed, because the necessary work was already done before and saved. If you compare this figure with the previous ones, you’ll notice that two parts of the diagram (where the green arrows are) do not appear any longer — those are calls that were not needed because of the caching.
In terms of coding, the change is minimal.
const costOfFragment = memoize((p: number, q: number) => {
.
. no changes here!
.
});That does it! The optimized algorithm does minimal work, and finds a nice split quickly.
Summary
We described an actual problem derived from a client’s request, and how we managed to solve it in an optimized way by applying Dynamic Programming and memoization, to go from a correct-but-slow algorithm to an also-correct-but-fast one, with minimal changes. This same techniques can be applied in many other contexts, for equally good performance enhancements; an all around win!
