Baggage, carbs and algorithms

Computational Thinking, MSU MAET

Nothing like a few brain burners to show the usefulness of computational thinking skills. I asked Meghan, my partner in crime and second grade teacher, to work with me in an attempt to solve two problems, using guidelines from Basic Strategy for Algorithmic Problem Solving.  The tools presented in this algorithm were exhaustive and exhausting; we only applied some of them  the two problems.

The first problem involved eight suitcases, identical in every way, except one was lighter than the rest. You have use of an balancing scale to compare their weights, with the goal of performing the fewest number of weigh-ins in order to identify the lightest briefcase. I had come across this problem before, most likely on Car Talk, so Meghan took over the problem solving and did an admirable job. She identified the necessary information in the problem including the data provided and what was being asked, just as she would ask of her students on a test. She determined she had all the information needed, so now it was time to find the algorithm.

She mentally walked through the non-optimal solution of dividing the suitcases in half to weigh 4 vs 4, thought about how that solution is achieved, then tried to see if there were any shortcuts along the way. Meghan realized that dividing eight suitcases into two equal groups at the start would always take three times to weigh them, so the beginning of the algorithm needed to be rethought. She sat in the couch for a few moments, pondering, then muttered “What if…no…wait.” Only when pressed did she explain her potential solution of dividing the suitcases into three groups: (1,2,3) (4,5,6) (7,8). (1,2,3) vs (4,5,6) can be weighed and three possibilities can result. If (1,2,3) was lighter, then the second step would be to weigh (1) vs (2), keeping (3) to the side. If either of those weighed is lighter, then you have your suitcase. If they are equal, the remaining (3) was lighter. The same idea could be applied if (4,5,6) was lighter. If (1,2,3) was equal in weight to (4,5,6), then you know (7,8) contains the lighter suitcase, so it’s trivial to find the lighter one.

FindLightest(group):
Divide group into thirds: A, B, C
Compare A to B
If A < B, FindLightest(A) or return A if only one suitcase in group
Else if B < A, FindLightest(B) or return B if only one suitcase in group
Else FindLightest(C) or return C if only one suitcase in group

We tried to see if this algorithm would work with other number of suitcases, and could see that it would allow you to find the lighter case in one step up to three suitcases,  two steps for up to nine suitcases, and three steps for up to 27. This makes sense intuitively since we are left with at most a third of the original group after each weigh-in to continue to compare.

The second problem was more insidious. A number of differently sized pancakes are randomly arranged in a stack, and the task is to sort them such that they are in order from smallest on the top to largest on the bottom. The only way to change the order is to place a spatula under part or all of the stack and flip them over. I decided to start by trying a few three and four pancake cases out. After a few tries, it became apparent that one way to get the pancakes in the right order was to put the spatula under the largest pancake that wasn’t in the right position, flip it to the top, then put the spatula under the position you are trying to get it to and flip again. Repeat until all the pancakes are in the right position. Since you can only flip the top portion of the stack, it would make sense to work from the bottom up, i.e. get the largest pancake on the bottom first, then the second largest, until you reach the top.

This bottom-up algorithm will always get to a solution:

Until all pancakes in correct position:
 Find largest not in correct position
 if at top
   flip to correct position
 else
   flip to top

Before I reached a general solution though, it could be seen that there could be multiple ways to get a given configuration sorted, some not as fast as others, so I visualized this by working backwards from the final desired state by creating a tree, as seen below for four pancakes:

photo (1)

As soon as I sketched this out, it became apparent that there were some cases where a faster solutions could be found than the algorithm described above. For instance, with a (1,2,4,3)  stack, it only takes three flips if working towards as upside-down stack, then flipping everything over: (1,2,4,3) -> (3,4,2,1) -> (4,3,2,1) -> (1,2,3,4) as opposed to four flips with the bottom-up algorithm described above (1,2,4,3) -> (4,2,1,3) -> (3,1,2,4) ->(2,1,3,4) -> (1,2,3,4). How to determine which path to take?

One key aspect seems to be to try to make clusters of pancakes, substacks that are in order or reverse order, as large as possible as you go through an algorithm. This is easier to see with a larger stack, such as the 7 pancake stack presented to us to solve: (3,6,2,1,7,5,4). There are 6 (or n-1, if n is number of pancakes) possible flips that could be done to it, since flipping the top pancake doesn’t change the state. The possible stacks after one flip are: (6,3,2,1,7,5,4) (2,6,3,1,7,5,4) (1,2,6,3,7,5,4) (7,1,2,6,3,5,4) (5,7,1,2,6,3,4) and (4,5,7,1,2,6,3). The first stack has the largest clusters: (6,[3,2,1],7,[5,4]), a size 3 and a size 2 cluster. The other possibilities have at most two size 2 clusters. So let’s continue with (6,3,2,1,7,5,4).

As you head further down the tree, there are only n-2 possibilities after the next flip, as one possible flip would be identical to the same order as the parent arrangement two levels up. So there’s five arrangements after the second flip, but only three of them keep the already made clusters, as it would be anti-productive to break up clusters you already created. These arrangements would be ([1,2,3],[6,7],[5,4]), (7,[1,2,3],[6,5,4]) and ([4,5],7,[1,2,3],6). Hard to tell where to go from here – is it more valuable to have a greater number of smaller clusters, as the first arrangement has, or fewer but larger clusters? Going further down the tree with these arrangements suggested that it’s better to go with fewer but larger clusters. After all, you are working towards what could be thought of as one cluster with all the pancakes in it. It’s also desirable to have the largest pancake in one cluster next to the largest pancake in the next cluster that could be merged together, since you will only have to flip the top cluster (once it’s on top of the stack) to merge the two clusters together.

We would thus proceed with merging these two clusters together, so flipping the entire stack gives us ([4,5,6],[3,2,1],7). Now we can flip the top cluster over, merging the two clusters into ([6,5,4,3,2,1],7), and then flip that top cluster to have the pancakes in order. I don’t know if this is optimal, but trying this “make and merge clusters” logic with other initial states consistently meets or beats the bottom-up algorithm.

photo (2)

CT skills were vital in thinking about this. Abstraction was obviously highly utilized. I used lots of specific cases to see if I could develop a general way of solving the problem. Looking for patterns was a big part of that. I could use a computer to help examine the patterns more efficiently than my pencil and paper let me. Of course, thinking with algorithms was key as well.

Leave a Reply

Your email address will not be published. Required fields are marked *