[HN Gopher] Algorithmic fitting of Japanese candy
___________________________________________________________________
Algorithmic fitting of Japanese candy
Author : EndXA
Score : 78 points
Date : 2024-06-19 09:32 UTC (2 days ago)
(HTM) web link (www.candyjapan.com)
(TXT) w3m dump (www.candyjapan.com)
| reedf1 wrote:
| If this is presented at programmers, why not just say "Here is a
| cool practical case of a knapsack/bin packing problem."? The
| article seems to be intentionally avoiding this.
| jerkstate wrote:
| That's what I thought too, then I remembered when I first
| discovered linear optimization, when solving a practical
| problem like this (I used Python PuLP, and coin-or as the
| backend). Not every programmer went to college for computer
| science. Anyways, I really liked the animations.
| carom wrote:
| If anyone is facing a problem like this today, check out or-
| tools [1]. Bin packing is one of their exemplar problems.
|
| 1. https://developers.google.com/optimization/introduction
| jerkstate wrote:
| I started with or-tools, early on I tried changing the
| backend and found that there were details in the problem
| definition that needed to be changed when switching
| backends. Not knowing a ton about the problem space, I
| thought that this inflexibility could get me into trouble
| later, so on the advice of a colleague I switched to PuLP,
| which does not require any code changes to try different
| solver backends, e.g. glpk or coin-or (or gurobi, a
| commercial solver which is supposedly very fast, although
| my problem did not need it)
| bemmu wrote:
| Fair enough. I hadn't personally encountered knapsack/bin
| packing problems before, so it wasn't immediately obvious this
| fell into such a category. Just thought I'd blog my practical
| encounter with the problem as I was exploring it.
| gwern wrote:
| Think of it as a "you could have invented binpacking algorithm
| X too" post.
| zimpenfish wrote:
| > "How hard could it be?"
|
| Having worked on something that required "optimal" box packing
| for deliveries[1], the answer is "very, and then some (and that
| was with the help of that fancy USMIL pallet-packing algorithm,
| IIRC)".
|
| [1] They wanted to use the smallest possible box plus some other
| constraints like "product X cannot have anything on top of it",
| etc.
| freeone3000 wrote:
| "A few minutes" seems... reasonable? Like, you can let it run for
| a few hours on a list, come back in the morning, see which combos
| work. You ship it out once a month, it's gotta be quicker than
| testing them by hand.
| 0xTJ wrote:
| If I'm reading it right, that's a over a minute for only 4
| candies.The "boxes" there isn't a per-customer shipping box,
| but the virtual boxes representing candies.
| freeone3000 wrote:
| Yes, understood, but you're going to ship out a maximum of
| fifteen or so candies or the economics doesn't work. Even
| with really awful scaling, the fact you have an entire month
| to prepare and send the next shipment gives you a _lot_ of
| computing time.
| financltravsty wrote:
| Now parallelize it lol
| Cthulhu_ wrote:
| (2016). Also posted 8 years ago, 50 comments:
| https://news.ycombinator.com/item?id=12973964
| madaxe_again wrote:
| Used to provide ecommerce solutions, from purchase through to
| despatch and beyond.
|
| A frequently asked for feature was box-packing - clients would
| complain that their packers would chuck something tiny in a huge
| box, use loads of packaging, and still manage to have the thing
| damaged on arrival due to shaking about in there.
|
| So we implemented the feature. It worked great. Clients bought
| it.
|
| Literally nobody used it, as humans inevitably decide they know
| better. Instead, we just ended up with clients reporting "the
| boxer told our packer to put a stick of gum in a 1m2 palletised
| delivery!", as that was what the packer would report, when it had
| done no such thing, so all we had done was move the point of
| blame from minimum wage warehouse workers to ourselves.
|
| We withdrew the feature.
| zimpenfish wrote:
| > Literally nobody used it, as humans inevitably decide they
| know better.
|
| Sadly when I was doing this, the packers were great - they'd
| follow the instructions from the service happily. Except the
| service itself would frequently output "garbage" because the
| product people refused to give me a timely feed of product
| dimensions etc.
| madaxe_again wrote:
| Yeah, that was the other half of the equation - nobody wanted
| to provide the necessary volumetric data at several clients,
| and the expectation was that it would somehow... just work.
| We even tried to make it really easy via an exception based
| workflow, sanity checking for wrong units etc., but nah.
| Whole thing was a boondoggle unlike anything else - folks had
| no problem rearranging their entire warehouses to come up
| with more efficient pick routes, but measuring boxes was a
| bridge too far.
| poopcat wrote:
| I loved how you used your skills to address a ~seemingly~ simple
| problem. The explanation was also cool
| resolutebat wrote:
| A friend of a friend worked at NASA on essentially this, except
| that instead of fitting Japanese candy in a box, they were
| fitting cargo into the Space Shuttle. As you can imagine this
| introduces a whole slew of new complications, notably mass
| distribution and that things must be unloaded in a certain order.
| ljlolel wrote:
| This top comment is very similar to this other comment
|
| https://news.ycombinator.com/item?id=12975858
| lkdfjlkdfjlg wrote:
| I think you just exposed someone's alt account.
| ljlolel wrote:
| Oh I thought it was maybe a bot
| lkdfjlkdfjlg wrote:
| Also plausible. When something gets reposted, repost
| previous popular comments. Farming technique popular on
| reddit.
| GuB-42 wrote:
| Not only that, but the optimal solution may involve packing at an
| angle, the most obvious being fitting a candy bar that is too
| long across the package, in diagonal. If you look at some of the
| best square packings, the results can be surprisingly messy[1],
| and few of them have been proven.
|
| It is clear that optimal algorithms are out of the question,
| which is the conclusion of the article, even with the constraints
| of orthogonal placement of simple boxes. In fact, in real life,
| when taking into account packages that are not simple boxes,
| items that can be squished a little and those that shouldn't be,
| etc... I wouldn't be surprised if humans were actually better
| than computers.
|
| [1] https://kingbird.myphotos.cc/packing/squares_in_squares.html
| fuzzythinker wrote:
| The linked page doesn't link back to its parent page which has
| dozens more shape-in-shape packages.
|
| https://erich-friedman.github.io/packing/
| crazygringo wrote:
| I loved reading this, because it feels like it's only the start.
| Now I'm really curious (and if anyone can point me to resources)
| --
|
| 1) Surely there are a bunch of more obvious optimizations, like
| don't place candies where they would fall because of gravity and
| nothing supporting them underneath, or always placing the candies
| in order of largest to smallest, and ignore anything symmetrical
| or rotationally equivalent to a previous solution... and how much
| would this reduce the search space?
|
| 2) What is the actual metric for fitting in a box "in the best
| way"? That lower layers are as full as possible before adding
| upper layers? That shifting of contents is minimized while
| upright? That shifting of contents is minimized in any
| orientation? To minimize small gaps and try to make non-used
| space as contiguous and compact as possible? Or is the box size
| arbitrary and the goal is to find the minimal box volume?
|
| 3) Is there separately a metric for "good enough"? Should the
| metric not to be to fit in a specified box, but rather find the
| smallest box of a set of standard box sizes that can fit the
| candies, with any arbitrary arrangement rather than a "best"? Is
| this a much easier problem, or is it just as hard or harder?
|
| I feel like Amazon must have solved this for all practical
| purposes.
|
| I suspect that it would work well and be fast if you simply place
| items in order from largest to smallest by volume, filling from
| bottom to top, quickly determine which box sizes are too small,
| and then just find the first arrangement that works. Curious if
| there are pathological cases where that wouldn't work?
| zimpenfish wrote:
| > I feel like Amazon must have solved this for all practical
| purposes.
|
| Given that I have, more than once, received a huge box from
| Amazon holding an extremely small item, I don't think they have
| unless they're really bad at packaging stock management and had
| to stuff things into whatever they had available?
|
| (To be fair, it has been infrequent but then I'm just one
| person and I don't believe I'm a statistical anomaly which
| suggests that at Amazon scale, it's happening thousands of
| times a day.)
| crazygringo wrote:
| > _unless they... had to stuff things into whatever they had
| available_
|
| I assume that's exactly what happened.
|
| You don't have to be "really bad at packaging stock
| management", you just have to have a supplier that is late
| delivering certain box sizes on a certain day. Late
| fulfillment is far more common than late ordering when it
| comes to automated systems like these.
|
| (And the more days' worth of box stock you try to maintain in
| case box delivery is late, the more it costs you in
| warehousing. So occasionally getting a box too big is
| probably going to be economically optimal, when the box
| suppliers aren't completely perfect in supplying on time.)
| dwighttk wrote:
| Also all these boxes have to be within reach of the
| picker... I've been getting more ersatz boxes (just kinda
| cardboard wrapped around a single book and glued) from
| Amazon, probably so they don't have to keep a huge number
| of pre sized boxes in stock.
| sqeaky wrote:
| I doubt they have it solved, but I also doubt it is so bad
| that it the software intends for me to get a single USB4
| cable in box suitable for a mini-fridge with a single air
| packing bag.
|
| If I were cording this for amazon, I would start with a known
| algorithm, something like the skyline texture atlas packing
| algorithm. Texture atlases are old school ways to send
| graphics to GPUs and they had to be certain sizes even if
| what you wanted to draw was much small. Like if you want to
| draw single letters, for efficiency packing a whole font and
| related graphics onto a single bitmap and sending it one go
| was usually more efficient. This has to do with batches once
| being very expensive and the only way to send stuff over
| AGP/PCIE to the GPU, I here it is better now but I don't
| really know.
|
| The skyline algorithm starts by lining up all the biggest
| textures along one edge, then it works down the size until
| one edge was full. Then it fills gaps with the largest
| remaining textures. This sometimes fails because "largest" is
| fuzzy, both longest single edge and total pixel can lead to
| quirks so game specific heuristics often need to be used
| (like creating a point system for "largest" where each item
| gets 1 point per pixel and 2 points per pixel if one
| dimension is over X or something). It was called the skyline
| packer because if you ran it with just colored boxes what it
| drew often looked like a low res city skyline, if you rotated
| it or packed along the bottom edge (but you always pack from
| topleft out because of how RAM and storage are efficiently
| iterated and prediction hardware, and other details)
|
| Here is a stackexchange post where they discuss "sorting
| things in scanline order" by which I think they mean height
| and then they pack the top edge left to right. If they packed
| bottom first or if you flip/rotate it you might see the
| skyline effect, if you squint real hard:
|
| https://gamedev.stackexchange.com/questions/2829/texture-
| pac...
|
| But once that is done for the bottom plane of the box other
| stuff can be jammed in on top. Also not doing it in...
| Ruby(?), which is what I think candy Japan used, is likely to
| help. I like Ruby just fine, but I did a pixel comparisons
| routine for 1080p screenshots once in it and it took like a
| minute for one comparison of two images. I wrote a
| c-extension and that dropped to 1 second. I would guess that
| modern multithreaded/SIMD C++ or Rust could knock out most
| Amazon packing sized packing problems exhaustively really
| fast. Still not a great solution, but 10s per package is
| likely faster than the human packers can work and I would
| feel comfortable making such promises to a customer (then
| hopefully deliver ms length solutions).
|
| And then for bigger problem spaces we can talk Monte Carlo...
| some other time.
| autoexec wrote:
| When you're forced to piss in plastic bottles and wear
| diapers to work because the time it takes to walk to a
| bathroom and back can cost you your job, you're not going to
| go out of your way to find the right-sized box for every
| item.
|
| Amazon employees are just scrambling to meet inhumane and
| unrealistic metrics set and enforced by assholes and
| algorithms that have zero concern for human rights, health,
| or dignity.
| Carrok wrote:
| There are many reasons we've stopped ordering from Amazon,
| their treatment of their human employees being the main
| one. The proliferation of fake products and reviews being
| another. The hostile anti-competitive business practices
| towards small businesses is yet one more reason, and I
| could keep going.
|
| I saw a recent poll that many Americans list Amazon as
| their favorite retailer, and it blows my mind. Do people
| really need same day delivery on consumer goods, for the
| not-low cost of the aforementioned problems?
| autoexec wrote:
| Amazon really is a terrible retailer. Their search is a
| complete joke. The reviews are impossible to trust.
| They'll happily send you counterfeit goods. They rip off
| designs and new products to replace with their own
| inferior versions, and even customer service isn't what
| is used to be.
|
| I think the main reason people use/prefer them is
| familiarity and availability. There are lots of things
| that are hard to find in local shops or even other stores
| online. That's in no small part because of what amazon as
| done to brick and mortar retail and their online
| competitors, but I do feel for people who want something
| but have no idea where they'd even start looking for it
| except for amazon. The situation is likely to only get
| worse as search engines grow increasingly less useful.
|
| Even when you want to quit them it can be hard to escape
| amazon. It's work to try to determine the trustworthiness
| of random storefronts you've never heard of before
| entrusting them with your credit card info, and I've even
| heard stories of people who ordered from other sites,
| paying more than they would have on amazon, only to get
| their item in an amazon box.
| crazygringo wrote:
| > _Do people really need same day delivery on consumer
| goods_
|
| No, but what I do need is low prices, reliable
| deliveries, easy returns, and a lot of customer reviews
| with photos and videos so I can get a sense of what the
| product actually is, and what kinds of things people like
| about it, and what kinds of problems they're having with
| it.
|
| Amazon is literally the only delivery service in my area
| that doesn't just leave packages in front of my building
| to be stolen, but actually follows my delivery
| instructions for a code that lets them in -- and even has
| a place to put that in in the first place.
|
| Amazon is the only store where if a product doesn't work
| or wasn't accurately described in the listing, I can
| easily drop it off at Whole Foods or UPS without having
| to box it up and print a label, and I don't have to worry
| about checking four weeks later whether I actually got
| refunded on my credit card because they _always_ refund
| within a couple of hours. I also don 't have to worry
| about submitting a "return request" and then waiting for
| an "RMA number" and then paying for return shipping.
|
| And Amazon is the only place where popular products
| across all categories have thousands of reviews, rather
| than 10 or 5 or just 1, which lets me avoid a lot more
| returns than I would have to make otherwise.
|
| Amazon sure isn't perfect, but the reality is that it's
| both cheaper and better than anything else for a large
| proportion of the things I need to buy.
| Carrok wrote:
| I did not say it does not have any upsides. I said it's
| downsides (externalities) far outweigh them.
|
| > Amazon is the only place where X
|
| It will continue to be that way, until every other option
| closes, and then Amazon reverts to the norms you see
| elsewhere, because they have no competition remaining and
| no reason to provide good service.
| rjmill wrote:
| > I feel like Amazon must have solved this for all practical
| purposes.
|
| Seeing how some of my recent orders have been packaged, I have
| my doubts.
|
| But there definitely seems to be some algorithmic packing going
| on. Here's an example that piqued my curiosity:
|
| I just received two bulk DnD miniature sets, a small 3-pack of
| wolf miniatures, and 2 packs of silicone rings. The miniatures
| and the rings were ordered in separate carts on different days,
| but arrived on the same day.
|
| The bulk miniatures showed up in one package (not surprising),
| but the wolves and ONE of the ring packs were packaged
| together. The last ring pack came in its own package.
|
| Clearly whatever their algorithm is, it's calibrated to avoid
| "overstuffing" packages. But why not group like things
| together? Why put the rings with the wolves?
|
| If anyone has insight into why Amazon's algorithm would do
| this, I'd love to hear about it.
| crazygringo wrote:
| AFAIK, it's from different items coming from different Amazon
| warehouses, and nothing to do with "overstuffing".
|
| In your case, one ring pack came from the same warehouse as
| the wolves, and was the last one. So the other one had to
| come from a different warehouse and so was packaged on its
| own.
|
| Amazon tries to distribute its stock across all its
| warehouses so there's hopefully an item nearby for when you
| want one-day delivery. But with products that aren't super
| popular, there's often _just_ one.
|
| Note that if you delay shipping with Amazon Day or no-rush
| when available, your items are more likely to come in a
| single package, because that gives Amazon the time to send
| items from different warehouses to a single one and then
| package all in one place. This seems to be based on a
| complicated calculation of whether that will save Amazon
| money, so it doesn't always happen.
| alexpotato wrote:
| While working at a Big Bank, a new policy was instituted where we
| had to fill out time sheets. We also had to allocate our
| "budgeted time" into these timesheets (Regardless of what we
| actually did).
|
| It ended up being a bin packing problem that no one actually did
| till I wrote a script to do it for me. This in turn led to some
| interesting conversations with my manager and the head of Capital
| Markets and Banking's CFO.
|
| You can read more details about it here:
| https://twitter.com/alexpotato/status/1296856648435326976
| Strang wrote:
| FYI, Twitter links aren't really reliable any more. When I
| click that link, I see just one message promising a thread but
| no thread.
| cinntaile wrote:
| I also couldn't access the content, but it sounded
| interesting!
| drdebug wrote:
| Also, a Twitter account is required.
| bradyat wrote:
| Here you go:
| https://threadreaderapp.com/thread/1296856648435326976.html
| Strang wrote:
| Thanks!
| nayuki wrote:
| I see all the <canvas> elements are blank because of JavaScript
| code errors.
| bemmu wrote:
| Fixed it.
| vslira wrote:
| A couple of months ago I tried using z3 to create an itinerary
| for my honeymoon. It seemed like a very straightforward
| implementation of a TSP with a few extra restrictions. It's 2024
| and I had an M2 - which is basically alien tech for the period
| when these problems started being solved - so I figured that in 5
| minutes' time I'd have the perfect walking trip in Rome. To quote
| TFA, how hard could it be?
|
| The whole story might become a blog post some day, but the
| punchline is that Moore's law ain't got nothing on NP-hard
| problems
| tredigi wrote:
| > Moore's law ain't got nothing on NP-hard problems
|
| Fun fact, exponential growth is _exactly_ what you need against
| NP-hard problems.
| bubblyworld wrote:
| Moore should go collect his millenium prize =P
| lkdfjlkdfjlg wrote:
| > Hey I know, I'm a programmer, I'll just write an algorithm to
| do it for me. How hard could it be?
|
| Hey I'm a programmer, I'll tell a computer to brute-force it.
|
| To someone who only has a hammer everything looks like a nail.
| deusum wrote:
| This would be a fascinating Code Golf challenge.
| bencyoung wrote:
| I once had a financial bin packing problem at a previous company.
| Rather than going down a dynamic programming route which was
| highly exponential, we decided to use a combination of monte-
| carlo simulation and a very basic genetic algorithm to try and
| find a solution. This made use of the fact that we could try
| solutions extremely quickly, and also timebound the overall time
| taken (something that was important as we had a limited time
| window). We'd still be able to run 1-2e6 different approaches in
| under a second.
|
| Although we couldn't guarentee the "best" approach possible we
| generally came up with something good enough, often in many
| orders of magnitude less time.
|
| A good example of the performance improvements you can make when
| you move from thinking of what the best solution is to what a
| "good enough" one is.
| cypherpunks01 wrote:
| Wouldn't using a constraint programming solver like CP-SAT be
| overall a faster way to do this?
|
| Then one would only have to specify the constraints and let the
| solver optimize a solution, rather than trying to write a
| customized packing problem algorithm from scratch. I'm sure it'd
| be fun, but when trying to best solve a real-world problem, I'd
| think using well-researched tools would be the quickest and
| safest way to go.
| Minor49er wrote:
| I stumbled across a PHP library that aims to solve this kind of
| thing
|
| https://github.com/dvdoug/BoxPacker?tab=readme-ov-file#boxpa...
___________________________________________________________________
(page generated 2024-06-21 23:01 UTC)