Score of Mystical Market Chains - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

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

• Q: What is the input to the problem?
  • A: The input is a balanced string chain representing a sequence of magical item symbols.
• Q: What is the output?
  • A: The output is an integer representing the total power score of the magical item chain.
• Q: What are the rules for calculating the score?
  • A:
    • The symbol "()" represents a basic magical item with a power score of 1.
    • A chain AB, where A and B are balanced chains, has a total power score of A + B.
    • A chain (A), where A is a balanced chain, has a power score of 2 * A.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to keep track of the scores as you parse through the string. For every opening bracket, push a 0 onto the stack. For every closing bracket, pop the top value, calculate the score for the balanced substring, and update the stack.

1. Initialize a stack with a single element `0` to handle score calculation.
2. Iterate over each character in the string `chain`:
   1. If the character is an opening bracket `'('`, push `0` onto the stack.
   2. If the character is a closing bracket `')'`:
       - Pop the top value from the stack.
       - Calculate the score for the balanced substring:
           - If the popped value is `0`, add `1` to the top value of the stack.
           - Otherwise, double the popped value and add it to the top value of the stack.
3. The final result will be the only value left in the stack after processing the entire string.
4. Return the value from the stack as the total score.

⚠️ Common Mistakes

• Not correctly handling nested structures which should be multiplied rather than added.
• Forgetting to update the stack correctly after processing each closing bracket.

I-mplement

def score_of_mystical_market_chains(chain):
    stack = [0]  # Initialize the stack with a 0 to handle the score calculation

    for char in chain:
        if char == '(':
            stack.append(0)  # Push a 0 onto the stack to represent a new balanced substring
        else:
            v = stack.pop()  # Pop the top element of the stack
            stack[-1] += max(2 * v, 1)  # Update the top element of the stack with the calculated score

    return stack.pop()  # The final result is the only element left in the stack

# Example usage
print(score_of_mystical_market_chains("()"))  # Output: 1
print(score_of_mystical_market_chains("(())"))  # Output: 2
print(score_of_mystical_market_chains("()()"))  # Output: 2