game 20-21 ege

memory = {}
'''
возвращает 1, если игра выигрышная, 0 если проигрышная
вторым вернется число ходов
a камней в первой куче, b во второй
'''
def game(a, b):
    '''
    вдруг игра закончилась

    if a + 1 + b >= 49:
        return 1
    if a + b + 1 >= 49:
        return 1
    if a * 3 + b >= 49:
        return 1
    if a + b * 3 >= 49:
        return 1
    '''
    if a + b >= 49:
        return (0, 0)

    '''
        Без мемоизации работает бесконечно долго ^_^
    '''
    global memory
    if (a, b) in memory:
        return memory[(a, b)]

    '''
    переходим во всевозможные ситуации
    '''
    has_loose = 0
    min_loose = 100000
    max_win = 0

    moves = [
        (a + 1, b),
        (a * 3, b),
        (a, b + 1),
        (a, b * 3)
    ]
    for new_a, new_b in moves:
        if game(new_a, new_b)[0] == 0:
            has_loose = 1
            min_loose = min(min_loose, game(new_a, new_b)[1] + 1)
        else:
            max_win = max(max_win, game(new_a, new_b)[1] + 1)
    '''
    был ли выигрышный переход
    '''
    if has_loose:
        memory[(a, b)] = (1, min_loose)
        return (1, min_loose)
    memory[(a, b)] = (0, max_win)
    return (0, max_win)

for start in range(1, 44):
    print(start, game(5, start), sep = '\t')