Once a shoe company in the South of Brazil (Novo Hamburgo or maybe São Leopoldo) had an employee who was long due retirement and they wanted to put some software in place to do his job, which was to cup up leather in the most efficient manner possible.
Try as they might, they never reached this man's efficiency.
People studying the traveling salesman problem have long known that a human being can get alarmingly close to an optimal route in minutes. The best answer can take days, weeks, heat death of the universe, but some teenager can get around 95% on the first try.
We’ve spent a lot of time trying to figure out how humans do these approximations, but honestly I think we could spend a lot more time looking at it.
You raise some serious points, which I shall try to address; my limited domain expertise notwithstanding.
> if the kids don't get into fights over who gets the reindeer-shaped cookie cutter, and who gets the star?
This, in comparable situations I have witnessed, should not be a problem. The kids should be able to fight quite easily over nuances such as depth of icing, area of icing, colour of icing etc. And in the case of embossed designs, who gets the star motif and who gets the reindeer. Fighting among children is guaranteed to be preserved at current levels under my proposed system; it doesn't upset the status quo.
> Danish Christmas cookies don't have icing. We only get to express ourselves through the shape.
This is perplexing. Perhaps a national education programme might be initiated - using Danish influencers on YouTube, promoting the use of icing and showing how it is made. (You'd start with water icing and move up to royal icing etc.)
Furthermore, one might use this cookie dilemma ("Danish cookies don't have icing") as a metaphor to address other fixed biases in the Danish psyche that might benefit from frank and open discussion.
This is amusing but IRL you'd just roll up the extra dough and cut more cookies out of it until you can only get one cookie, then eat the rest of the dough. This is your reward.
A real life example of a related problem I know is cutting leather, say to make shoes. There, the shape to be cut is constant, but the surfaces they have to cut from (hide shapes and their defects) are different for each hide.
Every year I need to convince my wife that we need more Christmas triangles. We do through in the occasional square, but with enough triangles we can render anything!
What does rectangle backing have to do with cutting cookies? Has the author ever rolled dough in their life?
Has anyone, ever, rolled dough into a perfect rectangle, let alone a square? Dough comes out in an ellipse, or a rounded rectangle at best. You can’t roll 90° corners. And if you could, the amount of time needed to roll the dough again is the least taxing part of your day, so it’s moot anyway.
If your packing algorithm involves corners, it’s a nonstarter for running the experiment in reverse. Or at the very least, with dough.
Roll the dough over shallow rectangular moulds. I did this over triangular molds when making croissant rolls. Rolling the dough over the thin mold ensures an even thickness, rather than cutting shapes out of an uneven hand-rolled blob.
Worked at Cinnabon many years ago: you can roll out dough to a rounded rectangle pretty easily. The trick is to work diagonally corner to corner. The radiused bits get cut off with the ends of the rolled, uh, "log" of cinnamon rolls before you cut the finished rolls off of the log.
There's some waste but they're shooting for consistent rolls. A home baker making cookies would optimize differently.
The article, as is typical in my experience, loads fine with javascript disabled. Browsing with javascript off by default is the only way to stay sane on the modern web I think. Most sites work better with javascript disabled.
That would be fittingly. Irony refers to a counter-intuitive result (and yes I know that some one more grammar nerd than me can probably tell me its more complicated). In this case, a giant cookie pop-up on an article about cookies could be described as fitting or coincidental but not ironic. It could be ironic if there was a giant cookie pop-up on an article about why one should never eat cookies.
The article doesn't really make it clear that there's an actual result, showing that many two-dimensional packing problems are equivalent to finding real roots of multivariate polynomials, and many problems are ∃ℝ-complete. (∃ℝ-complete is kind of like NP-complete for real numbers. The ∃ℝ complexity class lies between NP and PSPACE.)
The paper shows that various specific problems are ∃ℝ-complete. One such problem is packing simple polygons with at most 8 corners into a square, with rotation and translation. (E.g. cutting polygonal cookies out of dough.) Another is packing objects bounded by segments and hyperbolic curves into a square with translation but not rotation.
Random fact from the paper: there's no agreement on how to pronounce ∃ℝ-complete.
I've discovered that an area is most easily filled when the shapes of the individual components used to fill the area are similar.
So, rectangles with rectangles and ellipses with ellipses.
That's how I increase packing density but I can't prove it works.
26 comments
[ 3.8 ms ] story [ 50.2 ms ] threadTry as they might, they never reached this man's efficiency.
We’ve spent a lot of time trying to figure out how humans do these approximations, but honestly I think we could spend a lot more time looking at it.
And this research is from a Danish university, Danish Christmas cookies don't have icing. We only get to express ourselves through the shape.
> if the kids don't get into fights over who gets the reindeer-shaped cookie cutter, and who gets the star?
This, in comparable situations I have witnessed, should not be a problem. The kids should be able to fight quite easily over nuances such as depth of icing, area of icing, colour of icing etc. And in the case of embossed designs, who gets the star motif and who gets the reindeer. Fighting among children is guaranteed to be preserved at current levels under my proposed system; it doesn't upset the status quo.
> Danish Christmas cookies don't have icing. We only get to express ourselves through the shape.
This is perplexing. Perhaps a national education programme might be initiated - using Danish influencers on YouTube, promoting the use of icing and showing how it is made. (You'd start with water icing and move up to royal icing etc.)
Furthermore, one might use this cookie dilemma ("Danish cookies don't have icing") as a metaphor to address other fixed biases in the Danish psyche that might benefit from frank and open discussion.
Cutting cigar wrappers (https://en.wikipedia.org/wiki/Cigar#Wrapper) out of tobacco leaves is a similar problem (https://patents.google.com/patent/US4275627 has a good description). I once read about software for doing that, but can’t find that.
Has anyone, ever, rolled dough into a perfect rectangle, let alone a square? Dough comes out in an ellipse, or a rounded rectangle at best. You can’t roll 90° corners. And if you could, the amount of time needed to roll the dough again is the least taxing part of your day, so it’s moot anyway.
If your packing algorithm involves corners, it’s a nonstarter for running the experiment in reverse. Or at the very least, with dough.
There's some waste but they're shooting for consistent rolls. A home baker making cookies would optimize differently.
The paper shows that various specific problems are ∃ℝ-complete. One such problem is packing simple polygons with at most 8 corners into a square, with rotation and translation. (E.g. cutting polygonal cookies out of dough.) Another is packing objects bounded by segments and hyperbolic curves into a square with translation but not rotation.
Random fact from the paper: there's no agreement on how to pronounce ∃ℝ-complete.
The "Existential Theory of the Reals" is (ambiguiously) the ∃ℝ complexity class, a formal language, and an algorithmic problem. More info: https://en.wikipedia.org/wiki/Existential_theory_of_the_real...
Disclaimer: I didn't know anything about ∃ℝ before looking into this, but thought others might be interested in a bit of background.