Algorithmic fitting of Japanese candy | Hacker News Reader

Algorithmic fitting of Japanese candy

candyjapan.com

114 pointsbemmu50 comments

The very first line is "Candy Japan ships candy to subscribers twice a month." I read that and had to pause. Wow. I don't think if I tried for months that I could have done a better job describing _any_ business in such a small number of words. And that line and the last line are the only "marketing" this article does. It's subtle too, because the first line is completely necessary to introduce why the author wanted to algorithmically fit candy. It's just ... beautifully done. I'm not being sarcastic when I say any of that. Candy Japan has written a number of content-marketing articles and they're always informative and interesting. Obviously others agree because they bubble to the top of HN frequently.

Candy Japan's articles should probably be mandatory reading for anybody wanting to start a small, online business, because this type of marketing is gold.

My only complaint is the "dark pattern" of not listing prices. There are prominent calls-to-action to enter your email address and sign up. I don't want to enter my email address unless I want to sign up, which is dependent on the price.

"example@example.com" now has an email from Candy Japan, and I obviously can't click on the verification link there.

After some digging, I found https://www.candyjapan.com/gift, which lists prices:

    24 shipments! ($348.00, sent over one year)
    Dozen shipments ($174.00, sent over six months)
    Eight shipments ($116.00, sent over four months)
    Four shipments ($58.00, sent over two months)
    Two shipments ($29.00, sent over one month)

Doing the math, it's $14.50 per box. Even though many levels are listed, there is no quantity discount, which is not obvious - I'm not good at multiplying 29 or 14.5 by powers of 2 in my head. If it was $20 or $30/month, that would be a little different.

Some more digging with a disposable email finally brought me to https://www.candyjapan.com/subscribe, which shows that it's still $29/month whether gifting or subscribing. Furthermore, anyone can go to that page and see the price. No, the tiny "subscribe" link on the main page under the comic does not link there - it's an anchor to the email entry point.

Perhaps A/B testing says differently, but I would like the business a lot more if there was a big label, above the fold, on the main page, that said "$14.50 per box" or "$29 per month".

The home page says "For $29/month (shipping included) we'll start hunting for interesting sweets for you here in Japan twice a month, then box and ship them directly to you by Japan Post."

It's easy to miss, which is unfortunate, but I would classify it as more of a marketing oversight than as a "dark pattern" which would imply intent.

Yup, missed it. Agree it's an oversight, but it's still annoyingly difficult to find if you miss that line.

Lol I read that line and thought to myself "sold where do I sign up"

You have run into a monster.

https://en.wikipedia.org/wiki/Packing_problems

Packing of regular shapes in a confined space is hard enough... much less a general collection of cuboids in a 3D box. On the bright side, if you find a good way to do this you will have accomplished a lot more than packaging candy.

