# Oversized Pancake Flipper - Google Code Jam

### Lorenzo Mele Apr 10, 2017

## Google Code Jam

If you're a programmer and you don't know Google Code Jam, you should definitely go and check that. It's basically a coding competition, I like to call it "the programming olympics".

It's about 4 or 5 years I'm participating, I love it because it challenges my coding skills, and I'm not talking about "making a for loop".

This year I want to share my solutions of the problems, let's start with the first and the easiest one.

## The problem

Here the complete problem text.

You have a row of pancakes and a strange flipper, you have to find the right combination to make them show their *happy side*.

At first I thought it could be easy: just flip the *unhappy* pancakes and see what happens.

*"This is a competition, the solution can't be so simple!"* - my inner voice said. So I proceeded to the other problem to see if they were simpler, after those I came back.

## The solution

Facing the problem again, I had no other ideas but the first one. I decided to give it a try.

You can find the code here, but let me explain some part of it.

To ease the following steps, I get the first part of the input `line.split()[0]`

and I convert the pancake row in a list of binary items.

```
# ...
pancake_row = [p == '+' for p in line.split()[0]]
# ...
```

The list comprehension says something like *"for every character in the string, create an item with True value if the character equals +, False otherwise"*

List comprehension are very powerful, here is the code without it:

```
pancake_row = list()
for p in line.split()[0]:
pancake_row.append(p == '+')
```

Then i go through the list looking for a pancake to flip, now that every item is a boolean, I can check them with a simple `if`

:

```
# ...
pan_size = int(line.split()[1])
# ...
while i < (len(pancake_row) - pan_size + 1):
if not pancake_row[i]:
# ...
```

Now I put the flipper starting from the first *unhappy pancake* and then flip.

```
pancakes: ---+-++-
flipper: ***
flipped: ++++-++-
```

To make it in the code, I just have to `not`

the items: `not False == True`

:

```
# ...
while i < (len(pancake_row) - pan_size + 1):
if not pancake_row[i]:
for j in range(i, i + pan_size):
pancake_row[j] = not pancake_row[j]
# ...
```

I think I could have done it using *slicing*:

```
# ...
while i < (len(pancake_row) - pan_size + 1):
if not pancake_row[i]:
j = i + pan_size
pancake_row[i:j] = [not p for p in pancake_row[i:j]]
# ...
```

Going on with the example, the pancake row evolution should be the following:

```
--------+-++-
***
++++-++-
***
+++++---
***
++++++++
```

With this example we're lucky, because at the end all the pancakes are *happy*. We can check it using a special Python function (you don't have to reinvent the wheel):

```
# ...
all(pancake_row)
# ...
```

Return

`True`

if all elements of the iterable are true

If the pancakes are not all on the happy side, we can argue that it's impossible: the *unhappy* pancake should be at the end of the row, there's no way flip them without flipping the previous pancakes.

## What I learnt

My intuition was right... *I* was right! (not my inner voice).

So next time I could give it a try sooner.

Wow! Nice solution. I have been thinking about it for a while and I still have two open quiestions:

The first one seems to be true (at least the cases tested) but I can't see why. I am not so sure about the second one.

Can you give me any clue about them?

Due to my background I would go for a graph search based solution. The nodes of the graph are the state of the row of pancakes and the neighbors of a node are those states reachable by a flip action.

It is not the fastest one, but it is exhaustive and the solution is optimal.

I cannot show you the mathematical explanation but I have some hints.

Let's take the example of the post but reversed:

These are exactly the same flips made above.

I think the key point here is that you should never touch

happypancakes, unless forced to do so because of a nearestunhappyone.How many rounds do I need to pass if i want to have a job in googleðŸ¤”

I don't know... I think you should be

notable(anything that means) :)Huh, I can't believe the solution is so simple in the end!

I tried to solve it using XOR and discrete mathematics :(

Thanks for the post!

BTW you got a typo ("at the and")

Yes, that was my thought too!

(thanks for the typo ;) )