#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').
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.
0 <= len(actions) <= 10,000First solves only, ranked by stars and then time.