Wednesday, June 24, 2009

optimal packing of cupcakes in a box

Sandy had made cupcakes for Cameron's birthday today, and mentioned something in the morning that stuck with me: "The cupcakes perfectly fit into the container". By lunchtime the phrase had wandered back through the hallways of my mind to bear further analysis. Why was it perfect? How did she know? Were they packed hexagonally? I don't think so because a hexagonal pattern usually leaves gaps that seem inefficient with a cursory glance and I wouldn't expect it to look "perfect". More likely they were packed in a grid and it looked neat and tidy. What pattern is actually optimal?

Scott and I bounced around a couple of ideas before I went and pestered Hugh for a little more insight. I had an inkling that there must be a border condition where a square array becomes less efficient than a hexagonal array, and it could be stated with some simple rules like "Once there are more than 25 cupcakes, go hexagonal". Hugh confirmed the hexagonal pattern (and had even done some research on a theoretical problem close to this back in uni), but wasn't convinced that there existed a simple solution to the packing problem.

The first major step was to work out when an additional row could be added to the hexagonal array in the same space as the square array. Since they would start out with the same amount of cupcakes packed along the top, and the rows are parallel, it's only the height that changes. Since the hexagonal array has from centrepoint to centrepoint an angle of 30 degrees instead of straight down of the same length (as the centrepoint to centrepoint is the same as the circles are touching), the hex array has Cos(30) downward space taken, or roughly .866 of a cupcake length packed squarely. From this one can deduce that 7 rows in the hexagonal array isn't enough as it still takes up 6.06 of a square packed row, whereas 8 rows is as it gives 6.92 rows. So 9 rows of cupcakes packed hexagonally should fit into 8 rows of square packed cupcakes.


Since there are 4 rows with less cupcakes, and there is 1 cupcake missing from each row (regardless of how large the row is), there is 4 less cupcakes when hexagonal packing into a perfectly shaped box for square packing. So if the row size is greater than 4 cupcakes you will end up with a net gain by adding the additional row.

8x5

8x5 sounds big. That's too big an area for most storing boxes, too big for the oven and too big for the fridge. Might be better for things smaller than a cupcake, but for this experiment it seems that getting a whole row advantage just isn't going to happen. Therefore square packing is generally the way to go.

So what if there is enough space for 1/2 a cupcake on the edge of the tin? You can still hex pack them without reduction in numbers, but unless you are getting 8 or more rows in you're still not going to get any advantage. so maybe not a whole row, but would it b better to shimmy around some of the edge cakes to make room for possibly 1 or 2 more ?

When I got home I did some digging up on the net and it turns out that this is indeed a tricky problem. I found a couple of papers on the subject and they headed into some heavy maths pretty quickly. Markot (2002) promised a computable function to find the optimal solution, while it built on the groundwork by RL Graham (1996). Although both are looking at a slightly different problem (what is the biggest size cupcake you can make that will still fit X amount into a square box), the fundamentals are the same. If you have a look at Graham's optimal solutions from page 5 onward, it's clear that the solutions are not going to be a simple recipe like I hoped. I'll still dig a bit deeper though to see if there is any packing instructions that might help (Eg: starting in the corner and going along the longest side 1st as tight as you can, etc) but is seems like the general principle is going to serve all but the most persevering cupcake packer.