Transaction crash recovery
Your task
A checkout ledger crashed and recovery has to decide what to roll back. The journal is the records it appended, in order, with fields separated by a vertical bar. "begin|t7" opens transaction t7. "put|t7|cart:12|open" records that t7 wrote the value open to the key cart:12. "commit|t7" and "abort|t7" close t7. A transaction needs undo when it wrote at least one value and the journal holds neither a commit nor an abort for it, so its work is neither durable nor already rolled back. A transaction that opened but wrote nothing has nothing to undo. Some puts have no begin in this journal because the begin predates the last checkpoint, and those writes still count. Return the transaction ids needing undo, without duplicates, sorted ascending as text, so "t10" comes before "t2".
Examples
txns_needing_undo(journal: list[str]) -> list[str]txns_needing_undo(["begin|t1", "put|t1|cart:12|open", "commit|t1", "begin|t2", "put|t2|cart:13|open"])["t2"]txns_needing_undo(["begin|t3", "commit|t3", "begin|t4", "put|t4|user:9|paid", "abort|t4"])[]txns_needing_undo(["put|t8|order:1|new", "begin|t9", "put|t9|order:2|new", "begin|t7", "put|t7|order:3|new", "commit|t9"])["t7", "t8"]