Baseball Game

EASY✓ CHIP-TIMEDLC #682 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Replay a baseball scoring log where a plain number adds a new score, "+" sums the previous two, "D" doubles the last one, and "C" erases the most recent entry — total whatever remains once the log ends.

A log of baseball scoring operations arrives as a list of string tokens. A token holding a plain number records a new score on the board; the other three tokens react to what's already there.

A '+' token sums the two most recently recorded scores and records that sum as a new entry. A 'D' token doubles the single most recent score and records the result. A 'C' token undoes the most recent recording entirely, removing it from the board.

Once every token has been processed, the drill totals whatever scores remain on the board and hands back that sum. The log always contains enough prior scores for every '+', 'D', or 'C' it uses.

log holds anywhere from one to a few thousand tokens
numeric tokens can be negative, zero, or positive
'+' and 'D' always have enough prior scores to act on
final answer is the sum of whatever scores remain

EX 01

operations = ["5", "2", "C", "D", "+"]

→ 30

cancel then double then sum

EX 02

operations = ["10", "-5", "+", "C", "D"]

→ -5

negative completes a sum

EX 03

operations = ["1"]

→ 1

minimum size, no operators

The hintstake only what you need

HINT 1 THE NUDGE

Each entry in the log either adds a new score or reaches back into scores already on the board — the structure you pick needs to remember recent history, not just a running total.

HINT 2 THE STRUCTURE

A stack is exactly “recent history”: push new scores, and for “+” or “D” peek at the top one or two entries; “C” just pops.

HINT 3 ONE STEP FROM THE ANSWER

Walk the operations once, pushing parsed integers and using peek/pop for “+”, “D”, and “C”, then sum whatever is left on the stack at the end.

Coach's boardthe pattern, step by step

THE SCOREBOARD STACKPATTERN · EXPLICIT STACKoperations = ["5", "2", "C", "D", "+"]

SCORE STACK

— empty —

STEP 1

Replay the log left to right; the stack always holds the board's current scores.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/baseball-game.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        stack = []
        for op in operations:
            if op == "C":
                stack.pop()
            elif op == "D":
                stack.append(2 * stack[-1])
            elif op == "+":
                stack.append(stack[-1] + stack[-2])
            else:
                stack.append(int(op))
        return sum(stack)

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 13 LN

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        record = []  # entries stay in place; "C" just marks a slot dead
        for op in operations:
            if op == "C":
                for i in range(len(record) - 1, -1, -1):
                    if record[i] is not None:
                        record[i] = None
                        break
            elif op == "D":
                for i in range(len(record) - 1, -1, -1):
                    if record[i] is not None:
                        record.append(2 * record[i])
                        break
            elif op == "+":
                vals = []
                for i in range(len(record) - 1, -1, -1):
                    if record[i] is not None:
                        vals.append(record[i])
                        if len(vals) == 2:
                            break
                record.append(vals[0] + vals[1])
            else:
                record.append(int(op))
        return sum(v for v in record if v is not None)

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 25 LN

class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String op : operations) {
            switch (op) {
                case "C":
                    stack.pop();
                    break;
                case "D":
                    stack.push(2 * stack.peek());
                    break;
                case "+": {
                    Iterator<Integer> it = stack.iterator();
                    int top = it.next();
                    int second = it.next();
                    stack.push(top + second);
                    break;
                }
                default:
                    stack.push(Integer.parseInt(op));
            }
        }
        int sum = 0;
        for (int v : stack) {
            sum += v;
        }
        return sum;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 29 LN

class Solution {
    public int calPoints(String[] operations) {
        List<Integer> record = new ArrayList<>();
        for (String op : operations) {
            if (op.equals("C")) {
                for (int i = record.size() - 1; i >= 0; i--) {
                    if (record.get(i) != null) {
                        record.set(i, null);
                        break;
                    }
                }
            } else if (op.equals("D")) {
                for (int i = record.size() - 1; i >= 0; i--) {
                    if (record.get(i) != null) {
                        record.add(2 * record.get(i));
                        break;
                    }
                }
            } else if (op.equals("+")) {
                int found = 0;
                int a = 0, b = 0;
                for (int i = record.size() - 1; i >= 0 && found < 2; i--) {
                    if (record.get(i) != null) {
                        if (found == 0) {
                            a = record.get(i);
                        } else {
                            b = record.get(i);
                        }
                        found++;
                    }
                }
                record.add(a + b);
            } else {
                record.add(Integer.parseInt(op));
            }
        }
        int sum = 0;
        for (Integer v : record) {
            if (v != null) {
                sum += v;
            }
        }
        return sum;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 45 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED