Adam Megacz
2004-03-29 07:21:58 UTC
Brainteaser for yall. Earlier, I sized grid columns/rows by setting
each column to its minwidth and then handing out the slack in
proportion to the column's weight. This isn't what most people
"expect", though.
I'm trying to figure out how to do it in O(n) time (I figured out O(n
log n)) -- not because I care so much about the difference between
those two, but because O(nlgn) solutions are rarely incremental. In
other words, I want something where if very little has changed (like,
for example, only the goal width), we can use the old solution to get
the new one very quickly.
To make it harder, all this stuff has to be done with integers, *and*
the error has to be deterministic so that the columns don't "vibrate"
when you resize things really quickly. Basically this means that the
rounding error has to wind up in the same place regardless of whether
you computed the sizes from scratch or recycled the old solution.
Here's the formal statement of the problem:
You have a goal width for the sum of the columns. You must find 'k'
such that when each column is set to:
min(maxwidth, max(minwidth, k*weight))
the sum of all the columns equals the goal weight. Basically each
column is k*weight, and then you crop it to that column's max/min
size.
Winner gets a cookie.
- a
each column to its minwidth and then handing out the slack in
proportion to the column's weight. This isn't what most people
"expect", though.
I'm trying to figure out how to do it in O(n) time (I figured out O(n
log n)) -- not because I care so much about the difference between
those two, but because O(nlgn) solutions are rarely incremental. In
other words, I want something where if very little has changed (like,
for example, only the goal width), we can use the old solution to get
the new one very quickly.
To make it harder, all this stuff has to be done with integers, *and*
the error has to be deterministic so that the columns don't "vibrate"
when you resize things really quickly. Basically this means that the
rounding error has to wind up in the same place regardless of whether
you computed the sizes from scratch or recycled the old solution.
Here's the formal statement of the problem:
You have a goal width for the sum of the columns. You must find 'k'
such that when each column is set to:
min(maxwidth, max(minwidth, k*weight))
the sum of all the columns equals the goal weight. Basically each
column is k*weight, and then you crop it to that column's max/min
size.
Winner gets a cookie.
- a
--
"It's lucky," he added, after a pause, "that there are such a lot of
islands in the world. I almost envy you, Mr. Watson."
-- Mustapha Mond
"It's lucky," he added, after a pause, "that there are such a lot of
islands in the world. I almost envy you, Mr. Watson."
-- Mustapha Mond