Algorithmic fitting of japanese candy

Back when I still ran the subscription box Candy Japan, I spent many hours looking for candy and then checking which combinations would fit into a box in the best way.

Hey I know, I'm a programmer, I'll just write an algorithm to do it for me. How hard could it be?

Given a list of candy dimensions, test if they'll fit within the 23 x 17 x 4 cm parcel pictured below.

One necessary but not sufficient condition is that the total volume of the candies has to be less than the volume of the parcel.

Another one is that no individual candy can be too big:

Even with both conditions met, the candy still might not fit.

Below you can see an example of this. The green candy would fit in the box, but adding the red candy is impossible, even though each would fit individually and their total volume is less than that of the box.

To find the true solution, we can try putting candies next to each other in various ways to see if any permutations would fit. Different locations and rotations need to be tested.

Rotating the boxes is simple, just find all the ways to permute dimensions.

If you tested different locations millimeter by millimeter in three dimensions, with just three candies you would be looking at roughly 10²⁰ ways to place them. The program would take millions of years to complete.

Reducing permutations

Testing any combination which leaves space between the candies is useless. You can always just move them closer together and still have a valid permutation. In other words, don't test "islands" of candy.

Now you only need to test combinations where the candies are touching, but you can still slide the candies along each other, leaving as many permutations as you want accuracy.

Sliding the smaller one past the edge of the larger one just takes more space. Placing the smaller one between the edges doesn't take more space, but it isn't helping either.

From this it seems enough to only test combinations where two edges align. The parent box stays put while the child box goes through possible positions. The parent has 6 surfaces, each surface with 4 ways to align the unrotated child.

Below you can see the 144 different alignments after child rotation is also taken into account.

This method can be chained to test for arbitrary numbers of candy, although the permutations explode quite rapidly.

6*144^(n-1)*(n-1)! ^?

The 6 in the beginning comes from the 6 ways the first parentless candy can be rotated. Adding another candy means 144 more ways to attach it. (n-1)! because it can be attached to each of the existing candy boxes (first there is 1 way to attach it, then 2 ways, then 3 ways and so on, all multiplied together).

n	permutations
1	6
2	864
3	248832
4	107495424

At a million tests per second, 4 boxes would already take over a minute in the worst case, although you can abort as soon as you find a fit. With more boxes it would also be necessary to test for intersections with previously added ones, which would also eliminate many recursions.

Conclusion & improvements

So how hard can it be? NP-hard, it turns out.

It would make sense to try some common arrangements first, and to not venture down recursive branches where the previous box combination is already known not to fit.

I am likely to use an existing solution if I adopt this way to find optimal candy sequences, since at this point my JavaScript code is just too slow. For example the Python package pyShipping comes with an implementation which speeds up these tests by using heuristics.

Still, writing this was a fun learning experience. While I didn't learn to solve this problem, at least now I know it's way harder than it seems. 

Thank you for reading