002 — Baseball Game¶

Source¶

Original source: Classic stack-simulation exercise
Platform: LeetCode — https://leetcode.com/problems/baseball-game/
Topic: stack
Difficulty: Easy
Pattern: stack simulation
Basic idea inherited from: push/pop as undo — প্রতিটা operation stack-এর top-কে দেখে কাজ করে

1. Problem in simple words¶

তোমাকে কতগুলো operation-এর একটা list দেওয়া আছে (সবগুলো string আকারে)। তুমি একটা score record রাখবে আর প্রতিটা operation এক এক করে চালাবে:

একটা সংখ্যা x — নতুন একটা score হিসেবে x যোগ করো।
"+" — শেষ দুটো score-এর যোগফল নতুন একটা score হিসেবে যোগ করো।
"D" — শেষ score-এর দ্বিগুণ নতুন একটা score হিসেবে যোগ করো।
"C" — শেষ score-টা বাতিল করে দাও (record থেকে মুছে ফেলো)।

সব operation শেষে record-এ থাকা সব score-এর যোগফল return করো।

2. Which basic idea does this inherit from?¶

এটা push/pop-কে undo হিসেবে ব্যবহার করার সরাসরি প্রয়োগ। "C" মানে আক্ষরিক অর্থে "শেষ কাজটা undo করো" → একটা pop। x, "+", "D" — সবই নতুন কিছু push করে, আর তারা সবসময় সবচেয়ে recent এক-দুটো score-এর উপর নির্ভর করে, যেগুলো stack-এর top-এ বসে আছে।

3. What is the hidden math or logic?¶

লুকানো logic হলো temporal locality: প্রতিটা operation শুধু সবচেয়ে recent এক বা দুটো score-কে ছোঁয়, তার আগের history-কে নয়। তাই একটা LIFO structure যথেষ্ট — যা দরকার তা সবসময় উপরে থাকে। final answer হলো record-এ টিকে থাকা সব valid score-এর simple যোগফল।

4. Which data structure is needed?¶

একটা stack (Python list)। আমরা শেষ প্রান্তেই push (append), pop, আর peek ([-1], [-2]) করি — ঠিক stack-এর সস্তা প্রান্ত।

5. Why this data structure fits¶

প্রতিটা operation-এর জন্য যে তথ্য দরকার তা হলো সবচেয়ে recent score গুলো — মানে stack-এর top। "C" চায় শেষ-যোগ-করা score মুছতে → pop, O(1)। "D" চায় শেষ score → [-1], O(1)। "+" চায় শেষ দুটো → [-1] আর [-2], O(1)। কোনো মাঝখানে খোঁজাখুঁজি নেই, তাই stack নিখুঁতভাবে খাপ খায়।

6. Real-life analogy¶

একটা পেন্সিল দিয়ে কাগজে score লেখা ভাবো, একটার নিচে একটা। নতুন score এলে নিচে আরেকটা লাইন লেখো। কেউ ভুল হয়েছে বললে ("C") — শেষ লাইনটা মুছে দাও। কোনো লাইন যোগ করতে আগের লাইন(গুলো) দেখা লাগলে, তুমি সবসময় সবচেয়ে নিচের, মানে সবচেয়ে নতুন লাইনটাই দেখো। এই "নিচ থেকে যোগ করা আর নিচ থেকে মোছা"-ই stack।

7. Visual explanation¶

["5", "2", "C", "D", "+"] চালাই, stack বদলাতে দেখি:

op    action                                  stack (top ডানে)
"5"   integer -> push 5                       [5]
"2"   integer -> push 2                       [5, 2]
"C"   cancel  -> pop শেষ (2)                  [5]
"D"   double  -> push 2*top = 2*5 = 10        [5, 10]
"+"   sum     -> push top + প্রাক্-top = 15   [5, 10, 15]
end   sum = 5 + 10 + 15                        = 30

8. Example input and output¶

Input : ["5", "2", "C", "D", "+"]                       -> Output: 30
Input : ["5", "-2", "4", "C", "D", "9", "+", "+"]       -> Output: 27

Edge case (সব বাতিল): ["1", "C"]   -> Output: 0   (record খালি -> যোগফল 0)

দ্বিতীয় example-এ negative সংখ্যাও আছে ("-2"), তাই int() parse করা জরুরি — শুধু digit check করলে হবে না।

9. Brute force thinking¶

stack ছাড়া করতে গেলে একটা সাধারণ list রাখতাম, আর প্রতিটা operation-এ index hisaব করে শেষ element খুঁজতে হতো:

record = []
"+" হলে: last = len(record)-1; record.append(record[last] + record[last-1])
"C" হলে: record-এর শেষ element del করো (del record[-1])

আসলে এটাও কাজ করে — কারণ Python list-এর শেষ প্রান্ত নিজেই একটা stack।

10. Why brute force is slow¶

এই problem-এ আসল "brute force vs optimal" tension নেই — naive approach আর optimal approach একই, কারণ list-এর শেষ প্রান্ত (append/pop) এমনিতেই O(1)। ভুল approach হতো record-এর সামনে insert/delete করা (insert(0, ...) / pop(0)), যা প্রতিবার O(n) shift ঘটায় → পুরোটা O(n^2)। আসল শিক্ষা: সবসময় সস্তা (শেষ) প্রান্তেই কাজ করো।

11. Key observation¶

