DEV Community

Oversized Pancake Flipper - Google Code Jam

Lorenzo Mele on April 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 c...

Read full post

Pablo Urcola • Apr 13 '17

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

Does it work in any case?
Does it find the optimal solution (minimum flips)?

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.

Lorenzo Mele • Apr 14 '17

Does it work in any case?

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.

Abdul Hanan • Sep 2 '19

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 ?

theoretically I can see its not optimal in finding of minimum flips
theoretically with complex and long input(where cursor should move backward as well) its incomplete solution !