Editor

Undo the Spreadsheet Edits

#608 · Stacks and queues · Intermediate · 75 XP · about 15 min

A tiny spreadsheet keeps its cells in a dictionary such as {'A1': '5'}. Each edit is saved on an undo stack as a record of the cell and the value it had before, so the edits can be taken back in reverse order.

Write apply_edits(actions) that starts with an empty sheet, carries out the actions in order and returns the final sheet:

  • 'SET A1 5' sets cell A1 to the text '5'. A cell can be set again and again, and each SET is one edit.
  • 'UNDO' takes back the most recent edit that has not been undone yet: the cell gets its old value back, or disappears from the sheet if it was empty before that edit. With nothing left to undo, UNDO does nothing.

Return the sheet as a list of (cell, value) tuples sorted by cell name as text (so 'A10' comes before 'A2').

Examples

apply_edits(['SET A1 5', 'SET B2 hi', 'SET A1 7', 'UNDO'])
# returns [('A1', '5'), ('B2', 'hi')]
apply_edits(['SET C3 1', 'SET C3 2', 'SET C3 3', 'UNDO', 'UNDO'])
# returns [('C3', '1')]
apply_edits(['SET A1 5', 'UNDO', 'UNDO'])
# returns []

In the last example the first UNDO empties A1 again, and the second finds nothing to undo.

Constraints

  • 0 <= len(actions) <= 10,000
  • Cell names and values never contain spaces.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.