Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit


IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra
        cosa que pueda echar a perder la resolución del problema hasta
        que hayan pasado por lo menos 60 horas desde el envío de este
        mensaje. Gracias.

IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la
        date de ce message avant de poster solutions, indices ou autres
        révélations. Merci.

WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für
        diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser
        Mail. Danke.

BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de
        eerste 60 uur na het verzendingstijdstip van dit
        bericht. Waarvoor dank.

Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
        Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
        Xie4Lou4 Da2An4 De5 Jian4Yi4.  Xie4Xie4.

----------------------------------------------------------------

You will write a simulation of frost.

The frost simulation takes place in an M-by-N square grid of cells.  N
and M are both even.  The top and bottom edges of the grid are
connected, as are the left and right edges, so that the grid actually
represents a torus.

Each cell may contain vacuum, a vapor particle, or an ice particle.
Initially, there is one ice particle. in the middle of the grid, and
the rest of the cells are filled with a random distribution of vacuum
and vapor.

Time is discrete, measured in 'ticks', by a counter.  At each time
step, the grid is divided into "Margolus neighborhoods", which are 2x2
blocks of adjacent cells.  If a neighborhood contains an ice particle
at time T, then all the vapor cells in the same neighborhood change to
ice at time T+1.  If a neighborhood contains only vapor and vacuum at
time T, then its contents rotate a quarter turn clockwise or
counterclockwise, at random, at time T+1.

For example, using ' ' to indicate vacuum, '.' to indicate vapor, and
'*' to indicate ice:

        +--+                +--+
        |.*|       ==>      |**|
        | .|                | *|
        +--+                +--+

        +--+                +--+
        | .|       ==>      | *|
        |* |                |* |
        +--+                +--+

        +--+                +--+      +--+
        | .|       ==>      |..|  or  |  |  (50% chance either way)
        | .|                |  |      |..|
        +--+                +--+      +--+

        +--+                +--+      +--+
        |. |       ==>      | .|  or  |  |  (50% chance either way)
        |  |                |  |      |. |
        +--+                +--+      +--+

        +--+                +--+
        |**|      ==>       |**|
        |  |                |  |
        +--+                +--+

        +--+                +--+
        |  |      ==>       |  |
        |  |                |  |
        +--+                +--+


The division of the grid into neighborhoods changes from tick to tick.
(If the neighborhoods were always the same, the vapor particles would
be confined to one neighborhood for their entire lifetime, which is
not realistic.)  Suppose for concreteness that the grid is 4x6.  On
even-numbered ticks, cell (0,0) will be in the upper-left corner of
its neighborhood, which implies that the grid is divided into
neighborhoods like this:

        +--+--+--+
        |  |  |  |
        |  |  |  |
        +--+--+--+
        |  |  |  |
        |  |  |  |
        +--+--+--+

On odd-numbered ticks, cell (0,0) will be in the lower right corner of
its neighborhood, which divides the grid into neighborhoods like this:

         |  |  | 
        -+--+--+-
         |  |  | 
         |  |  | 
        -+--+--+-
         |  |  | 

(Remember that the edges of the grid wrap around, so there are still
six neighborhoods here:

        1|22|33|1
        -+--+--+-
        4|55|66|4
        4|55|66|4
        -+--+--+-
        1|22|33|1
)

Consider what might happen to a single vapor particle:


T=0:
        +--+--+--+
        |. |  |  |
        |  |  |  |
        +--+--+--+
        |  |  |  |
        |  |  |  |
        +--+--+--+

Let's say that the neighborhood around the particle happens to rotate
clockwise, yielding:

T=1:
         |. |  | 
        -+--+--+-
         |  |  | 
         |  |  | 
        -+--+--+-
         |  |  | 


Suppose the new neighborhood turns clockwise:

T=2:
        +--+--+--+
        |  |  |  |
        |  |  |  |
        +--+--+--+
        |  |  |  |
        | .|  |  |
        +--+--+--+

Suppose the new neighborhood turns counterclockwise:

T=3:
         |  |  | 
        -+--+--+-
         |  |  | 
         |. |  | 
        -+--+--+-
         |  |  | 

Suppose the new neighborhood turns counterclockwise:


T=4:
        +--+--+--+
        |  |  |  |
        |  |  |  |
        +--+--+--+
        |  |. |  |
        |  |  |  |
        +--+--+--+

As you can see, using these rules, vapor particles can wander freely,
but the total number of vapor particles is always conserved.  If a
grid starts out with a high vapor density in one place and a low
density elsewhere, the densities will soon equalize.

        +--+--+--+        +--+--+--+
        |  |  |  |        |. |. | .|
        |  |  |  |        |. |. |. |
        +--+--+--+  ==>   +--+--+--+
        |..|..|..|        |. |  |. |
        |..|..|..|        |..|. |  |
        +--+--+--+        +--+--+--+


Your program should have some method for graphic display of the grid
contents at each step, and some method for specifying the initial
vapor density.