Instantly share code, notes, and snippets.

Embed
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
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)))
@keobox

This comment has been minimized.

Show comment
Hide comment
@keobox

keobox commented Apr 11, 2017

Genius!

@yiakwy

This comment has been minimized.

Show comment
Hide comment
@yiakwy

yiakwy 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

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

This comment has been minimized.

Show comment
Hide comment
@yiakwy

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

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

This comment has been minimized.

Show comment
Hide comment
@suresh187

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

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?

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