Size Algorithm

Question

Hi,

Ok here's a little problem I would love to get some help on.

I have a view and the viewport size will vary based on user screen resolution. The viewport needs to contain N boxes which are lined up next to each other from right to left and take up all of the horizontal space in the viewport. Now if all the boxes could be the same size this would be easy, just divide the viewport width by N and you're away.

The problem is that each box needs to be 10% smaller than the box to its left hand side, so for example if the viewport is 271 pixels wide and there are three boxes I will be returned [100, 90, 81]

So I need an algorithm that when handed the width of the viewport and the number of horizontal boxs will return an array containing the width of that each of the boxes needs to be in order to fill the width of the viewport and reduce each boxes size by 10%.

Answers in any OO language is cool. Would just like to get some ideas on how to approach this and maybe see who can come up with the most elegant solution.

Regards,

Chris

Answer 1

This is really a mathematical problem. With two boxes given:

x = size of the first box n = number of boxes P = number of pixels

then

x + 0.9x = P

3: x + 0.9x + 0.81x = P
4: x + 0.9x + 0.81x + 0.729x = P

which is, in fact, a geometric series in the form:

S(n) = a + ar + arⁿ + ... + ar^n-1

where:

a = size of the first box
r = 0.9
S(n) = P

S(n) = a(1-rⁿ)/(1-r)

so

x = 0.1P/(1-0.9ⁿ)

which (finally!) seems correct and can be solved for any (P,n).

Answer 2

Start with computing the sum of boxes' widths, assuming the first box is 1, second 0.81, etc. You can do this iteratively or from the formula for geometric series. Then scale each box by the (viewport width)/(sum of original boxes' width) ratio.

Answer 3

It's called Geometric Progression and there is a Wikipedia article on it. The formulas are there too. I believe that cletus has made a mistake with his f(n). Corrected. :)

Answer 4

Let:
x = size of the first box
n = number of boxes
P = number of pixels

n = 1: x = P
n = 2: x + .9x = P
n = 3: x + .9x + .81x = P

P = x sum[1..n](.9 ^ (n - 1))

Therefore:
x = P / sum[1..n](.9 ^ (n - 1))

Using the Geometric Progression formula:
x = P (.9 - 1) / ((.9 ^ n) - 1))

Test:
P = 100
n = 3
Gives:
x = 36.9

Answer 5

    public static int[] GetWidths(int width, int partsCount)
 {
  double q = 0.9;
  int[] result = new int[partsCount];

  double a = (width * (1 - q)) / (1 - Math.Pow(q, partsCount));

  result[0] = (int) Math.Round(a);
  int sum = result[0];

  for (int i = 1; i < partsCount - 1; i++)
  {
   result[i] = (int) Math.Round( a * Math.Pow(q, i) );
   sum += result[i];
  }

  result[partsCount - 1] = width - sum;

  return result;
 }

It's because it is geometric progression.

Answer 6

Using a simple geometric progression, in Python,

def box_sizes(width, num_boxes) :
    first_box = width / (10 * (1 - 0.9**n))
    return [first_box * 0.9**i for i in range(n)]

>>> box_sizes(100, 5)
[24.419428096993972, 21.977485287294574, 19.779736758565118, 17.801763082708607, 16.021586774437747]
>>> sum(_)
100.00000000000001

You may want to tidy up the precision, or convert to integers, but that should do it.

Answer 7

Like others have mentioned, the widths of the boxes form a geometric progression. Given viewport width W and number of boxes N, we can solve directly for the width of the widest box X. To fit N boxes within the viewport, we need

X + 0.9 X + 0.9^2 X + ... + 0.9^(N-1) X <= W

{ 1 + 0.9 + 0.9^2 + ... + 0.9^(N-1) } X <= W

Applying the formula for the sum of a geometric progression gives

(1 - 0.9^N) X / (1 - 0.9) <= W

X <= 0.1 W / (1 - 0.9^N)

So there you have it, a closed-form expression which gives you the width of the widest box X.