×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

bottles in a cupboard

bottles in a cupboard

bottles in a cupboard

(OP)
This isn't really a puzzle in the conventional sense, as I don't have an answer, but it's a conundrum that's been trundling round in my head for some years now, and has given me a lot of fun. I also have to admit I posted it before in Dr Dobbs Journal, but the regular readership there had dwindled to about 10, and shortly afterwards dwindled by another one. I hope you enjoy it as much as I have:

Given a collection of random bottles (circles of a variety of sizes), write an algorithm that will decide whether they fit in a given cupboard (rectangle), and preferably, how to do it.

Note that I'm viewing this entirely as a 2 dimensional question; stacking bottles is not encouraged. All bottles are round without any projecting handles etc.

RE: bottles in a cupboard

Pseudocode to start

If bigger bottle > cupboard then return "Don't fit"
If sum(radius(bottle)) < min(cupboard dimensions the return "Fit"

:)

Cheers,
Dian

RE: bottles in a cupboard

Conceptually, each bottle is bounded by a square, which you're trying to fit in either:

a)  The rectangle of the cupboard
or
b)  One of the empty spaces formed where bottles come together and/or meet the edges of the cupboard


It would seem to make sense to start by trying to place the largest remaining bottle into the smallest available space.  Keep attempting to fit the bottle into spaces until you find the smallest space that can accomodate the bottle or until you have determined that it does not fit.

Do this recursively where you place bottle A in the smallest space where it can fit.  You then place bottle B in the smallest space where it can fit, etc.  If bottle (N) does not fit, move bottle (N-1) to the next larger space and try again.

I have not yet figured out how to best place the squares that bound the bottles into the rectangles.  For instance, does bottle A go in a corner, on an edge, or somewhere in the middle?  Does bottle B get placed bordering bottle A or somewhere removed from it?

It seems that placing large bottles next to each other would help maximize the reusable space between bottles, but I don't know how to calculate this or how to best arrange the larger bottles.

Hopefully this will serve as a starting point for you.

RE: bottles in a cupboard

I don't agree.

Each bottel will be included in a square to compute if the fit into the cupboard, but to calculate the accomodation among the, you need to use a square inside the circle.

This has a mathematical name but I don't know the word in english  

Cheers,
Dian

RE: bottles in a cupboard

I'd begin with a check as to whether the total amount of space needed for the bottles is bigger than the cupboard.  If it is, then the rest of the work is pointlless.

------------------------------
An old man tiger who lives in the UK  

RE: bottles in a cupboard

the squares around a circle can overlap no matter how you rotate them, while the circles don't. Think of the hexagonal pattern you can build with bottles each having the same radius. It's hexagonal. I don't either know how using the squares inside circles would help to find that. It's not a trivial problem.

Two bottles/circles don't overlap if the distance of their centers is greater than the sum of their radiuses.

A circle does not intersect with the outer rectangle, if the x or y coordinate of it's center has adifference of at least it's radius to each side of the rectangle, assumed the rectangle is aligned to x and y axis.

So intersection checks are easy. Finding ideal positions surely will mean to put bottles together as close as you can, so you'd look for points having a distance of radius to each other bottle or a/two rectangle side(s).

We may agree an algorithm should start with the largest bottles,as you may put the smallest ones in between the largest one towards the end and if you start with the smallest bottles you can stuff them near together, but you may not have sufficient area for the large ones then and don't take advantage of the spaces between them. But I'm not sure if it's always best to process bottles sorted by radius descending only.

Bye, Olaf.

RE: bottles in a cupboard

Olaf,

Good points.

My method was admittedly oversimplifying the issue, but I thought it might be a good starting point.  I hadn't taken into consideration a hexagonal approach.

To be honest, aside from trial and error, I'm not sure how I'd solve this if I were putting physical bottles into a box.  I'd probably start with the biggest bottles, but a lot of it would be guessing and rearranging.

RE: bottles in a cupboard

This seems to be a 2D subset of the more general "bin packing" problem.  Algorithms exist.  

RE: bottles in a cupboard

However, the standard packing algorithm doesn't account for open spaces left over when two items are placed next to each other.

RE: bottles in a cupboard

Thought a bit more, and now I'd opt for always using the largest bottle fitting into the smalles available free area. So you start with the largest bottle, and in the second step would use the largest of the small bottles to fit into the corner area.

There's an interesting case if the smalles bottle would not fit, but almost fits. Would it be good to move the largest bottle a bit off the edges to fit the small bottle, or should we wait to see if a large enough area will build up later.

Bye, Olaf.

RE: bottles in a cupboard

