Integer Poetry

Latin lets you shuffle the words of a line and keep the meaning. Word order carries less of the sense than it does in English, so a sentence can be rearranged for sound, for emphasis, or for play. In $1615$ the Jesuit Bernard Bauhuis wrote a one-line hexameter in praise of the Virgin, $$\textit{Tot tibi sunt dotes, Virgo, quot sidera caelo,}$$ “thou hast as many virtues, O Virgin, as there are stars in the heavens.” Its eight words can be set down in $8! = 40{,}320$ orders. How many of those still scan as a proper hexameter? And once we know, which scanning order would you choose to say if you had to say it fast?

Long and short

A hexameter is built of six feet, and each syllable in it is either long or short. Write a long syllable as $1$ and a short as $0$. The first four feet are each a dactyl, $1\,0\,0$, or a spondee, $1\,1$; the fifth foot is a dactyl; the sixth is a trochee, $1\,0$, or a spondee, $1\,1$. Four free feet of two kinds, then a fixed fifth, then two choices for the last, give $2^4 \cdot 2 = 32$ valid patterns.

The eight words have their own fixed shapes, save two that may be said either way: $$\begin{array}{l|l} \text{tot} & 1 \\ \text{tibi} & 0\,0 \;\text{or}\; 0\,1 \\ \text{sunt} & 1 \\ \text{dotes} & 1\,1 \\ \text{Virgo} & 1\,0 \;\text{or}\; 1\,1 \\ \text{quot} & 1 \\ \text{sidera} & 1\,0\,0 \\ \text{caelo} & 1\,1 \end{array}$$ Laid end to end they always come to fourteen syllables. A pattern can match an order only if it too has fourteen, and that is a real restriction: a foot is two syllables unless it is a dactyl, which is three, and the only way to reach fourteen is to have exactly one dactyl among the first four feet. Eight of the thirty-two patterns qualify.

Bernoulli’s count

To decide whether an order scans, lay its syllables out and ask whether the string of ones and zeros is one of the eight fourteen-syllable patterns, taking for the two flexible words whichever reading helps. Counting the orders that pass is an old amusement. Several seventeenth-century mathematicians attempted it; Jakob Bernoulli settled it in $1692$ at $3{,}312$. A short brute force over all $40{,}320$ orders confirms the figure, and the same enumeration is the verification this chapter carries for it.

Last words

Now the part for us. Imagine you must recite the line in a hurry, unsure you will reach the end, and you would like to have spoken as many whole words as possible before you are cut off. Whole words finish soonest when the short words go first, so the aim is to bring the briefest words forward while still scanning.

Following the article we fix one pattern to aim at, the fourteen-syllable one whose short syllables fall earliest: $$\begin{array}{c|c|c|c|c|c} 1\,0\,0 & 1\,1 & 1\,1 & 1\,1 & 1\,0\,0 & 1\,0 \\ \text{dactyl} & \text{spond.} & \text{spond.} & \text{spond.} & \text{dactyl} & \text{troch.} \end{array}$$ The task is then to lay the eight words across its fourteen slots so that each word’s shape sits on matching marks, speaking the short words as early as we can. Let $x_{w,p} = 1$ mean word $w$ begins at position $p$. A word may begin only where its shape fits the pattern; each word begins once; each slot is covered by exactly one word. The word that starts at $p$ and runs to $p + \ell_w$ holds those slots, so the cover is a tiling, and “short words early” is the small objective $$\text{minimise} \quad \sum_{w} \sum_p p \, x_{w,p},$$ the sum of the words’ starting positions: pushing a long word later costs more than pushing a short one, so the short words are drawn to the front.

from ortools.sat.python import cp_model

WORDS = {
    "tot": [(1,)], "tibi": [(0, 0), (0, 1)],
    "sunt": [(1,)], "dotes": [(1, 1)],
    "Virgo": [(1, 0), (1, 1)], "quot": [(1,)],
    "sidera": [(1, 0, 0)], "caelo": [(1, 1)],
}
TARGET = (1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0)

def valid_starts(word):
    opts = WORDS[word]
    L = len(opts[0])
    return [p for p in range(len(TARGET) - L + 1)
            if TARGET[p:p + L] in opts]

def place_model(fix=None):
    m = cp_model.CpModel()
    pl = {}
    for w in WORDS:
        cells = valid_starts(w)
        for p in cells:
            pl[w, p] = m.NewBoolVar("")
        m.Add(sum(pl[w, p] for p in cells) == 1)
    for q in range(len(TARGET)):
        m.Add(sum(pl[w, p] for (w, p) in pl
                  if p <= q < p + len(WORDS[w][0])) == 1)
    total = sum((p + 1) * pl[w, p] for (w, p) in pl)
    if fix is not None:
        m.Add(total == fix)
    return m, pl, total

def solve():
    m, pl, total = place_model()
    m.Minimize(total)
    s = cp_model.CpSolver()
    s.Solve(m)
    opt = int(s.ObjectiveValue())
    m2, pl2, _ = place_model(fix=opt)
    lines = []

    class C(cp_model.CpSolverSolutionCallback):
        def __init__(self):
            cp_model.CpSolverSolutionCallback.__init__(self)
        def on_solution_callback(self):
            at = {p: w for (w, p) in pl2
                  if self.Value(pl2[w, p])}
            lines.append(tuple(at[p] for p in sorted(at)))

    s2 = cp_model.CpSolver()
    s2.parameters.enumerate_all_solutions = True
    s2.Solve(m2, C())
    return opt, sorted(lines)

The solver does not hand back one line. It hands back twelve, all tied at the same best value, and Chlond’s printed answer, $$\textit{Sunt tibi quot tot dotes caelo sidera Virgo,}$$ is one of the twelve. The reason is worth seeing. The metre fixes three words outright: tibi, the only word that can lie on the early $0\,0$, takes the second slot; sidera, the only $1\,0\,0$, takes the late one; Virgo falls on the closing $1\,0$. What is left free is what the ear cannot tell apart in the metre. The three one-syllable words sunt, tot, quot are interchangeable across the three single-long slots, and the two two-syllable words dotes, caelo are interchangeable across their pair, so $$3! \cdot 2! = 12$$ lines share the crown. The optimisation has found the shape of the best line and correctly refused to invent a preference between words it has no way to rank. To choose one of the twelve you would need a reason the metre does not supply, and that is the honest end of the matter.

Sources. The puzzle is from Martin J. Chlond, Integer Poetry, INFORMS Transactions on Education volume $12$, number $1$ ($2011$), pages $65$–$66$, which draws it from Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (Addison-Wesley, $2011$), pages $500$–$502$, where Bauhuis’s $1615$ laudation and its scansion appear. The count of $3{,}312$ scanning arrangements is Jakob Bernoulli’s, from $1692$; it is verified here by direct enumeration. The assignment model and the position-weighted objective are Chlond’s (his objective weights position by the square of the word’s length, to the same effect); the reading of the objective as bringing short words forward, and the observation that the optimum is a family of twelve lines fixed in shape and free in its interchangeable words, are this chapter’s, each produced and checked by the model above.