Q. Plot

The Institute of Modern Art graciously provided you with a set of brushes. Having unpacked and tried each of them, you realize you can't really paint. Fortunately you find a strange photoplotter in a dark corner (according to other artists also confined to the Institute, it's mainly used for typesetting the catalogues for exhibitions).

You quickly hook up the plotter to your computer and reverse-engineer the strange communication protocol. It seems the plotter runs some sort of interpreter and can draw squares (also known as Resolution Independent Pixels). You decide to dig up a few photos and try to program the device to copy them onto the canvas.

   The albino. Drawn by the plotter
The albino. Drawn by the plotter

Your task is to draw a large grayscale picture similar to the input picture using a less-than-capable VM. Drawing primitives are squares given as x;y coordinates of their upper left corner and size. The image buffer is white at the beginning. There are two drawing modes: brush and erase. Brush increases the blackness of the image buffer at the given area by 1/4, erase decreases it by 1/4. Thus, it is possible to draw with 5 shades only (the possible pixel values on a 8-bit depth greyscale image: 255 (white), 192, 128, 64 and 0 (black)).

There is an upper limit on how many CPU instructions the plotter is willing to run - when this is reached, it simply stops interpreting. The plotter has very limited code memory as well, so only short code can be uploaded to it.

Constants:
NameValueDescription
IMGW16000image width in pixels
IMGH16000image height in pixels
MAXINST1000000maximum number of evaluated instructions
MAXCODE20000maximum code size (memory slots)
MAXAREAIMGW*IMGH*4maximum number of pixels brushed or erased
NUMREGS1024number of registers

The interpreter

Registers

Registers are numbered from R0 to R(NUMREGS-1). The first few registers have special function and alias:
R0 is PC program counter
R1 is the Z flag 1 means result of the last operation was zero (else it's 0)
R2 is the O flag 1 means last operation caused overflow (else it's 0)

Each register holds a signed integer between -2147483648 and 2147483647 inclusive. There is no dedicated stack or other accessible memory. Image buffer is write-only. Code memory is a separate read-only block of instructions, each instruction (all arguments included) taking up one slot.

A drawing instruction works from 3 adjacent registers, address of the first one specified by the user, and interprets them as X, Y, and W, where X and Y are the coordinates where the square shall be drawn and W is the width of the square. All coordinates are in pixels, from top-left of the image buffer, counting from 0. Width is in pixels. The coordinate specified will be the top left pixel of the square being drawn.

Value of all registers are 0 before the VM runs the first instruction.

When addressing in indirect mode, address is always taken as modulo NUMREGS.

Instruction set

Move:
 movr  Rdest, Rsrc   - move value from Rsrc to Rdest
 movc  Rdest, const  - move constant to Rdest
 movi  Rdest, Rsrc   - like movr, but both values of Rdest and Rsrc are interpreted
                       as register addresses (indirect memory addressing)

Arithmetics (all of these affect both Z and O flags):
 add  Rdest, Rsrc   - Rdest := Rdest + Rsrc
 sub  Rdest, Rsrc   - Rdest := Rdest - Rsrc
 mul  Rdest, Rsrc   - Rdest := Rdest * Rsrc
 div  Rdest, Rsrc   - Rdest := Rdest div Rsrc
 mod  Rdest, Rsrc   - Rdest := Rdest mod Rsrc

Draw:
 brush Rstart       - brush using the values in the 3 registers starting with the
                      one pointed to by Rstart
 erase Rstart       - erase using the values in the 3 registers starting with the
                      one pointed to by Rstart

Misc:
 exit               - stop execution (the image is ready)

PC and jumps

After the current instruction is loaded from the slot pointed by PC, but before the instruction takes effect, PC is immediately increased by one. Thus the shortest infinite loop is:
 movc R3, 1
 sub R0, R3
or using the PC alias:
 movc R3, 1
 sub PC, R3
The VM runs at most MAXINST instructions, if it doesn't encounter 'exit' before then, an error is generated. Code memory size is MAXCODE slots; above that, PC simply rolls over.

Arithmetics

Arithmetics is evaluated at arbitrary precision, then the result is fixed using the following method (using pseudo code, assuming the precise result is R):
Z := 0
O := 0
while R > 2147483647 do
	O := 1
	R -= 4294967296
end
while R < -2147483648 do
	O := 1
	R += 4294967296
end
if R == 0 then
	Z := 1
end
Rdest := R
The DIV and MOD instructions are evaluated the following way: if Rsrc == 0 then they fail; otherwise the arbitrary precision result of DIV and MOD are D and M such that
D := floor(Rdest/Rsrc)
M := Rdest - D*Rsrc
where floor(x) rounds the real value x downward to the nearest integer. Examples:
RdestRsrcDM
22 5 4 2
-22 5-5 3
22-5-5-3
-22-5 4-2
(This is how division works in pascal and python, but not in c and java where the result is rounded toward zero and not downward)

Drawing

The image starts with all pixels white. Drawing beyond the canvas is tolerated by the vm - squares are clipped so that only those pixel changes take effect which are on the canvas. When drawing a square from 2;3 with width 4, the top-left pixel is 2;3, the bottom-right pixel is 5;6. Drawing with 0 or negative width is also ignored.

Lamp of the photoplotter is expensive, thus the device has a built-in limit on the total area it is willing to draw in a single program (MAXAREA). The total area is calculated as a sum of the area of all squares drawn (both brush and erase), even for those pixels that were beyond the canvas. When the limit is reached, an error is generated.

Input

The photo to be copied.

Output

A list of photoplotter instructions in plain text format, one instruction per line.

Scoring

At the end the Euclidean distance of the image buffer and the input image is calculated and a score is given based on the best submission so far.

Evaluated score:

D := round(sqrt(SUM((P-Q)*(P-Q))))
where the SUM is taken over each P, Q corresponding pixels of the images

Scaled real score:

SCORE := round(100 * (1 - sqrt(1 - Dmin/D)))
where Dmin is the best submission so far.

Example program

(Broken into two columns for clarity, same as example.asm)

movc R3,20
movc R4,5
movc R5,5
movc R6,60
movc R7,1
movc R8,4
movc R9,6
movc R10,5
movc R11,17
movi R3,R8
add  R3,R7
movi R3,R5
add  R3,R7
movi R3,R9
sub  R3,R7
sub  R3,R7
brush R3
brush R3
brush R3
add  R3,R5
add  R4,R5
add  R4,R6
sub  R10,R7
sub  R7,Z
mul  R11,R7
sub  PC,R11
movc R3,50
movr R50,R6
div  R50,R8
movc R51,-10
movc R52,40
erase R3
erase R3
movc R51,40
erase R3
erase R3
movc R50,90
movc R51,15
erase R3
erase R3
movc R52,25
brush R3
movc R51,30
brush R3
movc R50,145
movc R51,5
movc R52,50
erase R3
erase R3
movc R40,65
add  R50,R40
erase R3
erase R3
add  R50,R40
movc R51,15
movc R52,40
brush R3
exit

Output of example program

Top left corner of the output image for the example program:

example output