4
$\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$
3
  • 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, 2020 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$ Mar 28, 2020 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, 2020 at 14:17

2 Answers 2

12
$\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:

$\endgroup$
2
  • 1
    $\begingroup$ The Knuth-Plass algorithm is also used in Adobe InDesign. $\endgroup$
    – user207421
    Mar 29, 2020 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$ Mar 30, 2020 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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