Program within a Program (Small)

A robot stands on a highway that runs east and west without end, and it carries a cake. There is a lamppost every mile in both directions. The robot must release the cake at the lamppost exactly $N$ posts east of the one it starts at. The route does not matter, only the lamppost where the cake is released.

The robot has very little memory and cannot reason on its own, so you give it a program before it starts. The program is a list of one or more statements in this format.

<S> <M> -> <action>

A statement applies when both of these hold.

1. The robot is in state S.
2. The robot stands at a lamppost marked with the number M.

Then <action> is one of the following.

1. <D> <NS> <NM>: write the number NM on the current lamppost, change the state to NS, and move one lamppost in direction D, where D is W for west and E for east.
2. R: release the cake at the current position and self-destruct.

If two or more statements share the same S and the same M, the robot misbehaves and destroys the cake. If the robot is in state X at a lamppost marked Y and no statement has S equal to X and M equal to Y, the robot gets confused and eats the cake.

Every state and every mark is an integer of absolute value at most 1,000,000. The robot starts in state 0, and every lamppost starts marked with 0.

Given $N$, print a program that makes the robot release the cake at the lamppost $N$ posts east of the start. The program must use at most 30 statements, and the robot must make at most $X$ moves. Many programs meet these conditions, so the output section fixes exactly one of them.

The first line has the number of test cases $T$. Each of the next $T$ lines has one integer $N$, the lamppost where the robot must release the cake.

For each test case, first print Case #x: 27, where $x$ is the test case number starting at 1. Then print the following 27 statements in exactly this order.

0 0 -> W 1 0
1 0 -> W 2 c0
2 0 -> W 3 c1
3 0 -> W 4 c2
4 0 -> W 5 c3
5 0 -> W 6 c4
6 0 -> W 7 c5
7 0 -> W 8 c6
8 0 -> W 9 c7
9 0 -> W 10 c8
10 0 -> E 11 4
11 0 -> W 12 0
11 1 -> E 11 1
11 2 -> E 11 2
12 0 -> W 12 0
12 1 -> W 12 2
12 2 -> E 13 1
12 3 -> W 12 3
12 4 -> E 14 4
13 0 -> E 12 3
13 1 -> E 13 1
13 2 -> E 13 2
13 3 -> E 13 3
14 0 -> R
14 1 -> E 14 1
14 2 -> E 14 2
14 3 -> E 14 3

The values c0 to c8 depend on $N$. Write $N$ as a nine digit binary number $N = \sum_{j=0}^{8} b_j 2^j$ with $b_j \in \{0, 1\}$, and set $c_j = 1 + b_j$. So the value is 1 when binary digit $j$ of $N$ is 0, and 2 when it is 1. Only those nine lines change with $N$; the other eighteen lines are the same for every $N$.

• $1 \le T \le 15$
• $0 \le N \le 500$
• $X = 1000000$

The nine lampposts west of the start hold $N$ in binary, one digit per lamppost, with the lowest digit closest to the start. Mark 1 means the digit 0 and mark 2 means the digit 1. States 0 to 10 write those nine digits and then the boundary mark 4 one post further west, and state 11 walks back east to the starting lamppost.

The rest is a loop. In state 12 the robot walks west over the lampposts it has already visited (mark 3) and subtracts 1 from the stored number: a lamppost holding the digit 0 (mark 1) becomes 2 and the borrow continues west, and the first lamppost holding the digit 1 (mark 2) becomes 1, which ends the subtraction. After a successful subtraction, state 13 walks back east, writes 3 on the first unmarked lamppost, and moves one post further east. That move is the single step east. If the stored number is already 0, the borrow reaches the boundary mark 4, and state 14 walks east and releases the cake at the first unmarked lamppost. The subtraction succeeds exactly $N$ times, so the cake lands on the lamppost $N$ posts east of the start. The program uses 27 statements and makes at most 253,029 moves.