## 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.

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

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

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

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

------------------------------

An old man who lives in the UK

## RE: bottles in a cupboard

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

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

## RE: bottles in a cupboard

## RE: bottles in a cupboard

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

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

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

...

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...

p5

## RE: bottles in 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

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

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

## RE: bottles in a cupboard

Keith

www.studiosoft.co.uk

## RE: bottles in a 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

Bye, Olaf.

## RE: bottles in a cupboard

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

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_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

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 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

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.