(OP)
One of the things that interested me was also the data-structure aspect of how to keep track of how the bottles touch. As several people have pointed out, when three bottles meet, they leave a space between them that may be big enough for further tiny bottles. It's fairly easy to stick one bottle in it, but then you have a very odd shape left over, and in addition to two sensible "triangular" rings of three linked bottles, you have an odd-shaped 4-member ring of bottles.

Putting the bottles in a hexagonal pattern obviously makes lots of sense for bottles that are the same size, and where the cupboard is large. On the other hand, if you think of 4 bottles of diameter x, and a cupboard 2x square, then the 4 bottles cannot be fitted if you start with three touching in a triangle, and must be arranged in a square.

I don't think this is a trivial problem, though it's an everyday one. Even doing a brute-force attempt at putting all bottles in all arrangements is difficult because there are analogue aspects - if we're looking at square and triangular arrangements of bottles in the 2x cupboard, do we ever need to look at other angles?

Practically, I would be tempted to start with a big bottle in a corner, and spread out from there, trying bottles touching adjacent surfaces (wall and other bottle). In the data structure, there needs to be a scheme to keep bottles in rings of objects, with some indication of what side of the bottle we're on, so in placing a new bottle, one trip round the appropriate ring will find all possible objects that could intersect with the new bottle. I dread to imagine how it scales with the number of bottles.

RE: bottles in a cupboard

This is an interesting thread.
At what point in the sorting process do you decide that the cupboard is full? A little bit more computing may just make room for another bottle.

Keith
www.studiosoft.co.uk

RE: bottles in a cupboard

what if the algorithm contains a clause

...
else
  # bottle doesn't fit anywhere on shelf
  drink_bottle()
endif
...


I think after a few of those, you'd no longer care about the problem... winky smile

p5

RE: bottles in a cupboard

Is the problem to get as many bottles into the cupboard as possible or to get a given number of bottles to fit into a cupboard.
This is a multi alogorithm problem.
The first alogorithm should start with treating the bottles as squares, start with the largest and see if they all fit in. The more complex solutions should be invoked if there are still bottles left over.

Keith
www.studiosoft.co.uk

RE: bottles in a cupboard

Hi lionelhill,

I'd not care for the shape of free areas. But with my thought of trying to fit something in the smallest area you'd of course need some knowledge about the areas and where they are located, that's true. Perhaps it would be sufficient to know into which direction vector of each bottle seperate areas exist and how large they are roughly (You may draw and count pixels with a flood fill to determine that rough area).

You can easily minimize the number of bottles you need to chek with, by using the "rectangle-around-the-bottle", which is called a bounding box in raytracing. It's much cheaper to calculate an overlap of two bounding boxes than to calculate the distance of two points. Only with those bottles, whose bounding boxes overlap you need to check their real distance. So even with a large inital area and lots of bottles the number of needed computations don't grow exponential, perhaps linear or even logarithmical.

Bye, Olaf.

RE: bottles in a cupboard

only squares? I think not.

if you put 4 biggish bottles in a square pattern, chances are you'd be able to fit in a smallish bottle in the space inbetween:

e.g. magnum (or even bigger) champagne bottle:
      BBBB
   BBBBBBBBBB
  BBBBBBBBBBBB
  BBBBBBBBBBBB
  BBBBBBBBBBBB
   BBBBBBBBBB
      BBBB

and and Angostura bitters bottle:
sss
sssss
 sss


      BBBB         BBBB
   BBBBBBBBBB   BBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
   BBBBBBBBBB   BBBBBBBBBB
      BBBB   sss   BBBB
            sssss
      BBBB   sss   BBBB
   BBBBBBBBBB   BBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
  BBBBBBBBBBBB BBBBBBBBBBBB
   BBBBBBBBBB   BBBBBBBBBB
      BBBB         BBBB


 

HTH,

p5wizard

RE: bottles in a cupboard

p5wizard, if you notice, where the 4 large bottles come together, there is a rectangular area (actually, and intersection of two rectangular areas) formed in the space between them.  This is where you placed the smaller bottle.

RE: bottles in a cupboard

The idea of only squares is to see if the bottles will fit loosely in the cupboard. No point in complicating things if they will fit in anyway. Take the scenario of 1 bottle in the cupboard.

Keith
www.studiosoft.co.uk

RE: bottles in a cupboard

(OP)
audiopro, you asked about the task: the task is to see if a given list of bottles will fit in a given cupboard.

It's actually based on a real-life situation, where I was trying to put chemical bottles in a steel cupboard; the chemical bottles ranged from 2.5L winchester bottles (probably about 25cm diameter) to tiny vials less than 1cm across, and the defined list of bottles was the huge ramshackle selection on the laboratory floor waiting to be packed safely into a slightly-too-small cupboard.

So many ideas are coming up! p5wizard's appeals greatly if the bottles aren't in their original context.

Audiopro's question made me realise that there is an end-point for a space. Once the gap between a set of bottles becomes smaller than the smallest bottle, it's full up.

