Undo and Redo for Document Edits

HardPython

Problem

Implement history management for a simplified Figma Design canvas. The canvas is represented by an ordered list of layer names, and actions can insert, delete, or replace a layer, then undo or redo previous edits.

Formal Specification

Write apply_history(initial, actions), where initial is a list of strings and actions is a list of dictionaries. Each edit dictionary has one of these forms:

{"type": "insert", "index": i, "value": name}
{"type": "delete", "index": i}
{"type": "set", "index": i, "value": name}

The remaining actions are {"type": "undo"} and {"type": "redo"}. Return the final list of layer names.

Each successful edit creates one undo step. undo restores the most recent undone edit, and redo reapplies the most recently undone edit. Calling undo or redo when its history is empty has no effect. After a new edit, all redo history must be discarded. Do not mutate initial.

Constraints

0 <= len(initial) <= 10^4
1 <= len(actions) <= 10^4
Layer names are non-empty strings
Edit indices are valid for the state at the time of the action
Each action has one of the specified formats

Function Signature

def apply_history(initial, actions):

Formal Specification

Write apply_history(initial, actions), where initial is a list of strings and actions is a list of dictionaries. Each edit dictionary has one of these forms:

{"type": "insert", "index": i, "value": name}
{"type": "delete", "index": i}
{"type": "set", "index": i, "value": name}

The remaining actions are {"type": "undo"} and {"type": "redo"}. Return the final list of layer names.