Solutions and Discussion for Perl Quiz of the Week #7 (Expert Edition)
Mark Jason Dominus <[email protected]> Wed, 04 Dec 2002 01:16:21 -0500
| Newsgroups | gmane.comp.lang.perl.qotw.quiz-of-the-week |
|---|---|
| Organization | Plover Systems |
| Message-ID | <[email protected]> |
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.