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, some method for specifying the initial vapor density, and whatever else you find useful.