Skip to content

Instantly share code, notes, and snippets.

# greenkey/gcj-2017-A.py Created Apr 10, 2017

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()] pan_size = int(line.split()) 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 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)))

### keobox commented Apr 11, 2017

 Genius!

### 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 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 commented May 15, 2018

 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?
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.