কনটেন্টে যান

002 — Baseball Game

Problem link ও উৎস

  • 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-কে দেখে কাজ করে

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

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

Input ও 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 করলে হবে না।

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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।

কোথায় বেশি কাজ হচ্ছে

এই 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)। আসল শিক্ষা: সবসময় সস্তা (শেষ) প্রান্তেই কাজ করো।

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

["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

ছোট input-এ ধাপে ধাপে

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

  1. "5" → push 5 → [5]
  2. "-2" → push -2 → [5, -2]
  3. "4" → push 4 → [5, -2, 4]
  4. "C" → pop 4 → [5, -2]
  5. "D" → push 2*(-2) = -4 → [5, -2, -4]
  6. "9" → push 9 → [5, -2, -4, 9]
  7. "+" → push 9 + (-4) = 5 → [5, -2, -4, 9, 5]
  8. "+" → push 5 + 9 = 14 → [5, -2, -4, 9, 5, 14]
  9. sum = 5 + (-2) + (-4) + 9 + 5 + 14 = 27 → return 27

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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-এর যোগফল।

Output মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

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