মূল observation: প্রতিটা operation শুধু record-এর শেষ এক-দুটো entry-কে ছোঁয়। কখনো গভীরে যেতে হয় না। তাই "শেষ প্রান্ত" cheap রাখলেই পুরো simulation cheap — মানে stack যথেষ্ট।

12. Optimized intuition¶

একটা stack নাও। operation list-এ একবার হাঁটো। "+" হলে top দুটোর যোগফল push করো; "D" হলে top-এর দ্বিগুণ push করো; "C" হলে top pop করো; নাহলে সংখ্যাটাকে int করে push করো। শেষে stack-এর সব element-এর sum return করো।

13. Thinking tweak¶

মোচড়: problem-টা একগাদা নিয়মের জটিল হিসাব মনে হলেও, প্রতিটা নিয়মই আসলে "top দেখো, একটা নতুন value push করো বা top pop করো"। জটিলতাটা চারটে ছোট, top-নির্ভর operation-এ ভেঙে যায়।

14. Step-by-step dry run¶

Input ["5", "-2", "4", "C", "D", "9", "+", "+"]:

"5" → push 5 → [5]
"-2" → push -2 → [5, -2]
"4" → push 4 → [5, -2, 4]
"C" → pop 4 → [5, -2]
"D" → push 2*(-2) = -4 → [5, -2, -4]
"9" → push 9 → [5, -2, -4, 9]
"+" → push 9 + (-4) = 5 → [5, -2, -4, 9, 5]
"+" → push 5 + 9 = 14 → [5, -2, -4, 9, 5, 14]
sum = 5 + (-2) + (-4) + 9 + 5 + 14 = 27 → return 27

15. Python solution¶

def cal_points(operations):
    stack = []
    for op in operations:
        if op == "+":
            stack.append(stack[-1] + stack[-2])   # শেষ দুটোর যোগ
        elif op == "D":
            stack.append(2 * stack[-1])           # শেষটার দ্বিগুণ
        elif op == "C":
            stack.pop()                            # শেষটা বাতিল
        else:
            stack.append(int(op))                  # সংখ্যা (negative-ও) push
    return sum(stack)

# ---- tests ----
assert cal_points(["5", "2", "C", "D", "+"]) == 30
assert cal_points(["5", "-2", "4", "C", "D", "9", "+", "+"]) == 27
assert cal_points(["1", "C"]) == 0          # সব বাতিল -> খালি record
assert cal_points(["1", "2", "3"]) == 6     # শুধু সংখ্যা
print("সব test pass!")

16. Line-by-line code explanation¶

stack = [] — valid score গুলো এখানে জমবে।
if op == "+": — শেষ দুটো score (stack[-1], stack[-2]) যোগ করে নতুন একটা push।
elif op == "D": — শেষ score-এর 2 * গুণ push।
elif op == "C": — শেষ score pop করে বাতিল।
else: stack.append(int(op)) — string-টা সংখ্যা; int() দিয়ে parse করে push (negative হ্যান্ডল হয়)।
return sum(stack) — record-এ টিকে থাকা সব score-এর যোগফল।

17. Output walkthrough¶

cal_points(["5", "2", "C", "D", "+"]) → section 7-এর মতো stack হয় [5, 10, 15], sum = 30। cal_points(["1", "C"]) → 1 push, তারপর pop → stack খালি → sum([]) = 0। সব assert pass হয়ে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — n-টা operation, প্রতিটা O(1) (push/pop/peek)। শেষের sum আরও O(n), মোট তাও O(n)।

19. Space complexity¶

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (সব operation সংখ্যা) stack-এ n-টা score জমতে পারে।

20. Common mistakes¶

negative সংখ্যা ভুলে যাওয়া — শুধু op.isdigit() দিয়ে check করলে "-2" ধরা পড়ে না; int() দিয়ে parse করা নিরাপদ।
"+"-এ ভুল দুটো element নেওয়া (যেমন stack[0] আর stack[1]); সবসময় শেষ দুটো ([-1], [-2])।
record-এর সামনে insert/delete করা (pop(0)) — অকারণে O(n) করে দেয়; শেষ প্রান্তেই কাজ করো।

21. Which basic problem this inherits from¶

ভিত্তি: stack-এর push/pop-as-undo discipline, যা problem 1 (Valid Parentheses)-এও দেখা — সেখানে "C"-এর মতো "শেষ খোলাটা বন্ধ করা" ছিল। chapter-এর ../patterns.md-এর Pattern 1 (Matching / Nesting / Undo) এর ছাতার নিচে।

22. Similar harder problems¶

Evaluate Reverse Polish Notation (postfix expression) — https://leetcode.com/problems/evaluate-reverse-polish-notation/ (এই tracker-এর #8)
Asteroid Collision (stack simulation) — https://leetcode.com/problems/asteroid-collision/ (#11)
Simplify Path (path-এ ".." কে undo হিসেবে) — https://leetcode.com/problems/simplify-path/ (#18)

23. Pattern learned¶

Stack simulation: যখন প্রতিটা step শুধু সবচেয়ে recent এক-দুটো result-এর উপর কাজ করে (যোগ করে বা undo করে), একটা stack নিয়ে operation গুলো আক্ষরিকভাবে চালিয়ে দাও।

24. Final summary¶

ভবিষ্যতের আমাকে: "প্রতিটা rule শুধু top দেখে — তাই stack।" "undo / cancel / শেষটা মুছো" মানেই pop; "আগেরগুলোর উপর ভিত্তি করে নতুন value" মানেই peek + push। শেষ প্রান্তেই সব কাজ রাখবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।