# Nesting Items based on quantity and sizing

857 views

### Sam Potter

Jun 20, 2022, 8:03:13 PMJun 20

I am looking for someone who can help create a spreadsheet for a somewhat complex situation.

I have physical products that I ship and in order to reduce my shipping costs I am able to nest some products inside others. I have the problem of figuring out what items can nest inside of others from a large list of items.

My products come in sizes that range from 5" to 16". I can nest up to 3 items inside one another if it is a 12", 10", and 9". The 9" goes inside the 10" and they both fit inside the 12".

I may have a list of items to ship such as:

0, 8" items
4, 7" items
0, 10" items
0, 12" items
0, 11" items
0, 6" items

Using a Google Sheet I would like to enter in the quantity of the different size items I have and then have a report that tells me how many nestings I can do and with which items in the most efficient manner.

So in this case I may have:

3 nestings of 12", 11", 10"
2 nestings of 11", 10", 8"
1 nesting of 11”, 8”, 7”
1 nesting of 8”, 7”, 6”
1 nesting of 8”, 7”,
4 single items of 7”

If it is acceptable to do so in this forum, I am willing to compensate for a quality solution to this problem.

Thank you

### Sam Potter

Jun 21, 2022, 9:31:16 AMJun 21
Sorry, the list of initial items I have for example would be as following:

4, 8" items
8, 7" items
2, 10" items
1, 12" item
3, 11" items
1, 6" item

### R Tichy

Jun 21, 2022, 11:03:10 AMJun 21
But you'd never nest more than 3 items?  I mean like 5, 7, 9, 12" ?

### Sam Potter

Jun 21, 2022, 11:25:48 AMJun 21
On a very rare occasion we will nest 4 items but again, that is rare and never more than 4. I would still say 3 items would be the limit as 4 is very rare.

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-c...@googlegroups.com.

### R Tichy

Jun 21, 2022, 11:53:17 AMJun 21
Is there only one answer that is correct, to you?

based on:
4, 8" items
8, 7" items
2, 10" items
1, 12" item
3, 11" items
1, 6" item

Is:
[12,8,7]
[8,7,6]
[11,8,7]
[11,8,7]
[11,10,7]
[10,7]
[7]
[7]

A solution, for example?

On Tuesday, June 21, 2022 at 8:31:16 AM UTC-5 s...@crystaltones.com wrote:

### Stephen Schlager

Jun 21, 2022, 12:25:39 PMJun 21
Are these singing bowls you are shipping? If not, do the shapes matter?
Are there more rules? For example can you put three 5" objects in one 16" next to each other (or two 7" next to each other inside 16") or is there only one inside another (unless there's a nested one in that)?

### Sam Potter

Jun 21, 2022, 2:18:02 PMJun 21
There is not necessarily only 1 answer that is correct. Generally we want the sizes to be fairly close in size as we nest them as nesting a 5" inside a 12" can be too loose. So I would say that a general rule of thumb would be that as we nest, we desire to be within 3" when possible of the items nested above and below. So, while your solution of 12,8,7 could work, a better solution would be 12,10,7  or 12, 11, 10 for example.

Great questions!
 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-c...@googlegroups.com.

### cbmserv...@gmail.com

Jun 21, 2022, 2:40:29 PMJun 21

At what difference in size would you not allow nesting?

In the situation below, you indicated 12 and 8 would not be a good combo. Your desired less than 3 inch difference is fine, but at what point would you say no to a combo? Or is the 3 inch difference the limit?

### Sam Potter

Jun 21, 2022, 2:51:54 PMJun 21
These are bowls and the shapes are fairly consistent with the exception that some are much taller than others so we would ultimately want to nest Tall bowls with other Tall bowls when possible.
We can only nest items that are smaller or bigger than the item next to it. For example, you cannot nest two 5" items together because they are the same size and one would not fit into another one and we would never place items NEXT to one another inside a much larger item.

Excellent questions.

### Sam Potter

Jun 21, 2022, 2:51:58 PMJun 21
Anything greater than a 4" difference we would not want to nest.

Here is a simple spreadsheet with just the sizes we are dealing with and a very simple calculation formula to determine the total weights of various types of products (the weights are not a factor in this problem) https://docs.google.com/spreadsheets/d/1EzyvSStTYVasb-lwz_JBbxdeOm2E7WiFmkpzCFTJBVg/edit?usp=sharing

### cbmserv...@gmail.com

Jun 21, 2022, 3:02:02 PMJun 21

Ok this seems like a nice little project. Would be happy to do it for you, unless others want to help.

Let me know and I can get started on it. To do so, please make a copy of the spreadsheet and provide edit access to this account.

Thanks,

George

### Stephen Schlager

Jun 21, 2022, 4:30:42 PMJun 21
It is an interesting problem. I don't have time at the moment to go all in, but wouldn't mind seeing how your solution progresses as others help you.

One thing - You say some are much taller than others. Seems like the height of the bowls should be considered.
You might have a situation as follows:
Say you have 3 bowls {diameter x height} like so  {10 x 10} , {9 x 8} , {9 x 5}
If the algorithm ignores height you might end up with a solution with two shipping boxes of approximate sizes:
1) Box size 10x10x10 - nesting the {9 x 5} bowl inside the {10 x 10} bowl
2) Box size 9x9x8 - sending {9 x 8} bowl separately

