The interesting problem of cookie dough placement.

BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

File this under the category of Ig Nobel research.

When making cookies, you have to space out the balls of dough on the baking sheet, so that as they spread in the oven, they don't flow into each other, or off the side of the sheet.

So given a size of baking sheet, say 15" x 13" or 40cm by 27cm, and a number of balls of dough to position, say 8 or 10 or 12, how to calculate the best positioning strategy?

You might opt for a rectangular grid:

+--------------+
|  x  x  x  x  |
|              |
|  x  x  x  x  |
|              |
|  x  x  x  x  |
+--------------+
[download]

Or you could go for a diagonal distribution:

+---------------+
| x   x   x   x |
|   x   x   x   |
| x   x   x   x |
+---------------+
[download]

An alternative formulation of the problem: Given a number of cookies to make, an initial ball size (diameter) and a spread factor (what units?), determine the minimum size (and shape) required to accommodate them with a specified minimum gap.

No urgency, and no prizes. Just the fun of taking part. Can it be golfed?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Comment on The interesting problem of cookie dough placement. Select or Download Code

Replies are listed 'Best First'.
Re: The interesting problem of cookie dough placement. by RichardK (Parson) on Mar 10, 2015 at 10:52 UTC
For filling a fixed shape regular arrangements don't always give the best packing density. see Circle_packing_in_a_square for some interesting examples. There's lots of theory around closest packing, it's a fun topic. Circle_packing	[reply]
Re: The interesting problem of cookie dough placement. by hdb (Monsignor) on Mar 10, 2015 at 11:58 UTC
I cannot see any problem with the cookies flowing into each other. Also, my baking sheets have a boundary so the dough cannot flow of the sheet either. In addition, my kids lose patience with placing the dough on the sheet even before the first sheet is filled. So the whole question sounds rather irrelevant to actual cookie making... ...and finally there is a link on Lady_Aleena's home node to get as many cookies as you like.	[reply]
Re^2: The interesting problem of cookie dough placement. by BrowserUk (Patriarch) on Mar 10, 2015 at 13:43 UTC
So the whole question sounds rather irrelevant to actual cookie making... Hence the Ig Nobel reference :) With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^2: The interesting problem of cookie dough placement. by Lady_Aleena (Priest) on Mar 11, 2015 at 21:48 UTC
You can also bypass my node and go right to the Cookies. :) *No matter how hysterical I get, my problems are not time sensitive. So, relax, have a cookie, and a very nice day!* Lady Aleena	[reply]
Re: The interesting problem of cookie dough placement. by QM (Parson) on Mar 10, 2015 at 12:09 UTC
The diagonal is easiest to create, but hexagonal is best packing. Since 6 circles fit around a central circle of the same diameter, you can fit 6 doughballs around a central one. The only issue is whether the height to width ratio of the cookie sheet makes hexagonal optimal, or results in the same number of cookies as diagonal. (Someone will surely produce a table of width/height ratio by arrangement? Assuming the smallest ~~diameter~~ dimension is at least N cookie diameters?) -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]
Re: The interesting problem of cookie dough placement. by BillKSmith (Monsignor) on Mar 10, 2015 at 13:52 UTC
I recently was working on a variation of this problem, but lost interest before I finished. This real application is just the motivation I need to try again. Thanks. Bill	[reply]
Re: The interesting problem of cookie dough placement. by Discipulus (Canon) on Mar 11, 2015 at 21:57 UTC
so what, no intelligent thoughts in this thread? i'd like to read them.. i'm forced to express my sparse thoughts: tessellation? hexagonal tessellation? the cookie is in the center of the tile (the space between cookie can be taken in count), start from the center of the baking sheet and fill the whole. I'm not able to do this. Another idea was related with figurative numbers but it is only worth to investigate for square baking sheets, not so frequent and the OP specified a rectangular shapes. You can enjoy figurative numbers in the Tartaglia's triangle. Then i tried something with Text::Wrap with no brillant results. Obviously you can think about cookies as an AoA and try to approximate the max row lenght and how many rows you'll need. you can even consider an element less for every even row to displace them in a diagonal like structure. But i think is a shaggy task of (square?) recursive approximations. Or you can do as we do at home for cookies: place as they go and two or more waves of cooking! L* There are no rules, there are no thumbs.. Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.	[reply] [d/l]
Re^2: The interesting problem of cookie dough placement. by BrowserUk (Patriarch) on Mar 11, 2015 at 22:44 UTC
You're rushing things! :) My first approach was: Randomly position N dots on the tray. Grow them in parallel, in steps, until one of them touches something -- an edge or another cookie. Move them half way into any adjacent space. Outer ones first towards the nearest edge(s). Inner ones toward the 'new edge' formed by a box 'drawn' inside the outer ones. goto step 2 if any of them are not touching in (at least) 4 places. end. But, a) it is a pain to program; b) it runs like a dog. My thoughts so far are summed up in this image. A diamond pattern is never the right answer. Unless you want to make exactly 5 cookies. Despite that TV chef's seem to use it exclusively! Of course, it could be that their practiced eyes are actually doing a honeycomb arrangement -- whether they know it or not -- and it is just my observation that it looks more like a diamond pattern. Despite the literature, a grid arrangement is the most efficient for any square, or tending to square tray. With honeycomb arrangements, it is important that you go for long/short/long(...) when odd numbers of long-edge aligned rows are required. The choice between grid and honeycomb depends upon the ratio of the sides. There are at least 6 different ratio break points. A table-driven lookup of the ratios to arrangements is probably the best/simplest selection mechanism. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]