Skip to content

Instantly share code, notes, and snippets.

@greenkey
Created April 10, 2017 11:56
Show Gist options
  • Save greenkey/1fd7a44c0b110ec9cd6f69b99b000adf to your computer and use it in GitHub Desktop.
Save greenkey/1fd7a44c0b110ec9cd6f69b99b000adf to your computer and use it in GitHub Desktop.
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
return 'IMPOSSIBLE'
def progress(s):
print("%-80s\r" % s, file=sys.stderr, end='')
if __name__ == '__main__':
if len(sys.argv) > 1:
inputfile = sys.argv[1]
else:
inputfile = 'input.test'
with open(inputfile) as f:
cases = int(f.readline())
for i in range(cases):
progress(i)
line = f.readline().strip()
print('Case #%d: %s' % (i+1, solve(line)))
@yiakwy
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

int
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;
}

@yiakwy
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.

@suresh187
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