Questions based on the session on Dynamic Programming by Apaar Kamal

CodingMinutesDP.py

# -*- coding: utf-8 -*-
"""
Questions based on the session on Dynamic Programming by Apaar Kamal.
https://join.codingminutes.com/dp-08


Alice and Bob are playing a game. Alice plays first.
We have a pile of n stones.

Q1.
Moves are either pick 2,3,4 and 5 stones from the pile.
Player unable to make a move looses. If n = 15, who wins the game?

Q2.
Moves are either pick 2,10,50 and 100 stones from the pile.
Player unable to make a move looses. If n = 232132, who wins the game?
"""
from functools import lru_cache
from typing import List


def isAliceWinnerRecursion(choices: List[int], n: int) -> bool:
    '''
    Recursive solution using lru_cache for memoization.
    Exceeds recursion depth for n > 1000.

    Parameters
    ----------
    choices : List[int]
        All possible number of stones that can be picked from the pile.
    n : int
        Initial number of stones in the pile.

    Returns
    -------
    bool
        If Alex ie Player 1 wins.
    '''
    @lru_cache(maxsize=None)
    def dfs(n_stones):
        if n_stones == 0:
            return False  # Losing condition

        for pick in choices:
            if pick <= n_stones:  # If stones can be picked
                if not dfs(n_stones - pick):  # Explore solution
                    return True  # If next leads to loss, current move is win
        return False  # No choice wins to win, so move is loss

    return dfs(n)


def isAliceWinnerDP(choices: List[int], n: int) -> bool:
    '''
    Similar logic to recursive solution, but maintains a DP array to store
    results. Better performance for larger n values.
    '''
    dp = [False] * (n+1)  # 1-D DP array for answers, lose by default
    for i in range(1, n+1):
        for pick in choices:
            if pick <= i:  # If stones can be picked
                if not dp[i - pick]:
                    dp[i] = True  # Pick is winner
                    break         # No need to explore rest
    return dp[n]  # Answer for n


def main():
    # Question 1
    moves = [2, 3, 4, 5]
    n = 15
    if isAliceWinnerRecursion(moves, n):
        print("Alice Wins")
    else:
        print("Bob wins")

    # Question 2
    moves = [2, 10, 50, 100]
    n = 232132
    if isAliceWinnerDP(moves, n):
        print("Alice Wins")
    else:
        print("Bob wins")


if __name__ == '__main__':
    main()