{{ message }}

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?