1
$\begingroup$

I've you've ever had a table of text like in Word or Google Docs, you'd know that there are ideal widths for each table column to minimize the height of the table and fit the most text, here's an example. I've tried thinking about how I could implement that myself, but have no ideas. I wonder if this would be some sort of optimization math equation, but I haven't touched math in forever. If it was, how would it optimize all the column widths? I did some looking up, as well as asking both GPT 3.5 and 4 to write a Python script for this, but they both had issues.

$\endgroup$
1
  • 1
    $\begingroup$ Shouldn't the first word of the post body be If? minimize the height of the table shouldn't be the only criterion - else make every column a mile and half. To find an approach, start with a simplified problem: How to size columns if texts weren't made up of words/"non-divisible" chunks - say, of repetitions of a single narrow glyph. $\endgroup$
    – greybeard
    Commented Sep 6, 2023 at 6:45

1 Answer 1

1
$\begingroup$

There is a reasonably efficient algorithm for this. I will assume that you have a value $w$ that is the maximum possible width for the table, and you want to find column widths that sum to at most $w$, that minimize the table height. For instance, $w$ might be the width of the page or of the text region on the page.

The solution will be to use binary search repeatedly. In particular, we'll do binary search on the height $h$ of the table.

I assume the text for each column is given. Therefore, given any proposed width $w_i$ for a column, you can compute the height required for that column (by formatting the text into a box of width $w_i$).

Now I suggest you use binary search on $h$, the height of the table, to find the minimum achievable height, given that the total table width must be no greater than $w$. Suppose we have a particular $h$. For each column, say the $i$th column, find the minimum width $w_i$ for that column that ensures its height will be at most $h$ (this can be done using binary search over $w_i$ combined with the fact from the prior paragraph). This gives a minimum width $w_i$ for each column. Now compute the sum $w_1+\dots+w_k$; if this is greater than $w$, then conclude that height $h$ is not attainable (within the constraint on max table width); otherwise conclude that height $h$ is attainable. Continue using binary search on $h$ to find the smallest $h$ that is attainable.

The total running time will be at most something like $O(n^2 \lg^2 n)$, where $n$ is the size of the input. There are probably optimizations to significantly improve this.

$\endgroup$

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.