I think since most shipping companies add cost to shipment based on box dimensions it would be better to ship two shipping boxes of approximate sizes:
1) Box size 10x10x10 - nesting the {9 x 8} bowl inside the {10 x 10} bowl
2) Box size 9x9x5 - sending {9 x 5} bowl separately

This is a basic example, and easily spotted as a human packing the bowls, but with lots of bowls of various sizes, the algorithm could get pretty far off and you might not know...after all the idea is to trust the program's output and not check it against your judgement each time.

Also you could have a similar situation with weight depending on how each shipping company calculates their shipment costs (a 5lb box and a 25lb box) might be different than two 15lb boxes...
However I think ignoring this for now is a good start and keeps the solution more simple. Start with a basic approach, and then refine later if you want to cut costs even more.

Finally - are there any materials that can't be nested in other materials? That could matter too.

### Sam Potter

Jun 21, 2022, 5:03:38 PMJun 21
Stephen, great observation.

In the future we may need to identify two types of items, Standard and Tall but that will be phase two of this project. Regarding materials, we do not have restrictions there due to our packing methods.

### R Tichy

Jun 21, 2022, 7:06:26 PMJun 21
With no regard to bowl shape, I have this working, I think.

Example:
nesting( [ [3,11], [1,12], [1,6], [2,10], [8,7], [4,8] ] ) = [ [ 12, 10, 7 ], [ 11, 8, 7 ], [ 11, 8, 7 ], [ 8, 7, 6 ], [ 8, 7 ], [ 11, 10, 7 ], [ 7 ], [ 7 ] ]

Where pairs are [quantity, size].

function nesting(bowls){

function buildNests(){

function balance(n){
if (n != 0){
d[n] -= 1
if (d[n] == 0){
delete d[n];
sizes = sizes.filter(function(x){ return d[x] > 0 })
}
}
}

while (d != {}) {
let nest = [];
while (sizes.length < 3){
sizes.push(0);
}
nest = [sizes[0],sizes[1],sizes[2]];
balance(nest[0]);
balance(nest[1]);
balance(nest[2]);
nest = nest.filter(function(x){ return x > 0 })
if (nest > []){
nests.push(nest);
}
else{
break;
}
}
}

var d = {};
var sizes = [], nests = [];

bowls.forEach(function(row){
d[row[1]] = row[0]
});
for (const size of Object.keys(d)) {
sizes.push(parseInt(size))
}
sizes.sort(parseInt).reverse()

buildNests();

var singles = nests.filter(function(e){
return e.length == 1;
});

singles.forEach(function(s){
var triples = nests.filter(function(e){
let m = Math.min(...e);
let dif = m - s[0];
return (e.length == 3 && (dif < 4) && (dif > 0))
})
if (triples > []){
let n = nests.pop();

let i = nests.indexOf(triples[0])
let j = nests[i][1]
nests[i] = [ nests[i][0], nests[i][2], n[0] ]
if (j in d){
d[j] += 1
}
else{
d[j] =1
}
}
else{
let n = nests.pop();
let k = n[0];
if (k in d){
d[k] += 1;
}
else{
d[k] = 1;
}
}

});
nests = nests.filter(function(e){
return e > [];
});
for (const size of Object.keys(d)) {
sizes.push(parseInt(size))
}
sizes.sort(parseInt).reverse()
buildNests();
return nests;
}

### Stephen Schlager

Jun 23, 2022, 9:15:41 PMJun 23
When I ran this with a small example I got two items placed together that shouldn't be:
nesting( [ [1,12], [1,6] ] ) = [ [ 12, 6 ] ]

I didn't look in depth at your code, but did see it looks like you account for the 3" difference [ (dif < 4) && (dif > 0) ] ...

