Text justification and word wrap

Text justification lays out words in lines of exactly the same width by widening the spaces between them, so that both margins are straight. Word wrap is the simpler half of the job: it breaks text into lines no wider than the width and leaves the right margin ragged. The usual method packs as many words as fit into each line, then shares a line’s spare spaces among its gaps with one division, the leftmost gaps taking any remainder. The rules that trip people up are the edges: the last line, a line with a single word, and a word that is wider than the line.

The problem

Two examples, with each line between bars:

1. "Exam results will be posted on the notice board on Friday." at width 16 gives four lines: |Exam results|, |will be posted|, |on the notice| and |board on Friday.|.
2. "Library closed for stock taking" at width 12 gives |Library |, a line with one word padded on the right, then |closed for| and |stock taking|.

Word wrap of the first notice gives the same four lines without the extra spaces: Exam results, will be posted, on the notice and board on Friday..

The brute force: try every layout

The fewest lines can be found by trying every layout: a line may end after any of the n − 1 gaps between words, so there are 2ⁿ⁻¹ layouts, and the shortest one whose lines all fit wins. The run counts them:

# The fewest lines by brute force: try every way to break the words into lines, and keep the shortest valid layout.

def every_layout(words, width):
    """(fewest lines of a valid layout, layouts tried): a layout breaks after any subset of the n - 1 gaps."""
    n = len(words)
    best, tried = None, 0
    for breaks in range(2 ** (n - 1)):
        tried += 1
        lines, current = 0, [words[0]]
        ok = True
        for k in range(1, n):
            if breaks >> (k - 1) & 1:  # a line ends before word k
                ok = ok and len(" ".join(current)) <= width
                lines, current = lines + 1, [words[k]]
            else:
                current.append(words[k])
        ok = ok and len(" ".join(current)) <= width
        if ok and (best is None or lines + 1 < best):
            best = lines + 1
    return best, tried


notice = "Exam results will be posted on the notice board on Friday.".split()
fewest, tried = every_layout(notice, 16)
print(f"{len(notice)} words, width 16: fewest lines {fewest}, {tried:,} layouts tried")

longer = (notice + "Parents may collect the printed sheets at the office".split())
for n in (12, 14, 16):
    fewest, tried = every_layout(longer[:n], 16)
    print(f"{n} words: fewest lines {fewest}, {tried:,} layouts tried")

11 words, width 16: fewest lines 4, 1,024 layouts tried
12 words: fewest lines 5, 2,048 layouts tried
14 words: fewest lines 6, 8,192 layouts tried
16 words: fewest lines 7, 32,768 layouts tried

Every extra word doubles the count. The 11-word notice needs 1,024 layouts, 16 words need 32,768, and 10⁴ words would need 2⁹⁹⁹⁹, a number with 3,010 digits.

What to notice

A line that can take one more word gains nothing by refusing it: pushing a word to the next line can only push the following lines later. So packing each line as full as it can be gives the fewest lines without trying any other layout. After that, a line’s spaces are simply the width minus its letters, and one division with remainder shares them among its gaps. Text justification is that packing plus the division, and word wrap is the packing alone.

Greedy packing, and why it uses the fewest lines Pro: opens with a Pro, Premium or Ultimate pass