0817 upside down cake problem

def cakeflip(x):
    # invert and reverse 
    x = np.array(x)
    if x[0]+x[1] != 1: # [1,0], [0,1] are isomorphic
        tmp = (x[1]+1)%2
        x[1] = (x[0]+1)%2
        x[0] = tmp
    return np.append(x[2:],x[0:2])

import numpy as np
for a in range(2,4):
    print '-'*40
    arr = np.zeros(a+a-1, dtype=np.uint8)
    #first filp
    arr[-2:] = 1
    cnt=1
    while np.any(arr):
        print cnt, "\t", arr
        arr = cakeflip(arr)
        cnt += 1
    print cnt, "\t", arr
    assert ((a*2-1)**2 - 1 )/2 == cnt
    # cnt = 2*n*(n-1) = (len(arr)^2 - 1) / 2
    # https://oeis.org/A046092
    # why? can you prove?
    
def simple_cakeflip(arr):
    return (len(arr)**2 - 1 )/2

def cakeflip2(x, idx=0):
    lx = len(x)
    assert lx>1
    idx0 = idx % lx
    idx1 = (idx+1) % lx
    if x[idx0] + x[idx1] == 1: #[0,1] or [1,0] are stable.
        return x 
    x0 = (x[idx1]+1)%2
    x[idx1] = (x[idx0]+1)%2
    x[idx0] = x0
    return x

for a in range(2,4):
    print '-'*40
    arr = np.zeros(a+a-1, dtype=np.uint8)
    idx = 0
    cnt = 0
    while cnt < 1 or np.any(arr):
        print cnt,"\t",arr
        arr = cakeflip2(arr, idx)
        idx += 2
        cnt += 1
    print cnt,"\t",arr
    assert cnt == simple_cakeflip(arr)