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.
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.
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() and I convert the pancake row in a list of binary items.
# ... pancake_row = [p == '+' for p in line.split()] # ...
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(): 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
# ... pan_size = int(line.split()) # ... 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) # ...
Trueif 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.
Top comments (7)
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 happy pancakes, unless forced to do so because of a nearest unhappy one.
This is not fair !!
I was trying to solve it with other ways.
solution is so simple that its raising Questions..?
does its a complete solution ?
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 ;) )
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) :)