1-D Cellular Automata

[YuckFoo]

Recent discussion of Pascal's triangle reminded me of a cool 1-D Cellular Automata and Wolfram's famous Rule 30.

Try $rule = 18, 22, 30, 45, 54, 110, or 150 for some snazzy Pascal's Triangle variations.

RuleFoo

update: Also rules 122, 126, 129, 146, 151

#!/usr/bin/perl

   use strict;

   my $rule = shift || 30;
   my $wide = shift || 80;
   my $high = shift || 60;

   my $binary = reverse(substr(sprintf("%8.8b", $rule), -8, 8));
   $binary =~ tr/01/ */;
   #print "$binary\n";

   my (%rules, $key, $i);

   for ($i = 7; $i >= 0; $i--) {
      $key = sprintf("%3.3b", $i);
      $key =~ tr/01/ */;
      $rules{$key} = substr($binary, $i, 1);
      #print "$key $rules{$key}\n";
   }

   my ($str, @chs);

   for (1..$wide) {
      if (rand(2) < 1) { $str .= ' '; }
      else             { $str .= '*'; }
   }

   for (1..$high) {
      @chs = split('', $str);
      print "$str\n";
      $str = '';
      for ($i = 0; $i < $wide; $i++) {
         $key = "$chs[$i-1]$chs[$i]$chs[($i+1)%@chs]";
         $str .= $rules{$key};
      }
   }

[gumby]

I was waiting for another one of these posts ;-) Rule 90 will generate Sierpinski's sieve (but then, you can in turn generate that from Pascal's triangle (mod 2)).

  #!/usr/bin/perl -w

  use strict;

  my ($file, %rules, $string, $rewrite, $angle, $i);

  $file = "gosper";
  
  # Peano-Gosper curve.
  $rules{"X"} = "X+YF++YF-FX--FXFX-YF+";
  $rules{"Y"} = "-FX+YFYF++YF+FX--FX-Y";
  $string = "FX"; $angle = 60; $i = 4;

  foreach (1..$i) {
    $rewrite = "";
    for (split //,$string) {
      $rewrite .= $rules{$_} || $_;
    }
    $string = $rewrite;
  }

  open PS,">$file.ps";
  print PS "%#\n\n";
  print PS "306 396 moveto\n";
  for my $ch (split //,$string) {
    if ($ch eq 'f') {
      print PS "0 1 rlineto\n";
    } elsif ($ch eq 'F') {
      print PS "0 1 rmoveto\n";
    } elsif ($ch eq '+') {
      print PS "360 $angle rotate\n";
    } elsif ($ch eq '-') {
      print PS "360 $angle neg rotate\n";
    } elsif ($ch eq '!') {
      print PS "-1 1 scale\n";
    } elsif ($ch eq '[') {
      print PS "gsave\n";
    } elsif ($ch eq ']') {
      print PS "stroke\ngrestore\n";
    }
  }
  print PS "stroke\nshowpage";
  close PS;

Note that you need to replace uppercase F with lowercase f to turn on the 'pen'.

[ferrency]

I like L-systems. A few years ago I wrote an L-system which displayed a Koch snowflake in postscript, for one of the early TPJ obfuscated perl contests, but I don't think it qualified due to the postscript. Maybe I'll post it in the obfuscation section if I can dig it up.

Unfortunately, since then, I haven't found any good turtle-graphics style module to support interesting L-system output. There was (is?) a Graphics::Turtle module (or something similar) in CPAN, but according to the author it was an idea, not an implementation.

However, using postscript for turtle graphics output is pretty easy, if you don't mind using a postscript viewer to look at the output. Instead of rotating your "turtle" and calculating a new (X, Y) based on your angle and a fixed radius, translate your current position to (0, 0), rotate the world around the origin, and then draw a line to (say) (0, 1). Using postscript as my output device, the snowflake generator was under 4 80-character lines long, including unnecessary obfuscation and without any external module dependancies.

I hope this provides some inspiration :) If I don't find my old postscript L-system generator maybe I'll rewrite it and post it here somewhere.

Alan

[gumby]

Thanks, great post. I've changed quite a bit of (cut out a lot of) code (and made some refinements) so I've posted a working version.

[gumby]

Sierpinski sieve:

#!/usr/bin/perl -wl
$_="co";
while (1) { s/..(?=c)/$&^"CO"/eg; s/^/ /; print; }

Now, why does this work? Because binom(m, n)(mod 2) = n XOR m, so this is just Pascal's triangle (mod 2).

Update: Will work now.

[RMGir]

why does this work?

It doesn't, at least, not with 5.6.1, or 5.005_03.

Does it need 5.8?

Edit: As petral points out, the regex will never match. I should have noticed that myself, instead of just trying the code...
--
Mike

[petral]

$_="co" will never match /..(?=c)/.

  p

[punkcraft]

I was playing with this with large values for width and height and found that I could get a 5 fold decrease in runtime by replacing the last for loop with this:

for (1..$high) {
   print "$str\n";

   $prev_str = substr($str, -1, 1) . $str .  substr($str, 0, 1);

   $str = '';

   for ($i = 0; $i < $wide; $i++) {
      $str .= $rules{substr($prev_str, $i, 3 )};
   }
}