I like Olaf's vectors too. I hadn't thought about keeping vectors to other bottles in the vicinity. Also of checking bounding-boxes before checking properly; this amounts to doing a quick check about whether the x or y min/max values overlap before doing any floating point maths.
 

RE: bottles in a cupboard

Ah, I see. drink_bottle() then may not always be a good idea.

Bye, Olaf.

RE: bottles in a cupboard

Well... the drink_bottle() way out was an idea of mine, because I have a similar problem at home. My wife only allows me one shelf in our living room cupboard as drinks cabinet. So when I buy another bottle of liquor, I *have* to make sure there's room for it, even if this means drink_bottle()-ing one of the existing ones. winky smile

But I see that this solution is not always a viable one. Unless of course you're using the lab's chemical bottles as hiding places for... No! You couldn't really...
Or could you?

p5

RE: bottles in a cupboard

Here's a solution treating the bottle as circles, not squares. It's a brute force algorithm since it hunts for a place to fit. And it's not an optimal solution, since the order the bottles are attempted can affect whether they fit or not. But is CAN find a solution and even seems to default to a honeycomb pattern if the bottle are all the same size (which is good).

First assume that the center of any bottle can be no closer to any wall of the cabinet than it's radius. This means we only have to test x,y positions for the center of a bottle that are smaller than the cabinet.

0,0
 +----------------------------+
 | .......................... |
 | .                        . |
 | .                        . |
 | .                        . |
 | .                        . |
 | .......................... |
 +----------------------------+
                         max_x,max_y

That is, if the cabinet is from the vertical lines and dashes, then the center of a bottle can only be on or within the dots (from 0+radius,0+radius to max_x-radius,max_y-radius). And this changes per bottle as they each may have a different radius. Smaller bottles can have their center closer to the wall than a bigger bottle.

Then, to place each bottle, it's just a matter of testing each bottle. It can be placed if you can find an x,y in the cabinet that meets these criteria...

  1) It's center is more than a radius away from any wall
  2) The distance from it's center to the center of any other bottle is greater than the sum of their radiuses.

So, something like this (in bad pseudocode)...

CODE

int    max_x;    // width of cabinet
int    max_y;    // depth of cabinet

for each bottle not yet placed
  for test_x = (0 + bottle_radius) to (max_x - bottle_radius)
    for test_y = (0 + bottle_radius) to (max_y - bottle_radius)
      for b = loop through all bottles already placed
        if distance from test_x,test_y to b_x,b_y > bottle_radius+b_radius
          place bottle
        endif
      endfor
    endfor
  endfor
endfor
Presorting the bottles by their radius will change their placement. From smallest to biggest, verses biggest to smallest will cause different placements. Randomizing the bottle order would give different results.

Since it is a brute force method, you could even try every permutation of bottle order which would cover any and all order advantages and disadvantages.

Do I make sense? Not sure if I described it very well, but it makes sense to me.


 

RE: bottles in a cupboard

I guess Olaf first described it as fitting bottles using their radius. This is the basis of my algorithm.

I think it's wrong to treat the bottles as squares, or any other shape, since calculating intersections using it's radius is so simple.

In other words, if you have bottle A and bottle B, their centers must be farther apart than the sum of their radiuses. A bottle can't overlap another bottle.

 

RE: bottles in a cupboard

Hi SamBones,

well, a bounding box is defined by xmin, xmax, ymin, ymax and intersection checks of bounding boxes are simple comparisons, while checking the distance means computing (x2-x1)^2+(y2-y1)^2 > (r1+r2)^2.

But in fact solving the last equation (= instead of >) in a bottle by bottle algorithm will find an ideal position regarding the first bottle and that makes any bounding box check unneccessary, no matter how cheap it is, if you already know in relation to which other bottle you want to find an ideal position. In fact it turns out that bottle two can be placed on any point of a circle with radius r1+r2 around the center of the first bottle. Quite similar to that rectangle you found for a bottle in relation to the cupboard edges.

But then there could be two or more bottles. Taking two other bottles into consideration will make it an equation finding the intersection points of two circles with radius r1+r3 around (x1,y1) and r2+r3 around (x2,y2), r3 being the radius of the new bottle in that case (x1,y1) and (x2,y2) being the positions of the first two bottles.

And then there were three... This makes the bounding box check helpful in general, especially if you have a huge number of bottles and a veery large cupboard. Keeping track of what bottles are near to some area or point is another way. Spatial or in this case aerial subdivision can help to see, which bottles even don't need a bounding box check, because they are not even remotly neighbor bottles.

In fact many geometrical problems have solutions in raytracing algorithms and taking a look at that topic can help a lot for the bottles in a cupboard problem.

Bye, Olaf.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close