Maybe it's a simple fix, looks like you wrote clean concise code.

### R Tichy

Jun 23, 2022, 9:32:47 PMJun 23
Truthfully, the 3" max difference requirement is not checked for during the first pass when I nest starting from the largest bowls and work to build the tightest nests.  The 3" check is only made when I am matching small single bowls with "triples" which then have their "middle" size removed and the smaller bowl added in.  (A "triple" is a nested set of three that is identified as appropriate for a smaller bowl to be nested in the current smallest bowl of the three.)

fwiw, I know a decent bit about shipping and shipping costs, and I'd be very surprised if shipping two boxes was better than using a lot more packing material (bubble wrap?) for the set you tested.

I'm sure the two of you can figure out how to modify my code, if not.

I would be very interested to see the final solution though, when decisions and code has been written to move data between the sheet and the custom functions, so I hope you'll share that.

Rob

### Stephen Schlager

Jun 23, 2022, 11:50:58 PMJun 23
I'm not actively working on this, or helping the original poster privately...Just what I've posted here.
I was just curious about the problem and when I came back was interested in where it stood. So I just ran some tests of the code you posted out of curiosity, since your code looks interesting and well written.
The solutions I was getting looked good most of the time. I was just throwing out an example in case it was something that was either unexpected or was helpful. Not knowing how your code worked, I wasn't sure if it might have a ripple effect with larger sets of bowls.

nesting( [ [1,16], [3,11], [1,12], [2,7], [1,10] ]) = [ [ 16, 12, 11 ], [ 11, 10, 7 ], [ 11, 7 ] ]
The above only has a couple places with 4" and they look like good packagings to me from a practical standpoint...and actually when I think about it, the more bowls you add, the more likely you'll find nicer pairings probably.

I don't disagree with you about putting more padding between two bowls that are more than 3" apart to avoid two boxes, I was just trying to stick to what the poster requested earlier in the thread.

If time allows this weekend, I may try to dabble with it some too...Your bowl swapping after an original nesting is a creative idea.
When I first saw this posted, I thought it was just going to be an "implement and be done" problem, but the more I think about it, the more complicated it seems...at least finding an optimal packing in general.
I think having a heuristic packing is more attainable and I think you've already done that with your solution.

### R Tichy

Jun 24, 2022, 8:04:03 AMJun 24
Oh, wasn't certain you two weren't conversing elsewhere.

In that case, I put together a GSheets function with the code and showed example usage.

### Stephen Schlager

Jun 26, 2022, 3:59:29 PMJun 26
I spent some time on this yesterday.
I tried a few different approaches:

1) Greedy approach
The smallest bowl tries to join a nest, if it can't it tries to find the next smallest number to start a nest with, if it can't it creates it's own nest...Now there's one less bowl, and the loop starts over until all bowls are gone.
2) Greedy approach (with alternating)
Basically the same as 1, except each time through the loop it alternates between choosing the smallest bowl not in a nest and the biggest bowl not in nest...I tried this since sometimes with the Greedy approach you get bowls at the end that can't be partnered cause their all the same size or close to the same size.
3) Ugly approach
In this one, every bowl has a set of potential partners (all other bowls it's allowed to be nested with [ basically a bowl of a different size that is <= 3" bigger or smaller than it ] ).
Then the "ugliest" bowls who have the least potential nesting partners get to go first and pair themselves up. They also pair themselves first with the "ugliest" bowls first out of their potential partners.
4) Towers
This one I built "Towers" which are linked bowls following the rule of not being more than 3" larger than the bowl under it (A tower might be: [14, 11, 9, 8, 5])
Each time in the loop I make the longest link possible (a tower). Also bowls prefer linking themselves to the largest bowl first, then gradually getting smaller until the bowl is only 1" larger than the bowl looking for a mate. If it can't find one, the link ends and the tower is constructed and the loop continues starting a new tower until all bowls are gone.
The idea was then to take the completed towers and mod 3 chunking them into nests of 3 until there was a leftover nest with less than 3 bowls for each tower. The leftovers from all towers would then be thrown back into a pool to be paired up hopefully.
I only got half done with this one before thinking it wasn't going to work well and also I was a bit tired of working on the problem.

I didn't implement a massage step fine tuning my "first pass" for any of these.

I ran some comparisons:
- No algorithm always won.
- Robert's algorithm was usually the best (although sometimes had small occurrences of larger than 3").
- Many of mine had wild swings where sometimes it would win or tie with Robert's and other times it would be the worst.
- Robert's was consistently the best or close to the best.

