Disclaimer
----------

Cet assombrissement est soumis au nom de Paris.pm canal assombri.

Written by Jean Forget
Ponder.Stibbons@wanadoo.fr

Solution
--------

This program computes the Fibonacci numbers, using regexps.

First, I'll prove that $_ contains only 0's, 1's and 2's, and
that all other digits are there for obfuscation purpose only.

Then, I'll prove that the numbers of 0's and 1's are Fibonacci numbers.

Lastly, I'll explain the result.

1 Which digits?
---------------

We start with a string which looks like "12222221" (with six 2's, because
we want to compute fib(6)).

This string contains substrings belonging to the following set:
"0", "1", "2", "00", "01", "10", "11", "02", "12", "22" and "21".

Of these substrings, only "0", "1", and "21" can match the regexp.
For these three substrings, the formula gives:
    0  -> 10
    1  ->  0
    21 ->  1
The resulting string will therefore contain substrings belonging to
the same set. And the de-obfuscated lines would read:
    while (/1$/){s=(2?[01])=int(abs((67*$1-1467)*$1+1423)/140)=eg}
    y/02//d;

2 How Fibonacci is computed
---------------------------

Theorem: at the end of the i-th iteration, the string contains
           fib(i-1) "1"s
mixed with fib(i) "0"s
      then (n-i) "2"s
      then either a "1" or a "0"

Demonstration: at the start of the program, the string contains a
single "1", n "2"s and another "1". After the first iteration,
the string contains a single "0", (n-1) "2"s and a "1".
That is, the first part of the string contains 0 "1"s (and 
fib(1-1) = 0) and only one "0" (fib(1) = 1).

Suppose this is true for i, we show it remains true for j=i+1.

- In the first part of the resulting  string, all "1"s come 
from the substitution 0 -> 10. There were fib(i) "0"s in the
original string, therefore there are fib(i) = fib(j-1) "1"s in
the resulting string.

- In the first part of the resulting string, all "0"s come
either from the substitution 1 -> 0 (fib(i-1) such substitutions), 
or from 0 ->10 (fib(i) such substitutions). Therefore, in the
resulting string, there are fib(i-1) + fib(i) "0"s, that is
fib(i+1) or fib(j).

- In the second part of the original string, only the last "2"
match the regexp. Actually, this "2" and the last "1" match
"21". Both digits are replaced with a single "1", in effect
deleting this "2". The number n-i becomes n-i-1, that is, n-j.

3 How many iterations?
----------------------
We start with n "2"s. Each iteration removes one "2". So, after
n iterations, we have a string consisting of:
           fib(n-1) "1"s
mixed with fib(n) "0"s
and then   a single "1", no longer prefixed by any "2"s.

After this iteration, the loop condition (end with "1") is still
true. So there is a (n+1)-th iteration, which produces:
           fib(n) "1"s
mixed with fib(n+1) "0"s
and then   a single "0", because of the 1 -> 0 substitution (used for a 
different purpose).

Then, we remove the (fib(n+1)+1) "0"s, with y/02//d, and the last 
string now contains only fib(n) "1"s.

By the way, y/02//d could even be replaced by y/0//d, because there are
no "2"s anymore.

4 Comments
----------
Where did the formula come from?
I needed a formula producing:
    0  -> 10
    1  ->  0
    21 ->  1
I tried a polynom y = a x**2 + b x + c, and I found
    y = (67 x**2 - 1467 x + 1400)/140
or, with the Horner formula
    y = ((67 x - 1467) x + 1400)/140
The problem is, only the three values give an positive integer result, which would be
an indication that these three values are the important ones, and
the other values can be discarded. So I introduced the functions
"abs" and "int". Since I had done that, I could alter a bit the 
polynom, and therefore I changed it to
    y = ((67 x - 1467) x + 1423)/140

Duration of the program.
This program is very inefficient. During the i-th iteration, you have
fib(i-1) substitutions "1 -> 0"
  fib(i) substitutions "0 -> 10" (which extends the string)
   and 1 substitution "21 -> 1".
Therefore, the i-th iteration has fib(i+1)+1 substitutions, that is
0.723 x 1.618 ** i + small quantity.
The total cost is 0.723 x sum(1.618 ** i + small quantities),
that is O(1.618**n). Not very good, but much fun.

