Algorithmic Fitting of Japanese Candy #
This video explains the complex algorithm for fitting Japanese candy into a subscription box. The goal was to automatically find the best combinations of candy that would fit within a specific box size.
Key Challenges #
- Volume isn't enough: Even if the total volume of candy is less than the box volume, individual candies might be too large or their shapes might not fit together.
- Computational Complexity: Testing all possible permutations of candy placement becomes computationally expensive very quickly. With just three candies, there are roughly 10^20 combinations to test.
Optimization Strategies #
- Eliminate "islands": Only test combinations where candies are touching, as moving them closer together is always a better solution.
- Align edges: Only test combinations where two edges of a smaller candy align with the edges of a larger one. This reduces the number of possible placements to 144 per candy.
Complexity and Limitations #
- The number of permutations still explodes exponentially with additional candy.
- Testing intersections with previously placed candies would further improve the algorithm, but also increases complexity.
Conclusion #
- The problem of finding optimal candy combinations is NP-hard, meaning it becomes exponentially more difficult to solve with larger problems.
- Existing solutions like pyShipping provide better performance using heuristics.
- The author learned about the complexity of this problem and abandoned the project due to increased postal rates.
Top Quotes #
Hey I know, I'm a programmer, I'll just write an algorithm to do it for me. How hard could it be?
So how hard can it be? NP-hard, it turns out.
...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.
Action Steps #
- Learn about NP-hard problems: Understand the limitations of algorithms for solving certain types of problems.
- Explore existing optimization solutions: Look into libraries like pyShipping for efficient ways to tackle complex fitting problems.
- Analyze computational complexity: Learn how to estimate the time and resources required to solve a problem based on its complexity.
Additional Information #
- Candy Japan no longer exists due to increased postal rates.
- The author can be found on X/Twitter at @bemmu.