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 |
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:
Name | Value | Description |
---|---|---|
IMGW | 16000 | image width in pixels |
IMGH | 16000 | image height in pixels |
MAXINST | 1000000 | maximum number of evaluated instructions |
MAXCODE | 20000 | maximum code size (memory slots) |
MAXAREA | IMGW*IMGH*4 | maximum number of pixels brushed or erased |
NUMREGS | 1024 | number of registers |
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.
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)
movc R3, 1 sub R0, R3or using the PC alias:
movc R3, 1 sub PC, R3The 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.
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 := RThe 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*Rsrcwhere floor(x) rounds the real value x downward to the nearest integer. Examples:
Rdest | Rsrc | D | M |
---|---|---|---|
22 | 5 | 4 | 2 |
-22 | 5 | -5 | 3 |
22 | -5 | -5 | -3 |
-22 | -5 | 4 | -2 |
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.
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.
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 |