Most of you have already heard of the PostScript file format. Right now, you are probably thinking that PostScript is "just a way to describe how a page of text looks like". We will prove you wrong. PostScript is a fully functional programming language, like any other language you know. Or (more precisely said) much UNLIKE any other language you know. To prove what we just said, both input files are PostScript files that actually compute something and do many other interesting things.
Your task will be simple – to determine what do the files compute and to send us the result. Yes, the computation takes a really long time, but that's the point. Understand, simplify, solve. And don't worry, we won't let you into the battle unprepared. The following paragraphs contain a short introduction to the PostScript programming language.
What's the main difference between PostScript and the classic programming languages? Most programming languages you probably know use infix notation of many functions. E.g. you write "4 + 7" when you want to add 4 and 7. PostScript uses postfix notation. (Hence the name "PostScript".) This essentially means that you have to write first the operands and then the operation. To add 4 and 7, you will have to write "4 7 add"
But let's start from the beginning. PostScript is an interpreted, stack-based language. During the interpretation, the interpreter maintains a stack (sometimes also called a buffer) containing processed data. Initially this stack is empty. One step of the interpretation looks as follows: The interpreter reads a token (a piece of data) from the file. If it is an operation, it is executed. Otherwise it is an operand and it is pushed on the stack.
A simple example: Let's consider the piece of code "4 1 7 add". First the interpreter
reads "4". It does not know how to execute "4" so it is pushed on the stack.
Tokens "1" and "7" are processed in the same way. After processing
"7" the stack looks as follows (with the top on the right):
STACK: 4 1 7
Now the interpreter encounters the operation "add". This operation pops two
topmost elements of the stack, computes their sum and pushes it on the stack. Most
of the basic operations work in a similar way. (Pop some elements, do something, push some
results.) After interpreting the operation "add" the stack looks as follows:
STACK: 4 8
We will now describe some of the basic operations in PostScript. We use the following notation: "operand1 ... operandN operation result1 ... resultM". The operands may be preceded by the word "(bottom)", this means that all elements in the stack are operands of this operation. Operand "operandN" is the topmost element on the stack. All the operands are popped, the operation is performed and then all the results are pushed onto the stack ("result1" first).
| operation | description |
|---|---|
| A B add A+B | addition |
| A B div A/B | division (in real numbers) |
| A B mod C | the result C equals A modulo B |
| A B mul A*B | multiplication |
| A B sub A-B | subtraction |
| operation | description |
|---|---|
| (bottom) any1 ... anyN clear | clears the stack (all elements are popped and discarded) |
| any1 ... anyN N copy any1 ... anyN any1 ... anyN | copy the topmost N elements |
| (bottom) any1 ... anyN count any1 ... anyN N | count elements on the stack |
| any dup any any | duplicate the topmost element |
| any1 any2 exch any2 any1 | exchange topmost two elements |
| anyK ... any1 any0 K index anyK ... any1 any0 anyK | duplicate the Kth element from top (topmost is 0th) |
| any pop | remove the topmost element |
| any1 ... anyN N K roll ??? | described below |
The purpose of the roll operator is to rearrange topmost N elements by rolling (rotating) them K times. We will call the elements "any1 ... anyN" the roll group. Rolling the elements in the positive direction means to take an element from the top of the roll group and to roll it to the bottom of the roll group. Of course rolling in the negative direction is the inverse operation – take an element from the bottom of the roll group and place it on the top.
If K is zero, nothing happens (the result is "any1 ... anyN"). If K is positive, the roll group is rolled in the positive direction K times. If K is negative, the roll group is rolled in the negative direction -K times.
Example. Stack before executing roll: A B C D E F G H 5 2
After executing roll: A B C G H D E F
| operation | description |
|---|---|
| X Y moveto | change the current position |
| (string) show | write the string to the current position using the current font |
| showpage | output the current page, start drawing a new one |
A piece of code is a sequence of operands and operations enclosed in braces. E.g. "{ pop 4 7 add }" is a piece of code. A piece of code is NOT executed immediately, but it is pushed onto the stack as one element. Why could this be necessary? E.g. operation "if" takes two elements from the stack – a boolean value and a piece of code. If the value is true, the code is executed.
A string in PostScript is a sequence of characters enclosed in parentheses. E.g. "(This is a string.)" is a string. The code "(Hello, world!) 200 400 moveto show" prints the string "Hello, world!" somewhere around the middle of a standard A4 page. A number may be converted to a string using the operation "cvs". Its syntax: "number memory cvs string", where "memory" is temporary memory allocated for the string. You may find an example in the hard input file.
An array is a sequence of elements enclosed in brackets. E.g. "[ 4 [ 1 3 ] 7 (Hello world) { pop } ]" is an array containing 5 elements. (a number, an array, a number, a string and a piece of code). You can get a specific element of an array using the operation "get". Its syntax: "array index get element". (Index is from 0 to N-1, where N is the length of the array.) E.g. after executing "[ 4 [ 1 3 ] 7 (Hello world) { pop } ] 3 get" the topmost element of the stack will be the string "(Hello world)".
| operation | description |
|---|---|
| X Y eq bool | "bool" is true if X=Y and false otherwise |
| exit | terminate the execution of the innermost cycle immediately |
| first step last { code } for | "code" is executed repeatedly, details explained below |
| X Y gt bool | "bool" is true if X>Y and false otherwise |
| bool { code } if | "code" is executed if "bool" is true |
| bool { code1 } { code2 } ifelse | "code1" is executed if "bool" is true, "code2" if "bool" is false |
| { code } loop | "code" is executed in an infinite loop |
| X Y lt bool | "bool" is true if X<Y and false otherwise |
| N { code } repeat | "code" is executed N times |
The most complicated loop is the for-loop. During execution of a for-loop, the interpreter maintains a temporary control variable, which is first set to "first". Before each repetition, this variable is compared to "last". If ("step" is positive and the variable is greater than "last") or ("step" is negative and the variable is less than "last"), the loop terminates. Otherwise the current value of the control variable is pushed onto the stack, "code" is executed and the control variable is increased by "step".
Example. The code "0 1 1 100 { add } for" adds the numbers from 1 to 100, also after the execution of this code the topmost element of the stack will be 5050. Executing the code "1 2.5 7 { } for" pushes the numbers 1, 3.5 and 6 onto the stack. Executing the code "1 1 0 { 4 7 add } for" does nothing.
These two different concepts are realized in the same way – using the operation "def". Its syntax: "/keyname value def". Basically this operation tells the interpreter that from now on whenever it encounters "keyname", it means "value". Whenever the interpreter encounters "keyname", it takes a look at "value". If "value" can be executed (it is an operation or a piece of code), it is executed. Otherwise "value" is pushed on the stack.
Example. "/fourtyseven 20 27 add def" (or equivalently "/fortyseven 47 def") defines a variable "fortyseven", containing the number 47. "/mul2 { 2 mul } def" defines a procedure (=operation) "mul2", which multiplies the topmost element of the stack by 2. Now suppose we have an empty stack and execute "fortyseven mul2". Now the stack contains one element – the number 94.