Search code examples
arraysalgorithmsortinggroupinggraph-algorithm

Algorithm for grouping colored boxes into squares

Assume a two-dimentional (width * height) array where each element is a colored box.

The count of boxes is n. The count of colors of all boxes is limited to a constant c, and c <<< n.

Now for a given k, find a way to group these boxes into larger squares, so that the count of all groups (squares) is closest to k, where the group item can be 1, 4, 9, 16, 25, 36, ... boxes inside (so that they can form a square).

Within each group (square), the elements must all be the same color. Single element squares are valid. Squares cannot overlap.

Solution 
  • list all 2 by 2 squares of same colored boxes
while count of squares != k
  if count < k
      if possible to split largest square into smaller squares
          split
      else
          stop
  else 
      if possible to combine 4 small squares into one
          combine
      else
          stop