In the easy subproblem, we can have multiple commands on one line separated by semicolons. The stack is initially empty but can stay non-empty when the program ends, so we can use the push command to determine the line order after sorting. The pushed values are ignored otherwise. For example, the following structure works:
push 1;... subroutine for x -> x ...;jump 3
push 0;... subroutine for x -> -x ...;jump 3
push 2;... subroutine for x -> x * x ...;jump 3In the normal case, the subroutine for x is executed and then the execution jumps to the line number 3, which means the program exits. In the reversed case, the subroutine for x2 is executed. Finally, in the sorted case the second line becomes the first and the subroutine for −x is executed. The subroutines are respectively:
input;print
input;push -1;*;print
input;dup;*;printThe full program then becomes:
push 1;input;print;jump 3
push 0;input;push -1;*;print;jump 3
push 2;input;dup;*;print;jump 3Arithmetic operations come before letters in the ASCII table. Also the dup command comes before all other word commands, so arithmetic operations together with dup are always first in the sorted order. However, all these operations crash with an empty stack and we don’t get a chance to push anything onto the top of the stack before we execute them, so we cannot have lines starting with arithmetic operations or dup.
A trick to execute such operations is to wrap them in “push ?” and pop. E.g. for + we have:
push 42
pop;+The general idea of the solution is to have 3 areas of the program separated by “jump 99” commands (assuming the program has 99 lines):
... subroutine for x -> x ...
...;jump 99
... extra lines for x -> -x ...
...;jump 99
... subroutine for x -> x * x when reversed ...Let’s label these 3 areas α, β and γ respectively. For γ, we can use the following sequence of commands (showed in reversed order for clarity).
input;dup
push ?
pop;*
print;jump 99If there are multiple input commands in the program, we need to make sure only one gets executed each time. One line can start with input and another can contain “push ?;input”. A jump command between them makes sure only one of them gets executed. As “input;dup” is already in γ, we use “push ?;input” in α. The whole α then becomes:
push ?;input
print;jump 99We know that “input;dup” ends up at the beginning of the sorted program. A jump command comes lexicographically right after input, so we can add it to β and use it to jump to the part calculating −x in the sorted program. The jump can go to a line starting with pop, print or push. Jumping to a print would be wrong, since we have x at the top of the stack at that point. Instead, we can calculate −x by pushing −1 onto the stack and then multiplying the two top-most elements. So we point jump to the line “push -1;*”, which we add to β.
The lines that follow in the sorted order after “push -1;*” start with push commands, which don’t allow us to print −x that is at the top of the stack, we jump back in the program using “push z;jump ℓ”, where ℓ is a line higher up in the program. We just pushed z to the stack, so the line we jump to starts with pop. We want the line that comes after popping z from stack to be “print;jump 99”, so the line popping z must come lexicographically after “pop;*” (from γ). We achieve it by using “pop;jump ℓ + 1”, which effectively continues on the next line.
To recapitulate, we have the following lines in β:
jump L # Line number to be determined
push -1;*
push ?;jump K # Line number to be determined
pop;jump K+1Putting all pieces together, the program looks as follows (with line numbers for clarity):
0: push 2;input
1: print;jump 10
2: jump 6
3: push -1;*
4: push 1;jump 3
5: pop;jump 4
6: print;jump 10
7: pop;*
8: push 3
9: input;dupThe sorted program is the following:
0: input;dup
1: jump 6
2: pop;*
3: pop;jump 4
4: print;jump 10
5: print;jump 10
6: push -1;*
7: push 1;jump 3
8: push 2;input
9: push 3