Skip to content

Instantly share code, notes, and snippets.

Created April 10, 2017 11:56
What would you like to do?
My solution for the Problem A of the 2017's edition of Google Code Jam: Oversized Pancake Flipper
#! /usr/bin/env python
import sys
def solve(line):
pancake_row = [p == '+' for p in line.split()[0]]
pan_size = int(line.split()[1])
flips = 0
i = 0
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]
flips += 1
i += 1
if all(pancake_row):
return flips
def progress(s):
print("%-80s\r" % s, file=sys.stderr, end='')
if __name__ == '__main__':
if len(sys.argv) > 1:
inputfile = sys.argv[1]
inputfile = 'input.test'
with open(inputfile) as f:
cases = int(f.readline())
for i in range(cases):
line = f.readline().strip()
print('Case #%d: %s' % (i+1, solve(line)))
Copy link

keobox commented Apr 11, 2017


Copy link

yiakwy commented Sep 6, 2017

You don't totally understand the question well. This is a state transfer machine problem. Naive solution consists of Wide First Search(wfs) and mathematical branches trimming. You loop though the array from left to right? I don't believe this is a accept answer.

here is simple mathematics about trmming:
K * flips = x* 2p + y * (2q-1). Where x represents the number of '+' in initial state and y represents the number of '-'. A Filter can be summarised as

math_rule(const char* arr, int l, int K){
    int i, x=0, y=0;
    for (i=0; i < l; i++) {
        if (arr[i] == '+') {
            x += 1;
        } else
        if (arr[i] == '-') {
            y += 1;
    // K*n = x*2*k1 + y*(2*k2 - 1)
    if (x == y and K % 2 == 0 and x % K != 0) {
        return IMPOSSIBLE;
    return 0;

Copy link

yiakwy commented Sep 6, 2017

each state can represented by a bit representation or an unique integer. I am serious. Google's problems need to you to think twice before coding.

Copy link

Consider the case ++-+-++ 3
i don't see any possible solution for this.
here x=5,y=2,k=3.
here x!=y, k%2!=0
So by your logic, its not impossible.
Could you please explain how to flip all values?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment