# Internet Problem Solving Contest

## Solution to Problem H – Holy cow, Vim!

### Easy subproblem H1

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 3``````

In 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;*;print``````

The full program then becomes:

``````push 1;input;print;jump 3
push 0;input;push -1;*;print;jump 3
push 2;input;dup;*;print;jump 3``````

### Hard subproblem H2

Arithmetic 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 99``````

If 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 99``````

We 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+1``````

Putting 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;dup``````

The 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``````