Aang and Zuko’s Elemental Duel - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Unit 12 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Dynamic Programming, Game Theory

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to determine if Aang wins the duel, assuming both players play optimally.
  • What is the base case?
    • If n = 0, the player cannot make a move and loses the game.
  • Can the players choose any x?
    • The players must choose x such that 0 < x < n and n % x == 0.
HAPPY CASE
Input: 
    n = 2
Output: 
    True
Explanation:
    Aang reduces the strength by 1, and Zuko has no more moves.

EDGE CASE
Input: 
    n = 3
Output: 
    False
Explanation:
    Aang reduces the strength by 1, and then Zuko does the same, leaving Aang with no moves.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For game theory problems, we want to consider the following approaches:

  • Dynamic Programming (DP): We can use DP to store the results of subproblems, where each state of the game (each value of n) represents whether the current player (Aang) wins or loses.
  • Game Theory: This is a game where both players play optimally, so at each step, Aang will try to force Zuko into a losing state.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to solve this problem. We will create a DP array where dp[i] is True if Aang wins when the battlefield strength is i, and False otherwise. Aang wins if there is a move x such that after reducing the battlefield strength by x, Zuko is left in a losing position.

Steps:

  1. Base Case:

    • If n = 0, Aang cannot make a move, so he loses the game (dp[0] = False).

  2. DP Array:

    • Create a DP array dp of size n + 1, initialized with False.
    • For each i from 1 to n, check all possible moves x such that 0 < x < i and i % x == 0.

  3. Recurrence Relation:

    • If there exists a move x such that after reducing i by x (i.e., i - x), Zuko is left in a losing state (dp[i - x] == False), then Aang wins at i.

  4. Return the Result:

    • The value at dp[n] will give whether Aang wins the duel or not.

4: I-mplement

Implement the code to solve the algorithm.

def aang_wins(n):
    # Initialize a DP array with False values
    dp = [False] * (n + 1)
    
    # Base case: if n = 0, Aang cannot make a move, so he loses
    dp[0] = False
    
    # Fill the DP array
    for i in range(1, n + 1):
        # Try all possible moves where 0 < x < i and i % x == 0
        for x in range(1, i):
            if i % x == 0:
                if not dp[i - x]:  # If the resulting state is a loss for Zuko, Aang wins
                    dp[i] = True
                    break
    
    return dp[n]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: n = 2
  • Expected Output: True

Example 2:

  • Input: n = 3
  • Expected Output: False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the input value representing the battlefield strength.

  • Time Complexity: O(n^2) because for each i from 1 to n, we check all possible divisors x such that 0 < x < i.
  • Space Complexity: O(n) to store the DP array.