Skip to main content
ZhimaYuandi

D01 · PREDICT · OPERATE · EXPLAIN YOUR CHOICE

Stack Lab: Undo Mistakes in a Campus Organizer

After editing a title and deleting a record, undo restores an older action instead of the latest one. History may be ordered incorrectly or its tags may still share mutable lists with current records.

Back to the practice route →

Make a prediction first

  • Implement LIFO in HistoryStack with list-tail append and pop. Save an independent snapshot before each successful add, edit or removal. Failed actions must not create history.
  • Undo restores exactly the latest successful mutation. Report an empty stack explicitly. History is session-local; redo and history across restarts are out of scope.
  • Copied tags must be independent. In M2, synchronize ID and title indexes after undo. This lab does not execute student Python online.

This is a deterministic teaching model. State checks inspect model invariants, not your prediction or Python code, and do not establish mastery. Model operation counts, browser time and Python implementation costs are different measures.

Controlled data-structure model

Inspect the model manually

Each action changes a controlled sample. This does not execute student Python, read disks or certify mastery from clicks or model state.

Save independent snapshots before successful mutations

History is listed bottom to top; the last entry pops first. Failed actions do not increase depth.

    Current records

    • doc_00000000000000000000000000000001 · Document-1 · study
    • doc_00000000000000000000000000000002 · Document-2 · study
    • doc_00000000000000000000000000000003 · Document-3 · study

    Three fixed sample records restored; history is empty. · Current model invariants: Consistent

    Operation counts and model scope

    Checks independent snapshot tags, unique IDs per snapshot and push/pop balance against depth. This inspects model state, not student code correctness.

    Pushes
    0
    Pops
    0
    Copied records (including restore)
    0
    History depth
    0
    Current records
    3

    For the container alone, append is amortized O(1) and tail pop is typically O(1). This model copies whole collections, so snapshot creation and restoration depend on record/tag volume. Entire undo is not O(1). Counts show pushes, pops and copied records, not browser timings.

    Counts follow the model definition, not browser elapsed time. Copies for displaying and saving model state are not counted as underlying container operations.

    Execution trace (up to 40 recent events)

    1. Three fixed sample records restored; history is empty.

    This checks model state only. It does not execute your Python or grade your prediction.

    Unchecked or invalidated

    Progressive learning hints

    Hints are fixed teaching content. Their use is recorded.

    Hint 1

    Write three successful actions as A, B and C. Predict which moment the first undo should restore.

    Hint 2

    Check that history length is unchanged after failure. Is copying only the list enough? Change tags and inspect an older snapshot.

    Hint 3

    Copy records and tags before a successful mutation, then push. Undo pops the latest snapshot. Account separately for copying, ID search, restoration and index rebuilding.

    My Python draft

    Save and export your draft here. Code is not executed or synced to the starter. Draft, input or strategy edits invalidate earlier model results and self-reports.

    Local learning records

    Saved only in this browser; export is available. No cross-device sync or proof of mastery. Earlier F01 and six-task records are preserved through migration.

    • D01 opened: —
    • Model check: Unchecked or invalidated
    • Local tests (self-reported): —
    • Highest hint level: 0/3
    • Reference viewed: —
    • Unaided variant (self-reported): —

    Implement it in the same Campus Resource Organizer

    class HistoryStack:
        def __init__(self):
            self._items = []
    
        def push(self, snapshot):
            raise NotImplementedError
    
        def pop(self):
            raise NotImplementedError
    

    An independent snapshot adds only this lab’s fault to the M1 baseline. The M2 starter contains all three labs’ unfinished parts. Keep reference answers separate from your own work.

    Download this lab’s starter

    python check_environment.py
    python -m unittest tests.test_d01 -v
    python -m unittest discover -s tests -v

    Use Python 3.11+ and its standard library. Extract into a new directory. See the package’s exact intentional-failure list. A passing reference validates materials; you still need to run your own code.

    Independent variant

    Independently implement challenges.brackets_match(text) to match (), [] and {} while ignoring other characters. Test empty input, crossed pairs, premature closing and unclosed pairs. Explain why the most recently opened bracket must match first. No implementation steps are given.

    python -m unittest tests.test_m2_variants -v

    Replace the skipped placeholder in tests/test_student_counterexamples.py with your own counterexample and explanation. Attempts using hints or references are not recorded as unaided.

    Costs and model boundaries

    For the container alone, append is amortized O(1) and tail pop is typically O(1). This model copies whole collections, so snapshot creation and restoration depend on record/tag volume. Entire undo is not O(1). Counts show pushes, pops and copied records, not browser timings.

    Reference explanation and answer

    View reference explanation (records answer use)

    A stack restores the state immediately before the latest successful mutation. Create history after validation but before mutation; do not push failures. Independent tag copies prevent later edits from corrupting history. Tail append is typically amortized O(1), but whole-collection copies, restoration and index rebuilds add separate costs.

    Download this lab’s reference (answer) · Version and source digest

    Course references and related experiments