Here is an annealing approach that might lead somewhere (although I'm not sure... I am no expert on packing and really smart people have been thinking about this for hundreds of years)

Instead of thinking of sharp cubes as geometric objects, think about each one as a function from space to 0 or 1. (0 if you're outside the box, 1 if you're in it).

Blur each cube function with a Gaussian, then try to position these blurry functions in your box so that they are well-separated. This positioning can be done using ordinary numerical optimization as a 'feasibility search': your objective function can be the maximum of the sum of the functions throughout the box, searching over the space of positions that lead to the cuboids being within the box's boundaries. You have to scale the blurred functions so that they all individually have the same max. Declare a positioning infeasible if the max of the sum is above the individual max.

The positions you get from this will be a first approximation of where you should put your candies.

After you've found the positions, reform your cube functions, this time using a sharper/thinner Gaussian. Then run the optimization again using the previous step's result as your first guess.

The idea here is that hopefully the problem of shifting blurry functions around to be uniform is a lot easier than the strict packing problem which most people try to avoid solving.

Also it's pretty amazing to me that you have made headway in this using Javascript. Good luck!

The trunk capacity of cars in defined as the number of a certain kind of box you can fit into it. Car manufacturers naturally want to maximize this number for their cars. Traditionally there are expert packers (pretty nice job if you ask me) who do this, but there are now some algorithmic approaches:

http://www.joachim-reichel.de/publications/diss.pdf

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

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.

> seed the RNG

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

Very true re: RNG seed.

A friend of a friend used to work at NASA on how to pack the Space Shuttle, which is essentially the same problem... except that things need to be taken out in the correct order, through a small hatch, with a robot arm and in zero gravity.

TL;DR: Packing candy is rocket science.

Did he try to write an algo for that?

This sounds like the kind of problem were I immediately decide that using some good ol' fashioned human rationale is the best way to proceed. Too many rules and conditions. Software is sometimes more difficult than its alternative.

As others have said, I would go with simulated annealing, or any non convex optimization algorithm you're more comfortable with.

But first I'd investigate what's really the gain of closely packing the candies. Would shipment costs increase with a bigger non completely filled box? wouldn't a non rigid bag be better? Do non closely packed candies get damaged with shipment? Do customers prefer closely packed candies?

I mean, let's say you get good enough local optimum configurations, then you have to exactly follow them packing the candies one by one... wouldn't it be easier to throw everything in a bigger bag and ship that?

There's something minimalistic and artful in trying to come up with the smallest packaging possible, which will probably appeal to the same people who enjoy Japanese candy, and Japanese culture in general.

And it doubles up as a 3D puzzle for the user! Take everything out and try to put them all back in. And if you can't, just eat some of the candies to make it easier to solve.

The only reasonable solution to this is to create a cnc machine that will pack the candy

because it's cool

Yup.

This is one of those things that 99% of customers will not notice. Some small percentage may prefer the closely-packed box over the bag but not be able to articular why.

And some very small percentage will see it, recognize the difficulty in continuously doing something like this over the "throw it in a bag and ship the bag" approach, and think it's amazing. Those are the fans that will repost your stuff, talk about you to others, etc.

This type of stuff is what creates the "1" in the 90-9-1 split.

We were presented with this problem in a course in constraint programming where we used a library called Gecode [2] to implicitly express and effectively search the solution space in terms of variable relationships/constraints. I remember symmetry breaking being a central concept [3].

[1] https://en.wikipedia.org/wiki/Constraint_programming [2] http://www.gecode.org/ [3] https://en.wikipedia.org/wiki/Symmetry-breaking_constraints

Yes, but even better there is the global constraint geost [1] which is specifically for this purpose in k-dimensions; see also [2] for a more detailed presentation.

Unfortunately, Gecode does not provide it (and you would have to express it in form of other, more lower level constraints which gets quickly complicated), and neither does Google's OR-tools which have a nice Python interface.

There is JaCoP which provides the geost global constraint and makes it available via the declarative MiniZinc problem description language so one needs not to use the Java API.

[1] http://sofdem.github.io/gccat/gccat/Cgeost.html [2] https://www.sics.se/~matsc/docent20090209.pdf [3] http://jacop.osolpro.com/

Sometimes hackers want to solve the hard problem, but not the most important problems.

Check out some of the comments.

This company might want redirect some focus on first principal issues like [1] consistently shipping 2 boxes a month to customers, [2] insuring the candy is of high quality, or [3] making sure basic user / subscription management works on their webapp.

It takes discipline to direct resources at what will really move the needle the most.

I agree. When I was re-analyzing one of CJ's experiments using Bayesian decision theory ( http://www.gwern.net/Candy%20Japan - speaking of wanting to solve hard but not important problems...) what I was struck most by was the incredibly high cancellation rates he was reporting. Clearly something is going wrong there.

BTW, I really like the concept of Candy Japan. But twice a month and $29 is too much. Hopefully they can get monthly or bi-monthly subscription soon.

I registered Candy Japan. I wanted to try it once for that month. Their subscription system is a mess. I accidentally registered twice because there were no confirmation page or confirmation mail once you registered. Also there is no login screen on their page, their "manage subscription" page didn't show my account. So I registered twice and then thought it didn't work and forgot about it (should have check my bank).

Well, they billed me twice and sent me two candies, once I received my candies it was too late for next month too so I bought 4 candies in total.

I tried to de-register but site didn't work. When I tried to login:

"Sorry, could not find subscription or you had several."

What a stupid warning, it can't de-register me because I have two subscription, and it fails to give me any actual information.

Then I contacted support, told them to delete my account. They again failed and sent me more candies next month, I asked refund and they did give and successfully terminated my account after that.

Anyway, be careful if you only want to register for one month. Their system is so bad, I don't know if it is intended that way so people can accidentally buy more candy or they are just plain bad.

Agreed. I eventually cancelled because it was rare to receive two packages per month, more like one in one month, two in the next, three in the next, none for the month after that and so on. I lost track of how many packages I was supposed to have received vs. how many I did receive, which I'm sure was less than how many I was supposed to receive.

The other issues I had was with the general quality of the candy being shipped seemed to get lower and lower as time went on, somehow the "DIY candy" packs being favored over chocolates or sour candies, and whilst this wasn't much of an issue, the blog posts explaining what you were supposed to receive never seemed to be in line with what was actually delivered. Maybe the posts were posted a bit too early, or too late. The issue being that if you didn't get the package the blog post was talking about, you didn't know if the candy was suitable for vegans, vegetarians, and you had to guess your way through the DIY candy, ultimately resulting in a mess.

I'm sorry. If you didn't receive a complete refund for all the shipments you did not want, you can contact me at my personal email me@bemmu.com.

It is alright, I ate and shared extra candies. But you really should work on your login/registration system, instead of trying to solve NP problems.

The downside to being an engineer in the e-commerce space ;)

