C. Visual Programming - VM

The WSA employs many programmers, who perform a bit better or a bit worse each day. This results in higher or lower quality code accordingly. The management understands the importance of high quality code (especially in such a security-sensitive domain!), therefore they decided to optimize the processes of the WSA software department.

The first step of the effort was to send a few managers to understand the nature of the problems. The programmers had shown thousands of lines of source code, written in various languages the managers had never seen before. They had a hard time trying to understand all this, and after weeks of evaluation, they figured out why: most programming languages are too complicated! They concluded that they must design a new programming language that is much simpler, and mandate its use within the organization.

   Two semi-transparent triangles connected with a not-so-bold line
Almost accurate visualisation of the example program (0.pp) for this task

They came up with something more visual (thus user friendly) and vastly simpler (it has only two different constructions and only one kind of instruction). Programmers were initially sceptical of the practicability of these ideas, so WSA management has hired you to prove the merits of the language by implementing certain example algorithms.

This problem is so large it's split in two separate problems: first you should write and test your toolchain for dealing with polyprog programs, then (using your brand new tools) you can attempt to create the example programs.

programming polyprog

The polyprog machine has 16 registers, of which the first 15 (from 0 to 14) are general purpose, while register 15 is the serial input/output (SIO) device. Registers store 16 bit unsigned integers.

Polyprog programs are represented by a list of polygons and lines. Color is specified in 32 bit RGBA (each component is an integer between 0 and 255). Coordinates are unsigned 16 bit integer x;y pairs. A polygon has a fill color, a stroke color, and at least 3 vertices specified by their coordinates. A line is a color and an ordered list of points (coordinates); the end points are the first and last points on the list.

To keep source code clean and readable:

All polygons have at least one line connected to them and a valid program contains at least one polygon.

Limits: DIM=65536 and LLEN=16.

the polyprog processor

The processor has an instruction pointer which points to one of the polygons. A polygon instruction is executed in multiple stages:

Stage 1: register operation

  A = (Y + B + C * D + Register[F]) * (255-X) / ( (255-T) + E ) + Z
and update A accordingly. Register values and constants are converted to 32 bit unsigned integers for the calculation; at the end, the result is truncated back to a 16 bit unsigned integer. (Thus, operations are evaluated modulo 232, division is integer division with non-negative operands, a zero second operand is fatal error and the final result modulo 216 is stored in A.)

Register[F] means the lower 4 bits of the value in F selects which register's value is substituted (the higher 4 bits are ignored).

Stage 2: route selection

Take every vertex of the polygon that has a connected line, sort them by y*DIM+x in ascending order, and walk this list checking for the following condition:

Stage 3: jump

Pick the vertex for which the condition was first satisfied in Stage 2; or if there's no such vertex, pick the last vertex in the above order. The instruction pointer is modified to point to the polygon on the other end of the line connected to the picked vertex.


After a reset all general purpose registers are initialized to contain their own addresses (so that the value in register N is N). The instruction pointer is pointing to the polygon that has the vertex with min(y*DIM+x). The program's input stream is set up so that the first read will get the first byte in the input.

serial input and output (SIO)

When register 15 (SIO) is read, it returns the next byte in the input stream until EOF; once EOF is reached, all subsequent reads will result in EOF. When SIO is written, it appends the byte to the output stream. If an instruction (polygon) attempts to read SIO multiple times, only the first attempt will result in reading a byte from the input stream, subsequent reads in the same instruction will reuse the same (cached) value without removing more bytes from the input. It is possible to read and write SIO in the same instruction, in which case the write happens later. The program stops running immediately when EOF is written to the serial output.

SIO data is an unsigned 8 bit integer placed in the least significant 8 bits of the register, leaving the upper 8 bits 0:

MSB                                        LSB
15                                           0
0  0  0  0  0  0  0  0  d  d  d  d  d  d  d  d
Input EOF is a word with value 256:
MSB                                        LSB
15                                           0
0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0
Output EOF is a word with value >255: at least one of the z bits is 1. (In this case, x bits are ignored.)
MSB                                        LSB
15                                           0
z  z  z  z  z  z  z  z  x  x  x  x  x  x  x  x

program submission syntax

The first line of the program contains two integers P and L separated by a space; P is the number of polygons, L is the number of lines. The next P lines describe polygons, then the next L lines describe lines.

A polygon description starts with 4 integers SR, SG, SB, SA for the stroke color components, then 4 integers FR, FG, FB, SB for the fill color components and an integer C, number of vertices. The rest of the line is a space separated list of X space Y coordinates of the vertices in CW or CCW order.

A line entry starts with 4 integers R, B, G and A for the color of the line, followed by integer P (the number of points) and list of X space Y coordinates giving the points of the line. P is limited to: 2 <= P <= LLEN.


This task is provided as an aid for developing your own toolchain, especially an interpreter, to develop, run and debug polyprogs. Please make sure you solve all inputs of this task before trying to solve the next problem.

Any new implementation of polyprog compilers and interpreters must comply with the standard described above. Verification is possible using the reference programs the Managers have provided. An implementor should run all five reference programs and compare the output to the reference outputs. Unfortunately the reference output of these programs is the Intellectual Property of the WSA, but the managers are willing to compare your output to the references and tell if they match.


You need to run five polyprog programs. A reference serial input, serial.in.bin is also provided; before running a reference program, the SIO's read pointer should be reset to the beginning of this file. Note: serial.in.bin is a binary file.


The output as written by the program on the SIO. Output files are binary, but never contain the \0 (nil) character. If your interpreter outputs \0 executing any of the reference programs, it is broken.

Example input

2 1
0 0 0 254 47 0 0 254 3 100 100 110 110 80 110
0 0 0 254 255 18 0 254 3 200 200 210 210 176 210
0 0 0 1 3 80 110 150 150 176 210

("The Input stream contains pairs of 7-bit unsigned integers in binary format; sum each pair and print the result to the output as 8-bit unsigned int in binary format. The program shall stop when EOF is read on the input stream. If the input stream contains an odd number of bytes, ignore the last byte.")

Example output

Running the reference solution on serial.in.bin should result in 3 bytes on the output stream - here represented in a hexadecimal format:
D3 D1 D5