Fill an area with best fitting "blocks"

Question

I have some code that generates blocks of text based on a user's selection. The height of these text blocks varies on how many items the users selected. What I am trying to do is ensure that these blocks are arranged on the page in the most efficient manner.

For example, section 1 is 250 points tall and section 2 is 650 points tall. If the user chooses:

400 points worth of content from part a of the form
200 points of content from part b
250 points of content from part c
50 points of content from part d

How can I make sure that part b and part d go into section 1 and part a & c go into section 2?

Here is my code so far:

section1_height = 250
section2_height = 650

#list1 and list2 are the variables that contain the user selections
Column1 = DWIMBLOCK([list1], (18, 430), (LEFT, TOP_BASELINE), (250, 250))
Column2 = DWIMBLOCK([list2], (275, 430), (LEFT, TOP_BASELINE), (250, 650))

columns = [Column1, Column2]
sec1_columns = []
sec2_columns = []

for column in columns:
 if column.height <= 250:
  sec1_columns.append(column)

for shorts in sec1_columns:
 if #This is where I am stuck

As you can see, I've divided my columns into those that are less than 250 points tall, but now I am stuck trying to do something along the lines of if sum of any number of blocks <= 250, assign those blocks to a new list How should I go about doing this? Thanks!

UPDATE:

Here is a rough outline of the layout, just so you can get a clearer picture.

____________________
|#########**********|
|# image #*        *|
|#########*        *|
|**********        *|
|*       **        *|
|*sec. 1 **        *|
|*       **sec. 2  *|
|**********        *|
|#########*        *|
|#       #*        *|
|# image #*        *|
|#       #*        *|
|#########**********|
____________________

The two images are always in the same spot and the same size.
It should also be noted that this is for PDF production, not web use, so CSS and Javascript are not options. The environment that I am working with allows for Python code only.

This is more of an algorithmic question, which looks like a variation on the Knapsack problem. How many parts and sections do you have to deal with in practice? This is to determine whether brute force is an option. — Thijs van Dien, May 24 '13 at 20:49
@ThijsvanDien At the moment I only have 2 sections I am dealing with, although this is a proof-of-concept project at the moment and will most likely end up becoming 4 sections. Brute force is an option for me personally, although something elegant would be nice to have in my toolbox! Also, thanks for adding the algorithm tag, didn't think of that... — Dryden Long, May 24 '13 at 20:54
Appparently, your sections are not all the same size. Are there always exactly 2? Do you have wiggle room to make them larger? For almost any variation of the problem, you will likely not be able to get an exact solution in runtime polynomial in the number of items. — Ulrich Schwarz, May 24 '13 at 20:54
That's just the number of sections, but how many parts? And is my understanding correct that a lower section (1) should always be filled first, before filling a higher one (2)? — Thijs van Dien, May 24 '13 at 21:08
@UlrichSchwarz Yes, my sections are different sizes. I've updated my question with a rough "sketch" of the layout. For now there will always be 2, but eventually there will be 4. I have set a minimum and maximum number of selections for the user, so there will always be more than enough selections to fill section 1 and never too many to overflow the content boundaries. I don't have wiggle room to make them larger, but they do not have to fill 100% of the area, just as much as possible without going over. — Dryden Long, May 24 '13 at 21:09
@ThijsvanDien Sorry, what do you mean by "parts"? Also, yes, section 1 should always be filled first. Some of my form groups have less than the amount to overflow section 1, so there will always be at least one `list` that is less than or equal to 250 points tall. — Dryden Long, May 24 '13 at 21:13
To expand on what Thijs is asking, if there are only say 10 blocks of text that the user could select, and 4 sections to place them, then you have "10 choose 4" = 210 possibilities - which is trivial to brute force. ...if users could select from 100 possible blocks of text , then you have "100 choose 4", or almost 4 million - might take too long to brute force. — Gerrat, May 24 '13 at 21:14
@Gerrat - I see now. The user will have upwards of 15 dynamically sized (height only, width is static) blocks of text to fit into 4 sections total. — Dryden Long, May 24 '13 at 21:17
There are 2^15 combinations to fill the first section, because for each block you can either put it in there or not put it in there. Only a subset of those will be feasible. You pick the combination that fills the most. Then you repeat with the remaining items for the next section. Working on an answer. — Thijs van Dien, May 24 '13 at 21:39
There is a first-fit decreasing algorithm here you could tweak by using different sized bins (it's not optimal ): http://stackoverflow.com/questions/7392143/python-implementations-of-packing-algorithm — Gerrat, May 24 '13 at 21:41

Thijs van Dien · Accepted Answer · 2013-05-24T23:30:45.553

Basically this is solving the Knapsack problem (with lengths as both values and weights) for each section, one after another. I will use brute force for this, but you can look it up and find other methods which are more efficient in terms of speed, but may not give an optimal solution - this one does.

There are 2^b (b being the number of blocks) combinations to fill the first section, because for each block you can either put it in there or not put it in there. Only a subset of those will be feasible. You pick the combination that fills the most. Then you repeat with the remaining items for the next section.

This should give you an idea how to do it:

from itertools import combinations, chain

unassigned_blocks = {
    ('a', 400),
    ('b', 200),
    ('c', 250),
    ('d',  50),
    # ...
}

sections_and_assigned_blocks = {
    ('1', 250): {},
    ('2', 650): {},
    # ...
}

for section in sorted(sections_and_assigned_blocks.keys()):
    best, best_length = {}, 0
    for combination in chain(*[combinations(unassigned_blocks, n)
                               for n in xrange(1, len(unassigned_blocks)+1)]):
        combination = set(combination)
        length = sum(block[1] for block in combination)
        if best_length < length <= section[1]:
            best, best_length = combination, length
    sections_and_assigned_blocks[section] = best
    unassigned_blocks -= best

from pprint import pprint
pprint(sections_and_assigned_blocks)
# {('1', 250): set([('c', 250)]),
#  ('2', 650): set([('a', 400), ('b', 200), ('d', 50)])}

Time complexity is O(s*2^b) (s being the number of sections). In the worst case scenario, sections 1-3 being too small to contain anything, there will be 4 * 2^15 = 131072 iterations. On such small scale, brute force is generally not a problem. However, increasing the number of blocks has a dramatic effect on performance!

Fill an area with best fitting "blocks"

1 Answers1