{{ 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #! /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)))

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?