bottles in a cupboard

[lionelhill]

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.

 

[Diancecht]

Pseudocode to start

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



Cheers,
Dian

 

[KornGeek]

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.

 

[Diancecht]

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

 

[GwydionM]

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 who lives in the UK

 

[Olaf Doschke]

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.

 

[KornGeek]

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.

 

[mintjulep]

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

 

[KornGeek]

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

 

[Olaf Doschke]

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.

 

[lionelhill]

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.

 

[audiopro]

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

http://www.studiosoft.co.uk

 

[p5wizard]

what if the algorithm contains a clause

[tt]...
else
# bottle doesn't fit anywhere on shelf
drink_bottle()
endif
...[/tt]

I think after a few of those, you'd no longer care about the problem... ;-)

p5

 

[audiopro]

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

http://www.studiosoft.co.uk

 

[Olaf Doschke]

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.

 

[p5wizard]

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:
[tt] BBBB
BBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBB
BBBB[/tt]
and and Angostura bitters bottle:
[tt] 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[/tt]



HTH,

p5wizard

 

[KornGeek]

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.

 

[audiopro]

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

http://www.studiosoft.co.uk

 

[lionelhill]

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.

 

[Olaf Doschke]

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

Bye, Olaf.