Two years ago the IPSC contestants had a hard time to understand a piece of code written in PostScript. Last year wasn't any better as we introduced a queue-based programming language. If you didn't participate last year (and even if you did :), this practice session will give you an unique chance to find out how difficult it was. But let's start with the basics:
A queue is a data structure that supports two operations: Put (insert an element into the queue) and Get (remove and return the element that has been in the queue for the longest time). Just like a queue in a shop – new customers are "inserted into the queue" at the end while the customer at the beginning of the queue is served and leaves.
We will define a simple programming language Quack. Quack uses a single queue to store (almost) all the data. At the start of the program, this queue is empty. The only data type in Quack is number: an integer from the range 0-65535. All mathematical operations are computed modulo 65536. (For example, 65530+10=4.) In addition to the queue, Quack has 26 registers denoted by lowercase letters (i.e. a-z). Each register holds one number.
A program is a sequence of commands separated by whitespaces. The first character determines the command, optionally followed by parameters. The commands are defined below:
| operation | description |
|---|---|
| + | Addition: get x, get y, put (x+y) modulo 65536. |
| - | Subtraction: get x, get y, put (x-y) modulo 65536. |
| * | Multiplication: get x, get y, put (x*y) modulo 65536. |
| / | Integer division: get x, get y, put x div y. (y mustn't be zero) |
| % | Modulo: get x, get y, put x modulo y. (y mustn't be zero) |
| Command | Description |
|---|---|
| >[register] | Get into register: get x, set the value of [register] to x. |
| <[register] | Put from register: put the value of [register]. |
| P | Print: get x, print x to the standard output, print a newline. |
| P[register] | Print register: print the value of [register] to the standard output, print a newline. |
| C | Print as char: get x, print the character with ASCII code x modulo 256 to the standard output. |
| C[register] | Print register as char: print the character with ASCII code x modulo 256 (where x is the value of [register]) to the standard output. |
| Command | Description |
|---|---|
| :[label] | Label: this line of the program has the label [label]. |
| J[label] | Jump (unconditional): the execution of the program continues on the line with the label [label]. |
| Z[register][label] | Jump if zero: if the value of [register] is zero, the execution of the program continues on the line with the label [label]. |
| E[register1][register2][label] | Jump if equal: if the values of [register1] and [register2] are equal, the execution of the program continues on the line with the label [label]. |
| G[register1][register2][label] | Jump if greater: if the value of [register1] is greater than the value of [register2], the execution of the program continues on the line with the label [label]. |
| Command | Description |
|---|---|
| Q | Quit: terminate the execution of the program. The program also terminates if the instruction pointer reaches the end of the program. |
| [number] | Put a number: If the first letter of a command doesn't match any of the previous lines, try to convert the command to a number and put in in the queue. |
The following program computes the sum 1 + 2 + ... + 20.
20 0 :start >a Zaend <a <a 1 + - >b <b Jstart :end P
Every time the execution of this program reaches the third line (the line with the label "start"), the queue contains exactly two numbers: the first is N, the second is the sum (N+1) + ... + 20. The number N is loaded into the register a. If it is already zero, the program jumps to the line with the label "end", prints the computed sum, and quits. Otherwise, we want to add N to the partial sum and decrease it. After the eighth instruction (put 1) the queue contains the values: PartialSum, N, N, 1. The following two instructions compute PartialSum+N and N-1. Finally, we place them in the correct order and repeat the loop.
For your convenience we provide you with an interpreter of this programming language. You may either download and compile it (you need a C++ compiler and STL to compile it) or use this web form. Please don't overuse the web form so that everyone gets a chance to use it.
Easy: Write a program to compute Fibonacci numbers in Quack.
Fibonacci numbers are defined as follows: F0=0, F1=1 and Fn+2=Fn+1+Fn.
The input is a non-negative number N (not exceeding 10000) which is placed in the queue before your program is executed. Your program should output a sequence of N numbers, the i-th of them being Fi-1 modulo 65536. Your program will be tested on various inputs, to be accepted it has to solve all of them correctly.
(Note that you may test your program by simply writing the input sequence as the first few lines of the code.)
Execution of your program may not take more than one million steps to finish. If this limit is exceeded, the program will be terminated. In such case you will receive a message "Too many steps." and your submission will be rejected.
Credits:
Problemsetter(s): misof
Contest-related materials: misof, Tom