Engineers want to solve NP problems.

Customers want stuff to arrive on time and cheap.

I suspect shipping is the real problem. Here in Japan, while there are several shippers who give great service at low prices within the country, there are almost none that do the same for international shipping.

I live in rural Japan in a famous tea growing area. Many of my neighbours are tea growers. They are desperate for ways to export their tea cheaply. I briefly looked into helping them out, but shipping looked impossible. They will sell me 100g of first cut shincha for $3-5 (in vacuum packed foil packages even!). But shipping? It will raise the price 5-10x. I bet the vast majority of his price is shipping :-(

The way to ship internationally is by slow boat. It's super cheap. What you want to do is ship by the palette (or better by the container) and then have someone on the other side forward it on with local shipping. But that takes both volume and cooperation of another entity.

For a small 1-2 person operation, it's infeasible.

Exactly, especially now with yen being so expensive. For the past 6 months I've spent $29000 on candy and $26000 to ship it. If I used airmail with tracking it would cost 3 times as much.

How come I can order something fairly heavy from China for $3 with free shipping? Of course they do WAY more volume than Japan, but it still makes no sense, it costs me more than that to ship it across town, and it's literally the same guy doing the local delivery.

It really depends on the company you were dealing with. They almost certainly have someone stateside who are dealing with customs, picking up containers and unpacking them. With enough volume, it's quite doable.

Basically, for shipping by sea, weight is barely important. Volume is the most important thing. I forget how much it costs to ship a container (like those big containers you see at ship yards or on trains), but essentially it is little enough that cross atlantic/pacific is essentially free. If you have enough to fill up a container and you have someone who can do the paperwork on the other end, it is totally feasible.

I shipped my bicycles from England to Japan on a partial palette. I can't even remember how much I paid... Maybe $100. And that's for a third party shipping company that came to my door, wrapped my bike boxes, put them on a palette and found space in an unfilled container. The hitch? I had to go to the docks in Japan, fill in the paperwork, do the customs inspection, etc. It took me a whole day. To have someone else do the work for me on that side would have cost $1000.

If you can't receive large shipments, then they have you over a barrel and they will suck the money out of you. Probably there is a business opportunity there...

I forget how much it costs to ship a container

Order of magnitude: thing "new iPhone" not "new MacBook." If that leaves anyone flabbergasted, yep, that is why containerization is one of the most important technologies in the world.

And the current price may be even more surprisingly lower because we live through a period of shipping capacity glut, see the bankruptcy of Hanjin Shipping.

They abuse an old international mail agreement. When mail is sent between 2 countries, it might go through several countries and it becomes difficult to calculate costs and manage forwarders.

Since it was assumed that anyone who receives a letter would write back (mind you this was thought up way before online shopping in the 1860s) it would average out, so basically every nation in the world agreed to forward foreign mail for free, assuming it would average out. This only works for things that are send as mail and not as packages.

https://en.wikipedia.org/wiki/Universal_Postal_Union

All of the world's postal services have peering agreements, the same as for Internet traffic.

IIRC the Chinese government will subsidize exports from china.

> They will sell me 100g of first cut shincha for $3-5 (in vacuum packed foil packages even!).

To put this in perspective for those unfamiliar with green teas: 100g of a good shincha in the US would cost at least 3x that much. For example, Upton's, my favorite specialty tea retailer who has good prices, will sell you an excellent shincha (88th Night Shincha https://secure.uptontea.com/store/item.asp?itemID=TJ87 ) but 100g will cost $34 - excluding S&H (~$5).

BTW, If your neighbors are looking for a good way to sell tea, you should try pointing them over to Yunomi. I've met the guy who runs this site and he's very passionate about trying to help small Japanese growers:

http://yunomi.life/pages/about-yunomi

> From this it seems enough to only test combinations where two edges align.

That can't be correct in general. Imagine a 9x9x9 cube, and nine 3x3x1 squares. This can fit into a 9x9x10 box, with the squares all on one side of the big cube. However, four of the squares will share only one edge with the cube, and one of the squares will share no edges with the cube.

Like this? http://imgur.com/a/61EnF

I probably misunderstood, but it seems to work. "Align with edge" I meant aligning with any edge of any box which is already in play.

Hmm, as long as you don't always use the big cube as the baseline, that works.

There are still cases it won't work; in fact, sometimes the optimal packing is pretty strange. For example, check the fifth optimal square packing: https://en.wikipedia.org/wiki/Square_packing_in_a_square

Wow, that's a more bizarre case than I would have imagined. I started with the assumption that rotating them other than multiples of 90 degrees would never help, but looks like I was wrong.

Well to be fair, packing a physical good in that type of arrangement would often cause breakage of the diagonal object. So establishing flush edges seems like a good assumption here.

There's also an upper bound on how bad an axis-aligned solution can be. And, on a less mathematical note, weird diagonal packings are counter-intuitive to everyone and you're not likely to get customers complaining that you packed inefficiently just because you missed an opportunity to use one.

There was a Kaggle competition on this subject a couple of years ago, plenty of interesting solutions : Packing Santa's Sleigh - https://www.kaggle.com/c/packing-santas-sleigh

Our company runs an SaaS shopping cart and we had to work in similar algorithms to estimate the size of the package when two or more products are packaged together, we would then send the sizes and weight of the total package to the different shipping carrier to get shipping estimates.

Correct me if I'm wrong, but this seems like a convex optimization problem, assuming you know the sizes of the boxes and volume to pack them in. I think you could define a set of equality/inequality constraints and solve the problem efficiently. For further reading: http://www.stanford.edu/class/ee364a/

It's not. The intersection constraints are not convex. You could use sequential convex programming to find a local optimum.

edit: to back up my claim: the feasible set of a convex optimization problem must be convex. suppose you have two squares of side length 1 at positions x1 and x2. The following two solutions are feasible:

    x1a = (-2, 0), x2a = ( 2, 0)
    x1b = ( 2, 0), x2b = (-2, 0)

but their midpoint is not:

    x1c = (x1a + x1b)/2 = (0, 0)
    x2c = (x2a + x2b)/2 = (0, 0)

therefore the feasible set is not convex.

Reply on news.ycombinator.com