Sample solutions and discussion Perl Expert Quiz of The Week #7 (20021127) 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. ---------------------------------------------------------------- Well, this quiz turned out to be a blast. I was afraid it would sound so complicated that nobody would bother with it, but about twenty highly varied solutions were posted to the -discuss list, and most people said they had fun. *I* certainly had fun, and that's what the list is really about. A few notes before I show the example: 1. Regrettably, I couldn't run all the submitted programs. Many of them used software packages that I don't have and couldn't conveniently install: Program Wanted Why not? ---------------------------------------------------------------- marvell.pl GD Wouldn't compile kennedy3.pl GD Ditto mccarthy.pl Image::Magick Never liked ImageMagick [*] toomey.pl Win32::Console Microsoft is against Plover Systems company policy toren2.pl OpenGL gcc ate all my swap while compiling OpenGL.c wilson.pl Class::Accessor Requires base.pm 1.95 which only comes with 5.8.0 [*] Yes, I realize this is cranky. I'm a cranky guy. In case you hadn't already noticed. 2. I ran all the other programs, sometimes several variations of each, for 120 seconds on a 100x100 grid with 20% randomly distributed vapor and one ice particle, and counted the number of time steps each one was able to complete. Here are the results: What Mode args steps lines (code) allwine.pl Tk "" 20 79 boger.pl dumb "" 36 115 carman.pl dumb "100 100 20" 346* 67 carman2.pl dumb "100 100 20" 315 66 fuglerud.pl dumb "100 100 .2" 92 48 gray.pl dumb/C "1 0.2 100 100" 65 110 haworth.pl dumb "100 100" 211 51 haworth2.pl dumb "100 100" 74 55 hofmann.pl dumb "100 100 .2" 128 51 johnson.pl dumb "100 100 20" 193 49 kennedy.pl dumb "" 34 361 kennedy2.pl Tk "" 13 362 michael.pl dumb "100 100 .2" 177 64 mjd1.pl PPM "100 100 .2" 164 93 mjd1d.pl dumb "100 100 .2" 162 94 mjd2.pl GIF "1000000000" 146 137 sainio.pl PNG "" 46 120 sainio2.pl dumb "" 126 120 sanderson.pl dumb ".2 100 100" 154 86 stander.pl Tk "-t 1" 43 188 toren.pl curses "100 100 20" 32 100 I did not order these by speed or size; that would be comparing apples and oranges in too many cases. All these programs are available at http://perl.plover.com/qotw/misc/e007/ except the ones I couldn't run, which are at http://perl.plover.com/qotw/misc/e007/CANTRUN/ You may enjoy the CANTRUN programs if you have the software to run them, because they tended to produce fancier output than the others. 3. To do this, I modified everyone's program to die after a time limit, specified by $ENV{TIMELIMIT}, and to print out the total number of ticks elapsed at the end. I recommend this fascinating exercise to anyone who wants to become a maintenance programmer, or any maintenance programmer who wants to become a better maintenance programmer. 4. Some sub-notes about the testing process: 1. The command line arguments aren't always exactly the same as the program the author sent to the list. I sometimes hacked them for my own convenience. For example, when there was a required command-line argument to say how long to run the simulation, I hacked it to default to 1_000_000_000. Sometimes the program was hardwired to use a grid of a certain size; in such cases I hacked them to use a 100x100 grid. The versions of the programs that I tested are at http://perl.plover.com/qotw/misc/e007/ 2. gray.pl, kennedy.pl, kennedy2.pl, johnson.pl, michael.pl, and sanderson.pl had sleep delays built in. I commented these out. 3. mjd2.pl uses a configuration file to define the initial board setup. The configuration I used was new 100 100 random 0.2 . cell 50 50 * 4. hofmann.pl and fuglerud.pl didn't output a display at each step; they did the simulation internally, and emitted only the final result. I modified their main loops to draw the grid after every step. It would be interesting to rerun all the tests with output disabled, to compare the simulation speeds independent of display processing. Unfortunately, I'm out of time. 5. stander.pl updates the display every 10 ticks by default; I used the -t option to update the display after every tick. Looking at the table above, carman2.pl, by Michael Carman, seems to be best-of-breed for plain-text outputs, since it's by far the fastest, and also not too big. So that's the one I'll show. ** Overview 'create_volume' initializes the main data structure that represents the current state of the world. 'frost' is the main loop, and iterates the 'cycle' function until all the vapor has frozen. 'cycle' partitions the world into Margolus neighborhoods, and calls 'process' on each one to update the contents of the neighborhood. 'text' is called periodically to dump out a plain-text version of the world. 'process' tells 'cycle' if anything has changed in the current neighborhood, and 'cycle' tells 'frost' if anything has changed anywhere at all. 'frost' terminates execution if nothing has changed. ** Details 'create_volume' initializes the data structure that represents the world. (One of the Tk submitters called this the 'window', and the pun was so apt I'm going to adopt it from now on: the frost is growing in a 'window'.) The window data structure is a straightforward two-dimensional array of strings; each string represents the contents of one cell, and contains exactly one of the following characters: represents denoted by (space) vacuum EMPTY . vapor VAPOR * ice ICE Since the representation of the window is simple, 'text', which transforms the window into a single string which can be printed, is trivial. Mr. Carman uses $" and "@$_" to implicitly join together the elements in each row of the window. 'process' is the inner loop of the simulation. It gets four arguments, which are the four cells of a neighborhood: A B C D It then modifies these arguments *in place*. Since the @_ elements are aliases for the actual arguments, and the actual arguments are four cells of the window, modifying the contents of @_ modifies the window directly. This is an unusual and rarely used feature of Perl that Carman has put to good use here; it probably accounts for a lot of the speed of the program. 'process' will also return a true value if the resulting neighborhood might change in the future, and false if not. 'process' first counts up the total number of vapor and ice particles in the neighborhood. If there is no vapor, then the neighborhood cannot possibly change and 'process' returns 0 immediately. Because no modification is necessary, and the arguments are to be modified in place, nothing else needs to be returned or computed. If the neighborhood *does* contain vapor, there are two cases: ice and no ice. In both cases the new neighborhood contents are computed and assigned back to the @_ array, which, since they're aliases for window cells, updates the contents of the window. One fine point here is that the assignments back to @_ look like this: @_[0 .. 3] = @_[1, 3, 0, 2]; (counterclockwise rotation of vapor). Since @_ has 4 elements, it might seem simpler to use @_ = @_[1, 3, 0, 2]; But this doesn't work. It clobbers the old contents of @_, which were the aliases, and replaces them with the new values without modifying the window. 'cycle' divides the window into neighborhoods and calls 'process' on each neighborhood. On even ticks, the division and call are simple and straightforward: for (my $x = 0; $x < $m; $x += 2) { for (my $y = 0; $y < $n; $y += 2) { $v = process($data->[ $x ][$y], $data->[ $x ][$y+1], $data->[$x+1][$y], $data->[$x+1][$y+1]) || $v; } The only possibly tricky thing here is $v, which records whether *any* neighborhood might change in the future. Initially it's 0, and it's set to 1 by this expression as soon as any process() call returns 1. 'cycle' returns $v back to the main loop in 'frost', which terminates the program if $v is 0. The loop for odd ticks is a little trickier, because some of the neighborhoods overlap the boundaries of the window. To keep the main part of the loop as simple as possible, and therefore as fast as possible, the program deals with the boundary neighborhoods before the others. The first thing it does is handle the special corner neighborhood, here marked with 1's: 1| | |1 -+--+--+- | | | | | | -+--+--+- 1| | |1 The code is simply: $v = process($data->[-1][-1], $data->[-1][0], $data->[ 0][-1], $data->[ 0][0]); Here the program uses the special [-1] subscript to indicate the last element of an array. Then it deals with the neighborhoods down the vertical seam: | | | -+--+--+- 2| | |2 2| | |2 -+--+--+- | | | for (my $y = 1; $y < $n - 2; $y += 2) { $v = process($data->[-1][$y], $data->[-1][$y+1], $data->[ 0][$y], $data->[ 0][$y+1]) || $v; } Then the horizontal seam: |33|33| -+--+--+- | | | | | | -+--+--+- |33|33| for (my $x = 1; $x < $m - 2; $x += 2) { $v = process($data->[$x][-1], $data->[$x+1][-1], $data->[$x][ 0], $data->[$x+1][ 0]) || $v; } Finally, having done this, it's ready to do the bulk of the work; most of the neighborhoods are in the middle. (In a 100x100 grid, there is one corner neighborhood, 98 seam neighborhoods, and 2,401 middle neighborhoods.) | | | -+--+--+- |44|44| |44|44| -+--+--+- | | | Because the code has already updated all the peculiar edge cases, it doesn't have to worry about overflow or wraparound in the indices; the loop is completely straightforward: for (my $x = 1; $x < $m - 2; $x += 2) { for (my $y = 1; $y < $n - 2; $y += 2) { $v = process($data->[ $x ][$y], $data->[ $x ][$y+1], $data->[$x+1][$y], $data->[$x+1][$y+1]) || $v; } } This saves time. After calling 'process' on every neighborhood, 'cycle' returns $v back to the main loop in 'frost' to indicate whether it's time to stop. The main control in 'frost' is also simple. It's essentially just while (cycle()) { print text(); } with some embellishments. The program uses an interesting trick to clear the screen: It runs the 'clear' command ('cls' command on Win 32 systems) inside of backticks, and records the output in a scalar variable; then when it wants to clear the screen, it just prints the contents of this variable: my $cs = ($^O eq 'MSWin32') ? `cls` : `clear`; ... print $cs, text(@vol); This is a lot faster than repeatedly calling the external 'clear' command. It works as long as 'clear' operates by printing some special character sequence to the terminal; if it makes a weird operating system call or something else not output-related, it won't work. I used to use this trick a lot, but for this program I dumped the 'clear' output into a file, examined it, and then hardwired the magic control sequence into my program. The approach in carman2.pl seems preferable to me, since mine doesn't work if the program is run on a terminal incompatible with the terminal on which I wrote the program. Here's the complete code, which is also available at http://perl.plover.com/qotw/misc/e007/carman2.pl ------ CODE STARTS HERE #!/usr/bin/perl # # This was a fun quiz. :) I haven't been motivated to generate images for # output, so this just barfs out some high-quality ASCII art. Still, it's # kind of fun to watch the frost "grow" across my screen. # use warnings; use strict; use constant EMPTY => ' '; use constant VAPOR => '.'; use constant ICE => '*'; my $t = 0; frost(create_volume(@ARGV)); # create a volume of size M x N with vapor density D # and a single ice particle in the center sub create_volume { my ($m, $n, $d) = (@_, 60, 40, 20); die "\$m must be even\n" if $m % 2; die "\$n must be even\n" if $n % 2; my @vol; for (1 .. $m) { push @vol, [ map {rand(100) < $d ? VAPOR : EMPTY} (1 .. $n) ]; } $vol[$m/2][$n/2] = ICE; return @vol; } # run frost simulation until all vapor freezes, # displaying volume each cycle. sub frost { my @vol = @_; my ($m, $n) = (scalar @vol, scalar @{$vol[0]}); my $cs = ($^O eq 'MSWin32') ? `cls` : `clear`; print $cs, text(@vol); print "t = $t\n"; while (cycle($t++, $m, $n, \@vol)) { print $cs, text(@vol); print "t = $t\n"; } print $cs, text(@vol); print "Finshed at t = $t\n"; } # run a single cycle of frost simulation sub cycle { my ($t, $m, $n, $data) = @_; my $v; # has vapor remaining if ($t % 2) { # boundary conditions -- do these seperately to keep # the checks out of the main loop # Corner $v = process($data->[-1][-1], $data->[-1][0], $data->[ 0][-1], $data->[ 0][0]); # vertical seam for (my $y = 1; $y < $n - 2; $y += 2) { $v = process($data->[-1][$y], $data->[-1][$y+1], $data->[ 0][$y], $data->[ 0][$y+1]) || $v; } # horizontal seam for (my $x = 1; $x < $m - 2; $x += 2) { $v = process($data->[$x][-1], $data->[$x+1][-1], $data->[$x][ 0], $data->[$x+1][ 0]) || $v; } # center for (my $x = 1; $x < $m - 2; $x += 2) { for (my $y = 1; $y < $n - 2; $y += 2) { $v = process($data->[ $x ][$y], $data->[ $x ][$y+1], $data->[$x+1][$y], $data->[$x+1][$y+1]) || $v; } } } else { for (my $x = 0; $x < $m; $x += 2) { for (my $y = 0; $y < $n; $y += 2) { $v = process($data->[ $x ][$y], $data->[ $x ][$y+1], $data->[$x+1][$y], $data->[$x+1][$y+1]) || $v; } } } return $v; } # process a neigborhood sub process { my ($vapor, $ice); foreach (@_) { $vapor++ if $_ eq VAPOR; $ice++ if $_ eq ICE; } # short-circuit if nothing to do. # faster, but it makes the output jumpy on my system. # things may look smoother without it. return 0 unless $vapor; if ($ice) { # freeze vapor @_[0..3] = map {$_ eq VAPOR ? ICE : $_} @_; } else { # randomly rotate vapor if (int rand(2)) { @_[0 .. 3] = @_[1, 3, 0, 2]; } else { @_[0 .. 3] = @_[2, 0, 3, 1]; } } return $ice ? 0 : $vapor; } # display volume as text sub text { my $t = ''; local $" = ''; foreach (@_) { $t .= "@$_\n"; } return $t; } ------ AND ENDS HERE More notes: 5. carman2.pl is not exactly the program submitted by Michael Carman; his program, carman.pl, had a couple of bugs, which I fixed. If you look at the summary table above, you'll see that carman.pl appears to be lightning fast, even faster than carman2.pl, but that's because it had a serious bug---the vapor particles in carman2.pl love moving horizontally, and they do it too much. This effect is quite evident if you're looking for it, and perhaps even if you're not. I wasn't looking for it, but it jumped out at me as I watched the output, because the resulting crystal was so bizarre-looking. Also, all the vapor disappeared from the middle rows of the grid while the top and bottom were still very humid. Then I ran a small test with just a few vapor particles and watched them move left and right. As a result of this misbehavior, the crystal grows way too fast, and once the vapor is all frozen, the simulation really screams, because of the short-circuit in 'process'. Here's the reason why this happened. The code the original program used to 'rotate' the neighborhoods was: if (int rand(2)) { unshift @cells, pop @cells; } else { push @cells, shift @cells; } If the neighborhood had > V ^ < then @cells has (> V ^ <). Notice that "unshift @cells, pop @cells" produces (< > V ^), which means < > V ^ and similarly "push @cells, shift @cells" produces (V ^ < >), which is V ^ < > Notice that at each stage, *every* vapor particle moves horizontally, and half of them move vertically. carman2.pl corrects this: if (int rand(2)) { @_[0 .. 3] = @_[1, 3, 0, 2]; } else { @_[0 .. 3] = @_[2, 0, 3, 1]; } While making this correction, I also eliminated the @cells array, which was superfluous. There was no need to copy the data to an auxiliary array and back again, and skipping the extra copies saved time. 6. carman.pl also had another bug: it never updated the neighborhoods along the vertical seam; the loop for doing that was entirely missing. I scratched my head over this for a while, and eventually instrumented the 'process' function to replace all cells with 'X'es at all the odd time steps. Then I ran the simulation on a small window, and sure enough, the output turned into this: XXXXXX XXXX XXXX XXXXXX Adding this slowed down the program a little bit, of course, but I was able to get the speed back by trimming some code in 'process' (where it really counts). 7. Several people remarked that they were envious of the folks who had written programs to generate graphical output. My programs generated graphical output rapidly, and I think the approach is worth discussing because it's extremely simple. About ten years ago, Jef Poskanzer invented the PPM graphics format. PPM is pretty much the simplest possible 24-bit graphics format. Because it's so simple, it's easy to write programs that read or write files in that format, and as a result everyone does. If you have tool X that wants files in format X, and tool Y that wants files in format Y, you may not have a program to convert format X to format Y. But it's easy to get (or write) a program to convert X to PPM and PPM to Y, because PPM is so extremely trivial. The PPM distribution comes with some C libraries for generating PPM files, and also with several dozen programs that convert PPM from and to other formats and that transform PPM images in various ways. Here's the PPM format: The file begins with 'P3' and then one or more whitespace characters. Then follow three numerals, sequences of ASCII digits, separate by whitespace. The first is the width, W, in pixels. The second is the height, H, in pixels. And the third is the maximum color level, C, a number from 1 to 255. There then follow 3*W*H numerals, each between 0 and C, separated from the others by white space. The first three numerals are the red, green, and blue levels for the upper-leftmost pixel; the next three are the red, green, and blue of the pixel to its right, and so on. "0 0 0" denotes black. If C is 255, then "255 255 255" denotes white. "255 0 0" is red. It's that simple. There is one other thing to know about PPM format: If the file begins with "P6" instead of "P3", then the red, green, and blue values are expressed as single characters, instead of as whitespace separated ASCII numerals. Black becomes "\0\0\0". White becomes "\xFF\xFF\xFF". Red is "\xFF\x00\x00". mjd1.pl emits a snapshot of each tick as a PPM file. It represents the window as an array of strings, one for each row of cells; each string contains one character for each cell, either a space, a ".", or a "*". Its function 'show' prints out a PPM file; you call it like this: open PPMFILE, ">", "snapshot.ppm" or die...; $Window->show(\*PPMFILE); close PPMFILE; Here's a slightly modified version of the code: sub show { my $S = shift; my $fh = shift; print $fh "P6\n", join(" ", $S->size, 255), "\n"; for (@{$S->{B}}) { my $s = $_; $s =~ s/ /\x0\x0\x0/g; # black $s =~ s/\./\x0\x0\xff/g; # blue $s =~ s/\*/\x0\xff\x0/g; # green print $fh $s; } } The first 'print' emits the 'P6', the width and height, and the 255 which is the maximum color level. Then for each row of pixels, it converts spaces to black, dots to blue, stars to green, and prints the result. Voila, instant PPM file. Now suppose you want the output as a JPEG instead of as a PPM. No problem. If you get the 'libjpeg' reference implementation of the JPEG standard, it comes with a program called 'cjpeg', which converts its input to a JPEG---and guess what format the input is required to be in? How convenient. If you want JPEG output, then you make a tiny change to the 'show' call: open JPEGFILE, "| cjpeg > snapshot.jpg" or die...; $Window->show(\*JPEGFILE); close JPEGFILE; Done, and much easier than programming GD or Imager or ImageMagick or almost anything else. 'cjpeg' is written in C, and it's fast. Multiple formats are supported. Would you like the output in PCL, suitable for sending directly to your HP printer? open JPEGFILE, "| ppmtolj > /dev/lp0" or die...; More people need to be aware of this approach, because it's just so easy. mjd2.pl is a more complete demonstration. 8. Several people posted links to their frost pictures. Here are some: Dan Boger: http://www.vraal.com/dan/7e/7e.0.png http://www.vraal.com/dan/7e/7e.500.png http://www.vraal.com/dan/7e/7e.1000.png http://www.vraal.com/dan/7e/7e.2000.png http://www.vraal.com/dan/7e/7e.End.png Animated GIFs I made of various experiments: http://perl.plover.com/qotw/misc/e007/movies/ Garth Sainio: http://www.sainio.org/qotw/7/ Steve Lane: http://www.usually.com/frost/frost2.html http://www.usually.com/frost/frost3.html http://www.usually.com/frost/frost5.html http://www.usually.com/frost/frost7.html http://www.usually.com/frost/frost8.html http://www.usually.com/frost/frost9.html http://www.usually.com/frost/frost10.html Jamie McCarthy: http://lvalue.com/qotw7/smalltest.mpeg http://lvalue.com/qotw7/bigtest.mpeg http://lvalue.com/qotw7/circle200.mpeg http://lvalue.com/qotw7/bigtest300.html Steve Marvell: http://www.fysh.org/~steve/frost.gif My apologies if I omitted anyone's pictures. 9. For some crazy reason, I got a big kick out of the following line in Tim Allwine's program: while($vapors) { 10. Dan Schmidt suggested that it might be faster to use a simple lookup table for the rule evaluation, rather than making a bunch of decisions based on the neighborhood values. But Jamie McCarthy and I both tried that and couldn't get it to go any faster. See: http://perl.plover.com/~alias/list.cgi?1:msp:912 and the ensuing messages in the thread. The program at http://perl.plover.com/qotw/misc/e007/mjd1f.pl is an attempt to speed up the program by memoizing the rule function. One odd piece of trivia that came out of this: In a typical simulation, only about 62 of the 81 possible neighborhood states ever appeared. 11. Maybe it's just my imagination, but after watching a few dozen simulations, I got the distinct impression that the growing frost crystal is surrounded by a region of lower-than-average vapor density. As an example, a small screenshot of one of the plain-text outputs of Garth Sainio's program is available at http://perl.plover.com/qotw/misc/e007/vacuum.jpg the frost is at the right, and the white ring around it is clearly visible, particularly if you stand back a few paces. Perhaps someone would be interested enough in this to study it a little more and figure out where it comes from and how big it is. 12. I like the frost simulator because it's an example of cellular automaton modeling that is both accessible and also apparently useful. The most well-known cellular automaton rules, are of course the game of Life, invented by J. H. Conway. But although Life is fascinating, it can also be unsatisfying: while it's quite clear that it's doing *something*, it's hard to say exactly what. The frost simulation incorporates a gas diffusion simulation, and it looks like just what it is. (See my animated gifs (URLs above) for examples of this.) Fluid flow simulation is tricky because it requires a hexagonal grid; on a square grid you get fluid flow that prefers to move in the cardinal directions, so I am told. Compressible gases (like the vapor in this example) can apparently be simulated on a square grid without any large-scale effects that indicate the underlying preference for certain directions. (My movies demonstrate this also.) I don't know why this is. The Margolus neighborhood technique is one that's worth remembering if you are interested in cellular automata generally, because it makes it easy to conserve the number of particles in a simulation that uses particles. This property is essential when modeling any physical phenomenon in which conservation of mass or energy is an issue. Conservation is extremely difficult to obtain with conventional nearest-neighbor techniques like those used in Life. Thanks to everyone who participated this week. QOTW will be on hiatus next week, so the next quiz will be along on 11 December. I will send an admin message in a few minutes that explains this.