# -*- encoding: utf-8 -*-
"""
retrograde analysisの習作
hexa pawn

state sample:
vvv
...
^^^
"""

def encode(state):
    "@return integer"
    result = 0
    pow = 1
    for c in state:
        if c == "v":
            result += pow * 2
        elif c == "^":
            result += pow
        pow *= 3
    return result

def decode(n):
    "@return state"
    result = []
    pow = 1
    for i in range(9):
        v = n % 3
        result.append(".^v"[v])
        n /= 3

    return "".join(result)

def _split_to_lines(state):
    return [
        state[:3],
        state[3:6],
        state[6:]]
        
def pretty_print(state, indent=0):
    """
    >>> encode("vvv...^^^")
    9503
    >>> pretty_print(decode(9503))
    -----
    vvv
    ...
    ^^^

    >>> encode("vvv.^.^.^")
    7397
    >>> pretty_print(decode(7397))
    -----
    vvv
    .^.
    ^.^

    """
    print("-" * 5)
    for line in _split_to_lines(state):
        print(" " * indent + line)


def flip_horizontal(state):
    """
    >>> pretty_print(flip_horizontal("123456789"))
    -----
    321
    654
    987
    """
    return "".join(
        "".join(reversed(line))
        for line in _split_to_lines(state))


def flip_vertical(state):
    """
    >>> pretty_print(flip_vertical("123456789"))
    -----
    789
    456
    123
    """
    return "".join(reversed(_split_to_lines(state)))


def flip_player(state):
    """
    >>> pretty_print(flip_vertical("vvv...^^^"))
    -----
    ^^^
    ...
    vvv
    """
    return "".join(
        ".^v"[".v^".index(c)] for c in state)


def _modify(state, mods):
    result = list(state)
    for (i, v) in mods:
        result[i] = v
    return "".join(result)


def get_parents(state):
    """stateに変化しうる直前の盤面のリストを返す
    >>> state = "........v"
    >>> pretty_print(state)
    -----
    ...
    ...
    ..v

    >>> for s in get_parents(state): 
    ...     pretty_print(s)
    -----
    ...
    ..^
    ...
    -----
    ..v
    .^.
    ...

    >>> pretty_print("...^v..v.")
    -----
    ...
    ^v.
    .v.
    >>> for s in get_parents("...^v..v."): 
    ...     pretty_print(s)
    -----
    .v.
    v^^
    ...
    -----
    .^.
    v..
    .^.
    -----
    .^.
    vv.
    ..^
    -----
    .^.
    vv.
    ^..
    """
    result = []
    # まず相手の手番ということで上下とプレイヤーをflipする
    state = flip_vertical(flip_player(state))
    # すべての自分の駒(^)について:
    #     前が空いていたので直進した
    #     斜め前に駒があったので取った
    # のどちらか
    # 初期状態から到達不能なのが生成されることもあるけど
    # 効率的でない以外の実害はない

    for i in range(6):
        if state[i] == "^":
            if state[i + 3] == ".":
                # 自分の駒の手前が空いているなら移動してきたかもしれない
                result.append(
                    _modify(state, [(i, "."), (i + 3, "^")]))
            if i % 3 in [0, 1] and state[i + 4] == ".":
                # 自分の駒の右下が空いているなら取って進んだかもしれない
                result.append(
                    _modify(state, [(i, "v"), (i + 4, "^")]))
            if i % 3 in [1, 2] and state[i + 2] == ".":
                # 自分の駒の左下が空いているなら取って進んだかもしれない
                result.append(
                    _modify(state, [(i, "v"), (i + 2, "^")]))
    
    return result

def get_children(state):
    """stateから変化しうる局面のリストを返す
    >>> state = ".....v.^."
    >>> pretty_print(state)
    -----
    ...
    ..v
    .^.

    >>> for s in get_parents(state): 
    ...     pretty_print(s)
    -----
    .v.
    ...
    ..^
    -----
    .v.
    ..v
    .^.
    """


    result = []
    for i in range(3, 9):
        if state[i] == "^":
            if state[i - 3] == ".":
                # 自分の駒の手前が空いているなら移動できる
                result.append(
                    _modify(state, [(i, "."), (i - 3, "^")]))
            if i % 3 in [0, 1] and state[i - 2] == "v":
                # 自分の駒の右上に敵駒があればとって進める
                result.append(
                    _modify(state, [(i, "."), (i - 2, "^")]))
            if i % 3 in [1, 2] and state[i - 4] == "v":
                # 自分の駒の左上に敵駒があればとって進める
                result.append(
                    _modify(state, [(i, "."), (i - 4, "^")]))

    # 相手の手番にうつるので上下とプレイヤーをflipする
    return [flip_vertical(flip_player(state)) for state in result]

def retrograde():
    # まず状態数分のサイズのリストを作る。
    # より大きな問題のときはいかに削減してオンメモリで持てるようにするか工夫が必要だけど
    # 今回は問題が十分小さいので深く考えない。3 ** 9という無駄だらけの置き方でも2万弱。
    flags = [0] * (3 ** 9) # 0: 未解決, 1: 勝ち, 2: 負け, 3: 引き分け

    # 「終わっている」盤面を探して終わってるフラグを立てる
    for i in range(3 ** 9):
        state = decode(i)
        if "v" in state[6:]:
            # 一番下まで敵の駒に侵入されたので負け
            flags[i] = 2

    # debug print 2だらけだ、0の所の方が少ない
    # print "".join(str(x) for x in flags)

    to_loop = True
    while to_loop:
        to_loop = False
        # すべての状態について、それが負け状態なら親は勝ち状態
        for i in range(3 ** 9):
            if flags[i] == 2:
                for p in get_parents(decode(i)):
                    pi = encode(p)
                    if flags[pi] == 0:
                        flags[pi] = 1
                        to_loop = True

        # すべての状態について、親の子が全部勝ち状態なら親は負け状態
        for i in range(3 ** 9):
            if flags[i] == 1:
                for p in get_parents(decode(i)):
                    pi = encode(p)
                    if flags[pi] == 0:
                        if all(flags[encode(c)] == 1 
                               for c in get_children(p)):
                            flags[pi] = 2
                            to_loop = True
        print "loop"

    file("result.py", "w").write("flags = %s" % flags)

    print flags[encode("vvv...^^^")]
    # -> 0 引き分け？
    for c in get_children("vvv...^^^"):
        pretty_print(c)
        print flags[encode(c)]
    # -> 0 引き分け？

def see_result():
    import result
    def get_msg(state):
        MSG = "DRAW WIN LOSE".split()
        return MSG[result.flags[encode(state)]]

    for c in get_children("vvv...^^^"):
        pretty_print(c)
        print(get_msg(c))
        for c2 in get_children(c):
            pretty_print(c2, 2)
            print("  " + get_msg(c2))
#            for c3 in get_children(c2):
#                pretty_print(c3, 2)
#                print("  " + get_msg(c3))
            

def _test():
    import doctest
    doctest.testmod()
    print "ok."

if __name__ == "__main__":
    _test()
    #retrograde()
    see_result()