Match

Match.py

'''
Pass
Reborn
Self-kill
'''

from math import ceil

def expand(n):
    a = n/1000
    n %= 1000
    b = n/100
    n %= 100
    c = n/10
    n %= 10
    d = n
    return a,b,c,d

def compose(x, y):
    a,b = x[0]%5, x[1]%5
    if a < b:
        x = a*10+b
    else:
        x = b*10+a

    a,b = y[0]%5, y[1]%5
    if a < b:
        y = a*10+b
    else:
        y = b*10+a

    return x*100+y


bdp = {}
wdp = {}

bmemo = {}
wmemo = {}

def fblack(n, wbt, bbt):
    global count
    print '%03d'%count,
    if n not in bmemo: bmemo[n] = count
    count += 1

    print ' '*(len(wbt)+len(bbt)), '%04d'%n, 'Black',

    if n in bdp:
        print '=>', bmemo[n], 'BLACK WIN' if bdp[n] == 1 else 'WHITE WIN'
        return bdp[n]

    m = expand(n)
    black = m[:2]
    white = m[2:]

    if black == (0,0):
        print '=> WHITE WIN'
        return -1

    print

    c = set()

    # Attack
    for i in 0,1:
        for j in 0,1:
            if black[i] == 0 or white[j] == 0:
                continue
            x = black
            y = black[i]+white[j], white[~j+2]
            c.add(compose(x,y))

    # Alteranative
    s = sum(black)
    for i in range(int(ceil(s/2.0))):
        if s-i > 5:  # Accepts 5. This means self-killing.
            continue
        if s == 5 and i == 0:
            continue
        x = i, s-i
        y = white
        c.add(compose(x,y))

    # Pass but excludes those: (2,2) -> (2,2), (3,3) -> (3,3) ...
    if black[0] != black[1]:
        c.add(n)

    # Search
    results = []
    for k in c:
        if k in bbt:
            #print 'DRAW'
            #results += [0]
            pass
        else:
            results += [fwhite(k, wbt|set([n]), bbt)]

    bdp[n] = max(results) if results else -1
    return bdp[n]


def fwhite(n, wbt, bbt):
    global count
    print '%03d'%count,
    if n not in wmemo: wmemo[n] = count
    count += 1

    print ' '*(len(wbt)+len(bbt)), '%04d'%n, 'White',

    if n in wdp:
        print '=>', wmemo[n], 'BLACK WIN' if wdp[n] == 1 else 'WHITE WIN'
        return wdp[n]

    m = expand(n)
    black = m[:2]
    white = m[2:]

    if white == (0,0):
        print '=> BLACK WIN'
        return 1

    print

    c = set()

    # Attack
    for i in 0,1:
        for j in 0,1:
            if black[i] == 0 or white[j] == 0:
                continue
            x = black[i]+white[j], black[~i+2]
            y = white
            c.add(compose(x,y))

    # Alteranative
    s = sum(white)
    for i in range(int(ceil(s/2.0))):
        if s-i > 5:  # Accepts 5. This means self-killing.
            continue
        x = black
        y = i, s-i
        c.add(compose(x,y))

    # Pass but excludes those: (2,2) -> (2,2), (3,3) -> (3,3) ...
    if white[0] != white[1]:
        c.add(n)

    # Search
    results = []
    for k in c:
        if k in wbt:
            #print 'DRAW'
            #results += [0]
            pass
        else:
            results += [fblack(k, wbt, bbt|set([n]))]

    wdp[n] = min(results) if results else 1
    return wdp[n]
                     
count = 0
print fblack(compose((1,1),(1,1)), set(), set())