subtract_a_square_lengths.py

from typing import List
import math

def game_lengths(n: int) -> List[int]:
    """Optimal game lengths for subtract-a-square for starting positions <=n
    Parameters
    ----------
    n:
        The maximum starting position to return
    Returns
    -------
    A list of game lengths in subtract-a-square where the winner wants to make
    the game as short as possible and the loser wants to make it as long as
    possible. The value at index 0 corresponds to starting a game with 0, meaning
    the first player loses automatically. In general, the ith number in the
    returned list will be the length of a game where the first player starts
    with the number i.
    """
    assert n >= 0, "n must be less than or equal to 0, got {}".format(n)
    known_lengths = [0]
    for i in range(1, n + 1):
        # get perfect squares less than or equal to i
        subtractable_squares = [j * j for j in range(1, int(math.sqrt(i)) + 1)]
        best_case_win = None
        best_case_loss = None
        starting_point = i
        for square in subtractable_squares:
            possible_move = starting_point - square
            possible_game_length = known_lengths[possible_move] + 1
            if possible_game_length % 2 == 0:
                # if the game will end in an even number of
                # turns from our current starting point, that
                # means it will be our turn when the game ends
                # at 0. Thus we will lose and want to make it
                # take as long as possible.
                best_case_loss = (
                    max(best_case_loss, possible_game_length)
                    if best_case_loss
                    else possible_game_length
                )
            else:
                # if the game will end in an odd number of
                # turns from our current starting point, that
                # means it will be our opponent's turn when the
                # game ends at 0. Thus we will win and want to
                # make it as short as possible.
                best_case_win = (
                    min(best_case_win, possible_game_length)
                    if best_case_win
                    else possible_game_length
                )

        if best_case_win is not None:
            known_lengths.append(best_case_win)
        else:
            known_lengths.append(best_case_loss)
    return known_lengths

print(game_lengths(100000))

An inefficient, but more direct, recursive implementation:

from functools import lru_cache

@lru_cache
def a(n):
    import math
    def S(m):
        return [j * j for j in range(1, int(math.sqrt(m)) + 1)]
    if n == 0:
        return 0
    possible_moves = [n - s for s in S(n)]
    if any(a(n - s) % 2 == 0 for s in S(n)):
        return min(a(n - s) for s in S(n) if a(n - s) % 2 == 0) + 1
    else:
        return max(a(n - s) for s in S(n)) + 1

print([a(i) for i in range(20)])