We will solve the easy input first.
(o) (a) (e) (t) (c) (c) (r) (_)
(_) (t) (_) (e) (n) (w) (_) (r)
(o) (e) (s) (i) (h) (u) (e) (c)
(d) (i) (r) (c) (i) (s) (r) (e)
1608168553 {
32 -3 roll
exch
2 index
32 3 roll
pop
17 5 roll
3 copy
7 2 roll
3 { pop } repeat
-5 24 4 add exch roll
30 2 roll
15 5 roll exch 15 -4 roll
dup 9 1 roll pop 6 index
8 -1 roll pop
20 -5 roll 5 -1 roll exch 5 1 roll 20 5 roll
} repeat
1 1 32 { 15 mul 550 exch sub 800 moveto show } for
showpage
This piece of code is pretty much straightforward. First we push some letters onto the stack, then we do an awful lot of operations with the stack and at the end we print the top 32 letters of the stack. (Note that the letters are printed from right to left.) The only problem: how does the middle part of code alter the stack? The easiest way to discover this is to modify the code and see what happens.
Instead of the original letters we push some unique strings (e.g. (1), (2), etc.) onto the stack. We won't run the cycle 1608168553 times, just once. After viewing the modified PostScript file we notice that the middle part of code is just a fixed permutation of the stack.
We want to determine the result after applying this permutation 1608168553 times. After we know the permutation, this can be done by hand. It suffices to split the permutation into disjoint cycles. Now we may rotate each of the cycles 1608168553 times (or equivalently (1608168553 modulo its length) times). An even more lazy solution is to use the following straightforward lemma:
Let P be a permutation, consisting of cycles with lengths l1, ..., lk. Then LCM(l1, ..., lk) times applied P is the identity. (LCM means "least common multiple".)
In our case the cycle lengths are 1, 5, 8 and 18. Their least common multiple is 360. Therefore applying the permutation 1608168553 times is equivalent to applying it only (1608168553 modulo 360) = 313 times. Now all we have to do is to take the original input file, replace 1608168553 by 313 and open the file in a PostScript viewer.
The hard input will be a bit more complicated. We define some variables, a procedure, an array and write some code. The first part of the code follows.
/last 0 def
{ /wherex 50 def /wherey 780 def 1200 {
rand 2147483648 div /foo exch def
/goo 0 def
/next 0 def
wherex wherey moveto
{
goo foo lt {
goo prob last 27 mul next add get add /goo exch def
next 1 add /next exch def
} {
exit
} ifelse
} loop
upperbound 3 163 409 mul mul lt { upperbound 1 add /upperbound exch def } if
next 1 sub dup /last exch def
dup 0 gt { 9 add 36 tmpstring cvrs } { pop ( ) } ifelse
dup stringwidth exch wherex add 2 add /wherex exch def
wherex 500 gt
{ /wherex 50 def wherey exch sub 20 sub /wherey exch def }
{ pop }
ifelse
show
} repeat showpage } loop
Note the last line of the code -- this part is an infinite loop. By deleting it we may find out that this is the part generating the random words. Just for the record, the array prob is a Markov transition matrix. Basically the matrix contains the probabilities Pr(next letter is X | this letter was Y). The code generates the words using this transition matrix. However, we are not interested in the words, also we may delete this part of code. Well, almost. There is one interesting line hidden in the middle:
upperbound 3 163 409 mul mul lt { upperbound 1 add /upperbound exch def } if
What does this line do? Take the current value of upperbound. Compare it with 3*163*409 = 200001. If it is less, increase upperbound by 1. Clearly after the awful lot of words is generated and the infinite loop finishes ;-) (well, already after after approx. 170 pages) upperbound will assume the value 200001 and stop changing.
Now let's concentrate on the last part of the input file.
/j 1 def
/k 0 def
upperbound {
j 1 add /number exch def
j trick1 j add number mod
j eq { k j add /k exch def } if
j 1 add /j exch def
} repeat
k 50 750 moveto tmpstring cvs show
showpage
We already know that this piece of code is repeated 200001 times. We may rewrite it into pseudo-C-code as follows: (From the syntax we assume that the procedure trick1 takes the top of the stack as an argument and replaces it with its output. Later we will show that trick1 really behaves in this way.)
j=1; k=0; upperbound=200001;
while (upperbound--) {
number=j+1;
if ( ((trick1(j)+j)%number) == j ) k+=j;
j++;
}
print(k);
This code looks pretty simple. If only we knew, what does trick1 compute, we would be almost done. So let's take a look at the procedure.
/trick1 {
/i exch def
i 1 gt
{
i {
i dup -1 add
trick1
exch /i exch def
} repeat
i -1 add { add } repeat
i i mul add i sub i sub
number mod
}
{ 0 }
ifelse
} def
On the first line the procedure takes the top of the stack and stores it in the variable i. If i<=1, trick1 pushes 0 onto the stack and returns. The other case is more complicated. First of all, look at this part:
i dup -1 add trick1 exch /i exch def
First line: i is pushed, i-1 is pushed. Second line: we call trick1 recursively. The value i-1 is replaced by trick1(i-1). Third line: Calling trick1 in the previous line probably destroyed the contents of the variable i. Therefore we stored it on the stack before calling the procedure. Now we restore the original value of i. The value trick1(i-1) remains on the stack.
The above code is repeated i times. Now we have i copies of the value trick1(i-1) on the top of the stack. In the next line we add them together. In the following lines we add i2-2i to this value and compute the remainder after dividing it by number.
Let's forget for a while that we compute the values of trick1 modulo number. We now know a simple recurrence equation for the values returned by trick1: trick1(1)=0, trick1(n)=n.trick1(n-1)+n2-2n for n>1. This equation can be solved using standard methods (consult e.g. the book Graham, Knuth, Patashnik: Concrete Mathematics if you are unfamiliar with this type of equations). The easiest method in this case is to guess the solution. The first values are 0, 0, 3, 20, 115, 714, 5033, ... We may notice that trick1(n) is approximately n!. The first values of trick1(n)-n! are -1, -2, -3, -4, -5, -6, ... and we won. The result is trick1(n)=n!-n. In fact, the real result is trick1(n)=(n!-n) mod number.
The last step awaits us. Back to the piece of our pseudo-C-code. We may rewrite it using the above result. Also note that trick1 does not change the value of number, therefore also after calling trick1 the value j+1 is stored in number.
j=1; k=0; upperbound=200001;
while (upperbound--) {
if ( ( (j!)%(j+1) ) == j ) k+=j;
j++;
}
print(k);
The code computes the sum of those values j from the set {1,2,...,200001} for which the complicated condition holds. Let's take a look at the condition. It is true iff j! gives the remainder j (or equivalently -1) modulo j+1. Those of you with some mathematical background probably know this condition under the name Wilson's lemma.
Lemma (Wilson). The number p is prime iff (p-1)! is congruent to -1 modulo p.
Also we add together all those values j for which j+1 is prime. In other words, the result is (sum of primes in {1,2,...,200001}) - (count of primes in {1,2,...,200001}). Note that the knowledge of Wilson's lemma was not necessary. You could compute (either by hand or by modifying the code) the first few values of j for which the condition holds and guess the result.
If you liked this problem and you are now interested in PostScript, we may recommend some literature to you. First of all, there is the PostScript Language Reference (and several other documents), which can be downloaded at the Adobe website.
You may find the First Guide to PostScript useful. Also you may download and take a look at one of the following books: Byram-Wigfield: Practical PostScript, Reid: Thinking in PostScript.
If you are fluent in Czech language, we recommend reading the project Vladimir Michl: PostScript. This document concentrates on one of the most powerful uses of PostScript -- drawing simple graphics. In fact, PostScript may often be the best possibility if you need to add a simple graphical output to your application!