stone game from 名侦探学院 2023-03-01 (aka nim)

nim.py

# get all possible next states
def get_next_state(tuple_state):
    ret = []
    # for all index of tuple_state, subtract any number of stones 1 through maximum possible
    for i in range(len(tuple_state)):
        for j in range(1, tuple_state[i]+1):
            # create new state
            new_state = list(tuple_state)
            new_state[i] -= j
            # sort new state
            new_state.sort()
            # remove 0s
            while new_state[0] == 0:
                new_state.pop(0)
                if new_state == []:
                    break
            # convert new state to tuple
            new_state = tuple(new_state)
            ret.append(new_state)
    # remove duplicates
    ret = list(set(ret))
    return ret

cache = {}
book = {}

def get_xian_hou(state):
    if state in cache:
        return cache[state]
    if state == ():
        cache[state] = 'hou'
        return 'hou'
    else:
        nxt_states = get_next_state(state)
        for nxt_state in nxt_states:
            if get_xian_hou(nxt_state) == 'hou':
                cache[state] = 'xian'
                book[state] = nxt_state
                return 'xian'
        cache[state] = 'hou'
        return 'hou'
    
if __name__ == '__main__':
    state = (3,)
    nxt_states = get_next_state(state)
    print (nxt_states)
    print (get_xian_hou((2,5,6,9)))

    # print value of cache whos value is 'hou'
    for key in cache:
        if cache[key] == 'hou':
            print (key)

    print (book[(2,5,6)])