3
$\begingroup$

This is a real-world application, not a student assignment.

  • Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
  • The boxes have the same height, but variable width.
  • When a box doesn't fit, it should wrap to the next line (just like text).
  • After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.

The input is, simply:

double colWidth = …;
List<double> boxWidths = [ … ];

And the output could be:

List<int> result = [ … ]; // Number of boxes in each line.
double minWidth = …;

An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:

| ** *** ***** |
| ** *         |

This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

| ** ***       |
| ***** ** *   |

The result is 2 boxes in the first line, and 3 boxes in the second line: List<int> result = [2, 3]. Widths are now 5 and 8. Difference is 3, and minWidth is 8.

Please note, we cannot change their order. If we could, then the difference would be 1 and minWidth would be 7:

| ** *** *     |
| ***** **     |

My question:

What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.

$\endgroup$
  • 1
    $\begingroup$ You'll have to decide how you want to measure how different the lengths are. Do you want to use max - min? Standard deviation? Something else? $\endgroup$ – D.W. Mar 28 at 20:21
  • 1
    $\begingroup$ @D.W. I know I want some "visually balanced" outcome for this, but I wouldn't know exactly how to define it. Maybe I could find the average line width, and then sum the square of the difference between the width of each line to this average. Maybe. I am open to suggestions. $\endgroup$ – MarcG Mar 28 at 20:58
  • $\begingroup$ You might want to wait at least 24 hours before accepting an answer to give at least everyone around the globe a chance to answer. $\endgroup$ – pipe Mar 29 at 14:17
11
$\begingroup$

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The Knuth-Plass algorithm is also used in Adobe InDesign. $\endgroup$ – user207421 Mar 29 at 6:35
  • 1
    $\begingroup$ Wow, that paper is a fascinating reading, thanks for pointing it out. However, I am not really formatting text, but only boxes, with no space between them. So the concepts of hyphenation and shrinking and expanding glue make no sense in my case. I will soon need another version with spacing, but that's another question. Well, I guess that algorithm could work in both cases, but I just searched now and couldn't find a Java or C# version. I wouldn't really know how to translate from Rust or C. Translating that other one from Python was already troubling for me. $\endgroup$ – MarcG Mar 30 at 2:42
3
$\begingroup$

This can be solved with dynamic programming; see https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness or https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/ for resources.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Do these take into account the fact that the number of lines is fixed? $\endgroup$ – MarcG Mar 28 at 21:23
  • 1
    $\begingroup$ @MarcG yes, they can easily handle that constraint. $\endgroup$ – D.W. Mar 28 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.