2
$\begingroup$

I have a bunch of coloured bricks. There are X different colours, and a random number of each colour. How do I stack them up into Y columns so that a) no row has two bricks of the same colour and b) the height of the largest column is minimised?

There is an obvious lower bound of highest number of bricks of a single colour but beyond that I don't know where to go. This is equivalent to an optimisation problem I'm trying to solve and I'd be grateful if someone recognised the problem!

$\endgroup$
  • 3
    $\begingroup$ If you don't know the total number of bricks of each color, does that mean you don't know anything about the future bricks at the time you're making a decision about the current brick? That seems like it would make it very difficult to get an optimal solution, since you could get a bunch of bricks of the same color at the end, which would ruin an optimally stacked solution for the earlier bricks. $\endgroup$ – Blckknght Nov 30 '17 at 3:37
  • $\begingroup$ I know all the bricks at the time I start stacking them, but not in advance (at coding time). Without knowledge of future bricks, you could definitely end up with a suboptimal final solution unless you restart placing them again. $\endgroup$ – Luke Nov 30 '17 at 18:09
  • $\begingroup$ Does allocating a column for each color solves the problem ? $\endgroup$ – user80502 Nov 30 '17 at 19:28
  • $\begingroup$ No, because Y can be less than X. With Y >= X, the problem is trivial, just allocate a column per colour. But with Y < X, it's non-trivial. $\endgroup$ – Luke Nov 30 '17 at 19:32
0
$\begingroup$

Let $n$ be the number of bricks and $c_i$ be the number of bricks of color $i$. First notice that in a $w \times h$ grid we can fit at most $wh$ bricks. Therefore, $\lceil \frac{n}{Y} \rceil$ is a lower bound on your height. The minimum height $h$ to stack all your bricks without violating the constraint will be $\max(\max_i(c_i), \lceil \frac{n}{Y} \rceil)$.

The idea is to go from left to right (column 1 to X) and keep pushing a brick of the same color on to the left most non-full stack. And by non-full I mean that the size of the stack is lower than our defined height $h$. No two colors will be in the same row and it is also obviously true, that we have enough room for all $n$ bricks.

A pseudo code is also provided:

color_count[i] = number of bricks of color i
height = max(max(color_count), ceil(n / Y))

current_column = 1
current_row = 1
current_color = 1
while current_color <= X
  while color_count[current_color] > 0
    put a brick at (current_row, current_column) with current_color
    color_count[current_color] -= 1
    if current_row == height
      current_column += 1
      current_row = 1
    else
      current_row += 1
  current_color += 1
$\endgroup$
  • 1
    $\begingroup$ Nice! Yeah, I can see that the other lower bound is also true, and we get the $\max(\max_i(c_i), \lceil \frac{n}{Y} \rceil)$ - then you're right, if we just sort by $c_i$ then just by filling each column as we go we can a) never have a duplicate in any row, because there aren't enough to wrap around and b) we always fit all of the bricks. This way, we've proved that the bricks always fit with Y equal to the lower bound and thus this solution is optimal. Thanks! $\endgroup$ – Luke Nov 30 '17 at 21:43
0
$\begingroup$

I propose a solution, but don't know if it's correct. Here are the steps :

Let $C$ be the array that stores the colors, and $Y$ the one for the columns, with $Y_i$ the height of column $i$.

  1. Count for each color the number of bricks that have this color.
  2. Sort $C$ in descending order according to the number of bricks of each color.
  3. Create a first column, and put in it all the bricks of color $c_1$.
  4. Create a new empty column.
  5. Now, fill the new empty column with bricks of color $c_2$. Because $C$ is sorted in descending order, after filling this column, $Y_2 \leq Y_1$.
  6. Continue to fill the last column with next bricks until $Y_1 = Y_2$. When finish, create a new empty column.
  7. Repeat 5 with the rest of the bricks.

Here's an example :

enter image description here

First iteration :

enter image description here

First column is full with all the bricks of color 1.

Second iteration :

enter image description here

We have put all the bricks of color 2. We have an empty cell, we can put a brick of color 3 and create a new column.

enter image description here

We now fill the new column with the rest of the bricks.

enter image description here

$\endgroup$
  • $\begingroup$ Ah sorry, you may have misunderstood - the number of columns is fixed, and I want the height of the column to be minimised. So imagine this, except there could only be at most two columns - your minimum height there is 6. Then find the general solution. Looks like we already have an optimal answer though, above ^ $\endgroup$ – Luke Nov 30 '17 at 21:46

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.