Path: csiph.com!news.mixmin.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: Paragraph Wrapping
Date: Fri, 27 Jan 2023 01:22:19 +0000
Organization: A noiseless patient Spider
Lines: 20
Message-ID: <87o7qkwz3o.fsf@bsb.me.uk>
References: <wrap-20230126195034@ram.dialup.fu-berlin.de>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="60014a0063bb2d5830bbe2489c026e03"; logging-data="1497578"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18OYSJBojVELvS9aiNG7vmTA8AU8pySwX8="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:od94sYCWNOuQu9VrB5diaB+KWvM= sha1:Q+zdROLHV5HuLaa/5ataglCwNE4=
X-BSB-Auth: 1.04305b3b24603825f755.20230127012219GMT.87o7qkwz3o.fsf@bsb.me.uk
Xref: csiph.com comp.programming:16351

ram@zedat.fu-berlin.de (Stefan Ram) writes:

>   To wrap a paragraph, I wrote a Python script that searched for
>   the best wrap, given a quality function that included penalties
>   for interpunction near the end of a line (but not at the end)
>   or adjacent lines that differed greatly in length.
>
>   It worked, but as the number of lines approached ten, it became
>   painfully slow.
>
>   By an incredible twist of fate, I came across a chapter of
>   a book that explained dynamic programming and how to use it
>   to reduce the complexity of global paragraph wrapping from
>   exponential to quadratic!

The TeX Book describes two-level algorithm to calculate optimal line
breaks in paragraphs and the optimal page breaks.

-- 
Ben.