CODEWITHSUNDEEP
rubyalgorithm
Stussa
Stussa

Reputation: 3415

How To Properly Layout a Grid

I have a number of 'bricks' of different size (width and height) and a container of a fixed size. I want to layout the bricks within the container as compactly as possible starting from the top moving downwards. I've selected the criteria that the grid should be optimal at any step, given the previous steps. So far, I have the following (inefficient) code that doesn't work: 

def fits?(x, y, w, h)
  !((x + w > W) || (y + h > H))
end

def overlaps?(existing, modified)
  existing[:x] + existing[:w] > modified[:x] && existing[:y] + existing[:h] > modified[:y] && modified[:x] + modified[:w] > existing[:x] && modified[:y] + modified[:h] > modified[:y]
end

AXIS = :x

W =  800
H = 6400

sizes = [
  { w: 200 , h: 200 },
  { w: 200 , h: 200 },
  { w: 400 , h: 400 },
  { w: 200 , h: 200 },
  { w: 200 , h: 200 },
  { w: 400 , h: 400 },
  { w: 600 , h: 600 },
  { w: 200 , h: 200 },
  { w: 800 , h: 800 },
]

existing = []

sizes.each do |size|
  size[:x] = 0
  size[:y] = 0

  existing.each do |existing|

    if overlaps?(size, existing)  

      if fits?(x = existing[:x] + existing[:w], y = existing[:y], size[:w], size[:h])
        size[:x] = x
        size[:y] = y
        redo 
      end

      if fits?(x = existing[:x], y = existing[:y] + existing[:h], size[:w], size[:h])
        size[:x] = x
        size[:y] = y
        redo
      end

      case AXIS
      when :x then size[:x] = 0; size[:y] = existing[:y] + existing[:h]
      when :y then size[:y] = 0; size[:x] = existing[:x] + existing[:w]
      end      
    end

  end

  puts "#{size[:x]} , #{size[:y]} , #{size[:w]} , #{size[:h]}"

  existing << size
end

Any ideas how I can fix this? It seems like this would be a prime example for greedy algorithm but I can't figure out what it should be.

Upvotes: 2

Views: 105

Answers (2)

amit
amit

Reputation: 178461

Your problem is NP-Hard, and thus there is no known polynomial solution for it.

An easy reduction from Subset Sub Problem can be shown:

generalized Subset sum Problem: Given a set S and an integer k, return true if and only if there is a subset of S that sums to k.

The reduction: Given an instance of subset sum (S,k)- create a container of size (1,k), and elements are (1,s) for each s in S.

It is easy to see that if and only if you can fill the container completely - the solution to the original subset sum problem is true, and thus the above is a polynomial reduction, and the problem is NP-Hard. (Note: The original problem of "getting it as compact as possible" is actually the optimization problem for this problem, and is still NP-Hard).

Sorry for the bad news.
Some alternatives are using exponential solution (such as backtracking), heuristics or approximation algorithms.
Note that in 1 dimensional space, the problem has a pseudo-polynomial solution, using dynamic programming, but I don't think it can be applied in 2 dimensional space trivially (if any).

Upvotes: 4

Philip
Philip

Reputation: 5917

As has been pointed out by amit, your problem is NP-hard. However, this shouldn't stop you from simply iterating over all permutations of bricks and see which one of them constitutes a best fit. That is, given that you don't have "too many" bricks.

The value of "too many" mainly depends on your computing speed and your available time, but my guess is that values up to, say, 14 are fine.

If the brute-force solution turns out to be too slow, you can still try heuristic or approximation algorithms.

EDIT: your example bricks are looking pretty artificial. Do your brick sizes obey to certain criteria or are they completely arbitrary? Maybe you can exploit constraints on the size of the bricks, if there are any.

Upvotes: 2

Related Questions