The keystroke journal
A text editor records every keystroke in a log, just in case: if the program crashes, the document can be restored by replaying the log from the start. Today the program crashed. Restore the document.
The document is empty at first, and the cursor is at its start. Each character of the log is one keystroke:
<moves the cursor one character to the left,>one to the right;[moves the cursor to the start of the document,]to the end;#erases the character to the left of the cursor;- any other character, including a space, is typed where the cursor stands, and the cursor ends up right after it.
A keystroke that has nothing to do (left at the very start, erase at the very start, right at the very end) changes nothing. The third and fourth tests are the log of a typist who was typing the first chapters of War and Peace in Russian: the typist corrects typos sometimes at once, sometimes a few letters later, and types the title at the very end of the work.
Input
One line: a log of 1 to 10⁶ characters in UTF-8. The characters <, >, [, ], # never occur in the text of the document: in the log they always mean keys.
Output
The document after all the keystrokes, on one line (empty if nothing is left in the document).
Examples
Example 1
и мр<и>[война ]!!#
война и мир!
Example 2
#<[кот]>>#<<<
ко
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Inserting into the middle of a Python list or a string means shifting the whole tail. What will that cost if half the text is typed at its start?
2Hint 2
A well-known trick for an editor is two stacks: everything left of the cursor and everything right of it. A letter, an erase, a step left and right cost O(1). And what do [ and ] cost?
3The idea
You need a structure in which both inserting at the cursor and jumping to the start or the end cost O(1). That is a doubly linked list with a sentinel: the sentinel closes the list into a ring, its right neighbour is the first letter, its left neighbour the last. The cursor is a link to the node it stands before; a cursor before the sentinel is the end of the document.
4Walkthrough
It is convenient to keep the nodes not as objects but as numbers in three arrays: ch, prev, next; node 0 is the sentinel. A new letter gets the next free number, and inserting before node at rewrites four links: two of the new node, next of its left neighbour and prev of at. Erasing throws out node prev[at] by linking its neighbours, two links. Left is at = prev[at] if the left is not the sentinel; right is at = next[at] if at is not the sentinel. To the start is at = next[0], to the end at = 0. At the end walk from the sentinel along next and print.
Erased nodes stay in the arrays, simply nobody links to them any more; there are no more nodes than the length of the log, so the memory is O(n). Arrays of numbers instead of objects are also faster in Python: creating a node object costs more than writing a number into a ready cell, and on the sixth test the version with objects is twice as slow.
4+Solution
5Complexity
O(n) for the whole log: each keystroke is O(1), and the final text is printed in one pass. Memory O(n).
6Common mistakes
- A Python list and a cursor index.
insertanddelin the middle shift the tail. The sixth test types half a million letters at the start of a long text: each shifts half a million cells. A shift is a fast memory copy, and on short logs it goes unnoticed, but here it comes to a quarter of a trillion cells moved. - Two stacks. The classic solution for an editor without “to the start” and “to the end” keys. Here every
[moves the whole left stack into the right one, and the seventh test jumps between the ends a hundred thousand times. It is the same gap buffer as in Emacs: good while edits are close to each other. - A space in the log. A space is a letter too: do not split the line on spaces and do not strip it, except for the newline at the end.
- An empty document. The ninth test erases and moves the cursor in an empty document; none of these keys should crash.