News for hackers. Stuff that matters.
Re:Algorithmic fitting of Japanese candy by esfandia on Wednesday November 16, 2016 @11:50PM (#12974406)
As a student a long time ago I worked with a friend on a 2-d version of this problem for a client who had a framing store. He was trying to cut mirrors of certain sizes in large sheets while minimizing the waste.

The approach we used was to start with a greedy best-first approach (like what is done by the Python library the author is using), and then try to improve on it by exploring the space of neighboring solutions. A "neighbor" here can be created by a pairwise permutation of candies (or mirrors in our case) in the order in which you're trying to fit them in the box, or trying to fit the candy flat instead of upright, etc.

You can do a hill-climb, which means you keep going as long as you can find a better neighbor, or you can use simulated annealing, which accepts a degradation in the solution (to avoid getting stuck in a local optimum) with a certain probability. This probability decreases over time so that you can eventually converge to a solution. Simulated annealing will work better than hill-climb, but its stochastic nature means two runs of the program might give you two different solutions (our client thought that was a bug!).

Re:Algorithmic fitting of Japanese candy by lotyrin on Thursday November 17, 2016 @12:00AM (#12974463)
Yeah, simulated annealing as to the order to place objects in is probably optimal for non-trivial values of n. Also, determinism can often be important and stochastic doesn't have to mean non-deterministic - seed the RNG.
Re:Algorithmic fitting of Japanese candy by kwhitefoot on Friday November 18, 2016 @03:30AM (#12985251)
> seed the RNG

This is something that can't be repeated often enough! Especially when running unit tests.

Re:Algorithmic fitting of Japanese candy by esfandia on Thursday November 17, 2016 @04:08PM (#12981587)
Very true re: RNG seed.