The magic of Robert's it seems is the nice second step idea to throw middle bowls back into the pool of bowls to be processed (I think the idea being, the middle ones are most likely to be nestable together?).
I'm not sure if any of these could be combined in a smart way to improve into a final more successful algorithm.

It would not be hard to run them all (they run quick) and take the best performing one for that case and give it to the user as the best choice, or show all solutions (maybe with any discrepancies listed like two instances of bowls 5" apart or whatever to let the user decide).

With all that said...kudos to Robert for finding such a successful algorithm as quick as he did.
I'm still curious if there's an algorithm that can always find the best solution...I'm beginning to think there is not other than a brute force approach which would be complicated to implement anyway.

Since I'm very curious about this problem now...I'd like to post this on another site with more viewers, maybe stackoverflow and see what a larger community might be able to do with this problem.

If anyone is interested, I can of course share what I've done, but I'd need some time to clean it up a bit as I was working quickly to try a bunch of ideas.

### R Tichy

Jun 26, 2022, 9:41:54 PMJun 26
I did a lot of programming for ERP/warehousing systems and while I was never asked to try and do a similar task, I thought it would be much more difficult.

I've been trying to figure out how to turn it into a programming challenge at codesignal.com, but those challenges like unique answers, and I am certain there are many equivalent answers.

My best advice in business programming is to solve of 80-90% of a problem "affordably," and then leave the stickier decisions to the people that haven't been laid off. (dark humor)

Another interesting complication would be to try and address "shape" within the same function instead of expecting a user to segregate by shape before using the function.

### Sam Potter

Jun 27, 2022, 2:36:43 PMJun 27
I have been gone for the past week since posting this problem but am back and looking to complete finding a solution. What additional questions can I answer?

- Sam

 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-c...@googlegroups.com.

### R Tichy

Jun 27, 2022, 4:59:11 PMJun 27
Well, the function I offered is "free" so if it doesn't meet your needs, you better tell us why.

### Sam Potter

Jun 27, 2022, 5:17:19 PMJun 27
This is great and I love seeing collaboration from others and contributing myself to collaborations. I have sent in my request for Edit capabilities so I can test various scenarios I would encounter and explore the scripting to see how it is accomplished.

Everyone who has offered their feedback is greatly appreciated and has my gratitude.

Thank you very much and I look forward to exploring future scenarios where I can provide valuable input to others.

 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

### Sam Potter

Jun 27, 2022, 5:20:13 PMJun 27
It works great and absolutely meets what I was initially looking for. Thank you very much.

-Sam Potter

### R Tichy

Jun 27, 2022, 5:36:12 PMJun 27
I saw that you were trying to get edit access, and the easiest way (generally, that I know of) is for you to just do "File>Make A Copy" and you'll get the script with it.

### Sam Potter

Jun 27, 2022, 5:49:11 PMJun 27
Yes, I did make a copy and got full access to everything. Thank you again and great work!!!!

 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

Message has been deleted
Message has been deleted

### Stephen Schlager

Jun 27, 2022, 10:33:52 PMJun 27
Good luck Sam. Good job Rob.

I'll post an update if I end up posting this to another site to canvas a larger audience.
It reminds me a bit of the bin-packing problem. Although I never was an algorithms guy (I just like puzzles and problems), I once had to implement a heuristic approach to the "bin-packing" problem to put files of various sizes into zip files that could only be so large because of the web protocol. The bin packing problem is NP hard, and though this seems easier (maybe?), this very well could be also. So I'm curious about it.

I'd love to hear if you get the problem on that site or do anything else with it Rob.

### Sam Potter

Jun 28, 2022, 3:24:26 PMJun 28
One thing I found is that the nesting script does not work if the number of items is null or 0. Also, when I have 0 for the number of 9" bowls, it is still attempting to place 5, 9" bowls in the nesting options.I also have a null amount for 7" bowls but the calculation is still trying to add 2, 7" bowls into the nesting.

This is definitely on the right track but there seems to be a slight error still happening.

I have a coppied spreadsheet located at https://docs.google.com/spreadsheets/d/1DqrG1ntcS7ymtmZX_p7GtaHpOWG8Vuu32SBsMU9R2Xo/edit?usp=sharing with full edit capabilities that shows what I am referring to.

Thanks,
Sam
 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

On Mon, Jun 27, 2022 at 8:33 PM Mission Brewery <missionbrew...@gmail.com> wrote:
Good luck Sam. Good job Rob.

I'll post an update if I end up posting this to another site to canvas a larger audience.
It reminds me a bit of the bin-packing problem. Although I never was an algorithms guy (I just like puzzles and problems), I once had to implement a heuristic approach to the "bin-packing" problem to put files of various sizes into zip files that could only be so large because of the web protocol. The bin packing problem is NP hard, and though this seems easier (maybe?), this very well could be also. So I'm curious about it.

I'd love to hear if you get the problem on that site or do anything else with it Rob.

On Monday, June 27, 2022 at 2:49:11 PM UTC-7 s...@crystaltones.com wrote:

### R Tichy

Jun 28, 2022, 3:34:58 PMJun 28
Starting around line 51 in the appscript:

pairs.forEach(function(row){
if (row[0] > 0){                     <===== Add this
d[row[1]] = row[0]
});

### Sam Potter

Jun 28, 2022, 3:39:18 PMJun 28
I will try that now Robert. Thanks for looking at that and sorry if I messed you up at all as I was possibly poking around in there while you were in there.

- Sam

### Sam Potter

Jun 28, 2022, 3:55:38 PMJun 28
That worked great. Thank you!

On Tuesday, June 28, 2022 at 1:34:58 PM UTC-6 robt...@AOL.com wrote:

### CBMServices Web

Jun 28, 2022, 4:43:02 PMJun 28
Hi Sam,

Have you tested the solution I sent you?

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-c...@googlegroups.com.

### Steve Schlager

Jul 5, 2022, 12:10:02 AMJul 5

### cbmserv...@gmail.com

Jul 5, 2022, 1:18:25 AMJul 5

Interesting. However, it would have been nice if you requested a solution in JavaScript so we can understand better what he was suggesting to do with his solution.

Sent: July 4, 2022 9:10 PM
Subject: Re: [Apps-Script] Re: Nesting Items based on quantity and sizing

### Steve Schlager

Jul 5, 2022, 2:31:50 AMJul 5
Yep. I don't post much on there and my brain is just used to JS being assumed...Anyhow, too late for that now.
I'm working on making a JS version...but it's slow going since I don't know Python and only get time here and there between my several jobs.
I'll definitely share it on here once I finish, but maybe someone will beat me to it.

### Sam Potter

Jul 6, 2022, 9:36:35 AMJul 6
Hi Steve, sorry for the delayed response. I have been gone on vacation and then out sick with Covid the last 2 weeks. I am going to take a look at it today and greatly appreciate you putting that together.

I will let you know later today once I have had a chance to look at it.

Thank you again!
Sam
 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

Message has been deleted
Message has been deleted
Message has been deleted
Message has been deleted

### Stephen Schlager

Jul 7, 2022, 6:02:37 PMJul 7
I've implemented the stackoverflow developer's solution in Javascript as well as his improved solution.

You can find the code via:

Additionally, I've included Rob's original algorithm along with the other two with results comparisons. Feel free to add your own algorithm and compare it to the others.

### Sam Potter

Jul 8, 2022, 9:34:28 AMJul 8
Hi Steve,

I really appreciate your efforts in this one. This was just phase one of the problem I need to solve and to complicate things more I will be introducing various case sizes that potential bowl nests can go into. And then on top of that, additional rules that will help define what size boxes the various nesting sizes should go in. As soon as I have the rules defined for this I will introduce it to you and the group again to see if anyone wants to take a stab at that.

I am interested in checking out your JavaScript when you get to that point and thank you again.

Warm Regards,
Sam Potter
 Crystal Tones SAMUEL G POTTER | Operations / Technology Officer5684 S 900 E Murray, UT 84121(Cell) 1-360-989-4748 (Office) 1-385-799-2800 (EMAIL) s...@crystaltones.com

DISCLOSURES:  ANY MATERIAL EXCHANGED BETWEEN THE PARTIES HERETO IS FOR DISCUSSION PURPOSES

On Thu, Jul 7, 2022 at 6:10 AM Steve Schlager <steve.a....@gmail.com> wrote:
No worries Sam. Frankly the post in the other forum is a bit academic and a lot of effort to wade through (at least for me).

I'm taking the guy's code that solved it and making it Javascript as time permits. I'm close to finished, just a few bugs to fix. When I finish I'll share it for whoever is interested.
As stated previously Rob's solution is right most of the time and should get your shipping costs down and save you some headache figuring out how to package things.

For me I got interested in the academic idea of an algorithm that always finds the best solution. Maybe I'll create a sheet with some metrics as well.

On Wednesday, July 6, 2022 at 6:36:35 AM UTC-7 s...@crystaltones.com wrote: