Stuffing Sacks – a coding solution
Back in April, I was being nosy on Twitter and noticed a conversation between a couple of math teachers I follow. Sam J. Shah blogged about an interesting math problem they were trying to solve. The problem goes something like this.
When I go to the grocery store, I come back with a lot of plastic bags.
I stuff them inside each other when I get home. I stuff them until they’re all inside the last bag.
There are 2 ways I can stuff 3 bags. I could stuff one bag into another, then stuff both into the third bag.
Or, I could stuff the first two bags side-by-side into the third bag.
How many ways can I stuff TEN bags?
It’s a really beautiful problem, and I can tell because it ate at me for a whole month and here I am still thinking about it. After a few fits and starts, I could tell it had a recursive nature to it.
I started by counting all of the possibilities. Once I got to 5 and 6 bags, you can see some patterns.
Here are all the ways you can stuff 5 bags.
Abstracting this a little, I turned the drawings into trees instead of bags. The connector means “contains”. The last abstraction shows how many bags are stuffed into the “sub-stuff”. For example, the first big bag contains 1,1,1,1 sub-stuffs. The last two bags on the right have one big bag with a 3,1 sub-stuff. Since there are two ways to stuff 3 bags and 1 way to stuff 1 bag, there are 2 ways to stuff a (3,1) sub-stuff.
You can see the beginnings of a formula emerging.
wts stands for “ways to stuff. To figure out the number of ways to stuff 5 bags, you need to know how many ways there are to stuff 4, 3, 2, and 1 bag. The fifth bag can contain 4 sub-stuffs (4 ways to stuff) or 3 + 1 sub-stuffs (2 ways * 1 way) or 2 + 2 sub-stuffs (1 way * 1 way) or 2 + 1 + 1 sub-stuffs (1*1*1) or 1+1+1+1 sub-stuffs (1*1*1*1). Add them all up and that is 9 ways to stuff the 5 bags.
So I wrote this program to emulate the problem and count all of the ways to stuff “n” bags. I was really proud of it and thought I had it working just great.
I worked really hard on it. There is an array inside one of the objects pre-populated with [1,1,1,2]. There is 1 way to stuff 0 bags. 1 way to stuff 1 bag. 1 way to stuff 2 bags. 2 ways to stuff 3 bags. After this, it follows the algorithm I mentioned above. When the program calculates the number of ways to stuff a new type of bag, it’s added to the array.
It’s a dreadful program to understand. The BigBagStuffer contains BagStuffers. Each BagStuffer contains a decomposition of the BigBagStuffer – it has the sub-stuffs. For example, you can stuff 7 bags by stuffing the 6 remaining bags inside a seventh. Those 6 bags can be arranged (6), (5,1), (4,2), (3,3), (4, 1, 1), and every way there is to add whole numbers to get 6.
The BagStuffer constructor finds all decompositions of a number of length “len”. BagStuffer (6,3) for example contains all ways to stuff 6 bags in a sequence of 3 numbers. It will contain all the ways to stuff (4, 1, 1), (3, 2, 1), and the (2, 2, 2) bags.
The arrCompare() utility function is there to identify unique decompositions. The (2, 1, 1) is the same as the (1, 1, 2) stuff, so the second one is never added to the list.
The math to calculate the number of ways to stuff the bags is on lines 160 through 173.
I thought it was really good and solid and it produces this sequence.
1, 1, 2, 4, 9, 20, 49, 117, 297, 746.
Right about this time, I was checking Sam’s blog again and noticed this link come up.
It describes a problem of identifying the number of unique rooted trees that can be made with “n” nodes. This problem can be modeled as a rooted tree. A bag stuff can be shown as a tree with one root and branches demonstrating the relationship “contains”. This web page above shows the actual sequence of “stuffs” is not what I thought, but it’s this.
1, 1, 2, 4, 9, 20, 48, 115, 286, 719
So I’m overcounting, but how? The method is really sound.
Since 7 bags is the place where I overcounted, I went through the work of drawing out – using rooted trees – every single way to stuff 7 bags. I wanted to see how the overcounting happened.
Not seeing any duplicates yet. But then I found them.
These are all the ways you can stuff 6 bags into a seventh, where you stuff them as (3,3). My algorithm would have shown there are 4 ways to stuff these bags, because there are 2 ways to stuff 3 bags and 2*2 = 4. However, if you look, the 2nd and 4th ways are duplicates and I should have only counted one of them.
I inferred that anytime you have a sub-stuff with a duplicate in the sequence (such as (4,4) or (3,3,1) or (5,5,2)) you will need to count only unique stuffs and not multiply all the ways together as I was doing before.
So how many unique stuffs are there when you have duplicates? I was further confused when I realized that some stuffs will have 3 or more dimensions of duplicates, such as (3,3,3) or (4,4,4). There are 4 ways to stuff 4 bags, but the number of ways to stuff a bag containing 4 stuffs and 4 stuffs and 4 stuffs is not 4x4x4. You have to eliminate the duplicates.
I played with different algorithms for finding the unique stuffs when you have duplicates. This is similar in structure to a dominoes counting problem. How many unique dominoes are in a box? Extend it to “n” dimensional dominoes.
I made a spreadsheet showing this work. It’s messy but I sort of love it for that reason.
The algorithm is shown in the numUniqueTrees() function in my final code. numUniqueTrees() takes two parameters, the number of ways to stuff the bags and the number of duplicates that appear. So if you had a 13-bag containing a (6,6) sub-stuff, the number of unique combinations therein would be given by numUniqueTrees(20,2).
My final “Baggies” program calculates the number of ways to stuff “n” grocery bags and eliminates the duplicates causing the error in counting. This one gives me the sequence shown in the proper link, but it breaks down somewhere in the high teens due to the recursion – I’m overflowing whatever memory Khan Academy’s little environment gives me. 🙂
Made using: Khan Academy Computer Science.
My code is horribly messy. If I inherited this code from someone else and had to maintain it, I’d be bitter. It’s still so exciting to me because of that sense of “flow” I had as I wrote it. Recursion is head-splitting. I had to plan hard for some of it and some of it just sailed off the keyboard as I coded, and I loved that feeling.
Thanks to Sam and Matt Enlow for a really fun problem-solving experience!