Revenge of the Pancakes! (Google CodeJam 2016)

In the second problem of the Qualification Round we find ourselves in a strange IHOP:

The Infinite House of Pancakes has just introduced a new kind of pancake! It has a happy face made of chocolate chips on one side (the "happy side"), and nothing on the other side (the "blank side").

You are the head waiter on duty, and the kitchen has just given you a stack of pancakes to serve to a customer. Like any good pancake server, you have X-ray pancake vision, and you can see whether each pancake in the stack has the happy side up or the blank side up. You think the customer will be happiest if every pancake is happy side up when you serve them.

You know the following maneuver: carefully lift up some number of pancakes (possibly all of them) from the top of the stack, flip that entire group over, and then put the group back down on top of any pancakes that you did not lift up.

What is the smallest number of times you will need to execute the maneuver to get all the pancakes happy side up, if you make optimal choices?

It was at this point I started realizing that these challenges might be less about programming, per se, and more about the underlying thought process.  And I suppose that's what programming really is all about.  Anyone can google the proper syntax for a programming language (I should know, I do it all the time!)  Just like a good math puzzle the trick here is figuring out how to find the answer - actually finding them often becomes pretty trivial.

Granted, for people who are aiming for the top scores in the competition, I'm sure it's as much about micro-optimization as anything else, but my goal (for now) is merely to produce a solution that works.  So for me, this is really just a Riddler puzzle disguised as a programming challenge.  The easy part is getting the input and sending the corresponding output - the trick is working out the function that converts one into the other.

First we can note that any right-side-up pancakes at the bottom of the stack can be ignored.  They're already in the right position and we don't ever need to touch them.  (In the Python solution I originally submitted, I actually removed them from the "stack" but afterwards realized that this was unnecessary and cleaned up the code to the version you'll see below.)

As a simple illustration, let 'U' be an upside down pancake and 'R' be right side up.  Given this stack, how would we turn them all facing up?

U
R
U
R

The second pancake is already right side up, but we're going to have to move it anyway because we need to flip the one below it.  So if we decide to work from the bottom up, so to speak, and flip the top three pancakes, we end up with:

R
U
R
R

Now we need to flip the second pancake, but again we must flip the top one with it.  But doing so will leave us in the exact same position!  It's basically an infinite loop of pancakes, which sounds delicious but is really a problem for us.

Instead let's work from the top down, and just flip every time we hit a change in orientation.  Starting again with

U
R
U
R

Let's just flip the top pancake.  Now we have:

R
R
U
R

Now we need to flip the top two pancakes:

U
U
U
R

And finally we flip the top three pancakes:

R
R
R
R

What we've done is successively made larger and larger groups of pancakes that are all in the same orientation.  That is, each turn we've reduced the number of distinct groups of pancakes by 1 until they're all facing the right way, and we can't do it any faster than that.

The key insight is that, because we're constrained to always flipping from the top of the stack, we'll need a flip for every time there's a change in orientation.  That is, even if pancakes are right-side-up in the original configuration, if there are any upside-down pancakes below them they're going to have to be flipped.

For the Code Jam problem, we don't need to provide the sequence of flips, just the optimal number of flips - which is simply the number of distinct groups of pancakes in the stack (keeping in mind to "ignore" a right-side-up group at the bottom if it exists).

So my Python solution does this by setting an initial orientation of right side up (represented by '+' in the problem's input file) and then simply moving through the stack from the bottom up, counting each time there's a change from + to - or vice versa.  This isn't necessarily the fastest method, but it solved both the small and large variants of the problem in a fraction of a second:

Leave a Reply