# Internet Problem Solving Contest

## Solution to Problem Q – Quack Strikes Back

Solving this task was pretty straightforward. We use the register n to store the input number, registers a and b to store two consecutive Fibonacci numbers. The queue is used to perform the required computations, one at a time.

The actual code follows and is explained below.

```>n
Znend

0
>a
1
>b

:loop

<a
P

<n
1
-
>n
Znend

<b
<a
<b
+
>a
>b

Jloop
:end
```

Store the input number. If it is zero, terminate without printing anything. Initialize a and b to the first two Fibonacci numbers. In a loop: print the current number, compute how many numbers still have to be printed (terminate if zero), push values b and a+b and store them into a and b respectively (thus computing the next Fibonacci number).

First we will consider a more simple task: to write a quine (i.e. a program that prints its source). We will use the most straightforward method. A program usually consists of two parts: data and code.

In our case data will obviously be a sequence of numbers. Imagine a program, whose code part simply takes the data, interprets it as ASCII values of characters and prints these characters. Writing this code is trivial.

Second step: how to select the data? We want to print the source of the program. The only part we have so far is our first code. What happens when we take the ASCII values of code as data? We obtain a program that prints its own code part. We are not done yet, but we already made a major step.

What remains is to print the data part. Nothing could be simpler. We will slightly modify our code. The new code2 will do the following:

1. Take data. Interpret it as numbers and print them.
2. Take data again. Interpret it as ASCII values of characters and print those characters.

In the first step this program will correctly print its data part. If we choose data to be ASCII values of code2, in the second step the program will correctly print its code part.

Now back to our original task – to write an eniuq. The idea remains the same: the program will consist of a data part and a code part. But this time the code part will have to be more tricky. Again, suppose that the data part contains the ASCII values of characters in the code part. This time, the code part has to:

1. Take data and reverse it.
2. Take data again. Interpret it as ASCII values of characters and print those characters.
3. Take data again. Interpret it as numbers and... print them? Wrong! For each number, we have to print its digits in reverse order.

Reversing the data: Push two zeroes. We will try to rearrange the queue in rounds. In each round we will move one of the numbers. After each round the queue will contain: "(suffix of data) 0 (reversed prefix of data) 0". In the beginning we are clearly in such situation. In each round we take the first number in the first part and move it to the beginning of the second part.

Printing the characters is simple, it can be done in one pass through the queue. But how to reverse the digits of each number? We will use a little dirty trick: Our code will only use the registers a and b, all labels will be uppercase. Thus each character in our code part has ASCII value between 10 (line feed) and 98 (lowercase b) – in other words, each of the numbers in the data part will have exactly two digits. This will make reversing their digits reasonably simple.

The last step we have to figure out is how to do arithmetic operations on all numbers in the queue. If the queue was empty, performing the operations was simple: push operands, do the operation, pop the result. Now it is not that simple. We will have to do it in two passes. In the first pass we fill the queue with the correct operands, in the second pass we will apply all operators.

As an example, suppose we want to add 47 to each of the numbers in the queue. In the beginning the queue contains "a b c d e ... y z 0" (where letters represent arbitrary positive numbers). In the first pass we change the queue to contain "1 a 47 1 b 47 1 c 47 ... 1 z 47 0". Note that we added the ones to be able to detect when to stop applying addition.

A slightly commented code part of our solution follows. We assume data is the sequence of ASCII values of these characters.

We start by pushing two zeores and reversing the sequence of numbers.

```0
0

:REVNEXT
>a
ZaREVDONE
>b
ZbEND1ST
<b
:END1ST
0
<a
>b
ZbEND2ND
<b
:END2ND
0
JREVNEXT

:REVDONE
```

Print the characters corresponding to the current contents of the queue.

```:LOOP1
>a
ZaLOOP1END
Ca
<a
JLOOP1
:LOOP1END
0
```

For each x in the queue push "1 x 10 x 10". In the next pass, compute x%10 and x/10. Push a 48 (ASCII value of '0') after each of the results.

```:LOOP2
>a
ZaLOOP2END
1
<a
10
<a
10
JLOOP2
:LOOP2END
0

:LOOP3
>a
ZaLOOP3END
1
%
48
/
48
JLOOP3
:LOOP3END
0
```

Add 48 to each number in the queue. Push a 10 (line feed) after each two numbers. Finally, print all computed numbers as characters and we are done.

```:LOOP4
>a
ZaLOOP4END
1
+
+
10
JLOOP4
:LOOP4END
0

:LOOP5
>a
ZaEND
C
C
C
JLOOP5

:END
```