Daily Shaarli

All links of one day in a single page.

10/05/18

Watch Scientists Accidentally Blow Up Their Lab With The Strongest Indoor Magnetic Field Ever

Researchers at the University of Tokyo were expecting to create a strong magnetic field, but they got a lot more than they were bargaining for.

Description and implementation of the core Knuth-Plass line-wrapping algorithm.

Line-breaking algorithms take a paragraph's-worth of words, and split the words into line-lengthed chunks. The two algorithms many programmer's know of are:

  • The greedy algorithm; and,
  • The Knuth-Plass algorithm (the 'latex one').

Most programmers "know" the following three facts:

  • Knuth-Plass produces the 'best' line breaks;
  • Knuth-Plass is a quadratic algorithm; and,
  • Knuth-Plass uses dynamic programming and is impossible for mere mortals to code.

While we happen to agree with (1), we will demonstrate that (2) and (3) are, respectively, not true, and unnecessarily obscure. In fact, the Knuth-Plass algorithm---even in its most naive implementation---is strongly dominated by a light-weight linear run-time, and the implementation of the core algorithm is remarkably straightforward.