--------------enig98EF0C3220500747A59F0A5A
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: quoted-printable

Hi!

* Ruby Quiz, 09.03.2007 13:58:
> The goal is to create a simulation of frost.

My aim was not to solve the task in a very object-oriened way or to
have a shiny output. My major objectives were

 * Writing a Ruby program that can easily be ported to C, porting it
   and then compare the performance. It turned out that the C
   implementation is faster by a factor of about 100.

 * Finding a simple way of animating the produced data without
   having to implement a GUI.

For the implementation see source below, let's turn to animation:

I use numbered PGM files as output format. For tick 0 (initial state
tick_00000.pgm is written, for tick 1 tick_00001.pgm and so forth.
For large simulations - I ran a C 1280x1024 C simulation with 25%
vapor that took about 7 minutes (with the bottleneck being the
Journaling File System) that took 3472 ticks meaning 3473 output
frames - it can be a good idea not to display all of the frames but
only every 10th or so. This goal can easily achieved by not looking
at all frames but only at those matching "tick_*0.pgm". For every
20th one could use "tick_*[02468]*.pgm" and so on.

One way of animating the output is using "convert" to create an
animated gif in the following manner:

convert -delay 0 -loop 0 tick_*.pgm simfrost.gif

Beware that this can require quite a lot of RAM!

A less demanding way of animtin the output is using an appropriate
display program. Personally I perfer qiv. To use this program to
animate the output all one has to do is issue

qiv -s -d 0 tick_*pgm

Where '-s' orders qiv to display the images as a slideshow and '-d'
provides a delay in seconds between the individual images, for I was
using the program for 1280x1024 images I set this delay to 0.

qiv is available at http://www.klografx.net/qiv/

The second major advantage of using PGM or PBM or PGM besides the
simplicity of output is that they can be converted to virtually any
other graphics format because they are the generic formats used by
the netpbm tools, see http://netpbm.sourceforge.net/

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Follows Ruby implementation
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#!/usr/bin/ruby -w

#####################################################################
# Ruby Quiz 117, SimFrost
#
# The simulation uses an array of integers.
#
# It seems to make sense to use
#
# 0 to represent vacuum
# 1 to represent vapor
# 2 to represent ice
#
# Note that your terminal emulation should support ANSI escape
# sequences
#
#####################################################################

#####################################################################
# Integer#even - see if Integer is even
#####################################################################

class Integer
  def even?
    self/2*2 == self
  end
end

#####################################################################
# cls - clear screen
#####################################################################

def cls
  print "\e[2J"
end

#####################################################################
# home - move cursor to home position
#####################################################################

def home
  print "\e[1;1H"
end

#####################################################################
# Get even positive number
#####################################################################

def get_even_positive(desc)
  n = 0
  until n > 0 && n.even?
    print "Please enter #{desc} (must be even and positive): "
    n = gets.to_i
  end
  return n
end

#####################################################################
#
# Read probability
#
# Input is probability in percent, return value is probability
#
#####################################################################

def get_probability(desc)
  p = -1.0
  while p < 0.0 or p > 100.0
    print "Please enter probability for #{desc} (in %, float): "
    p = gets.to_f
  end
  return p / 100.0
end

#####################################################################
#
# Read settings
#
#####################################################################

def get_settings
  okay = "no"
  while okay != "yes"
    cls
    cols = get_even_positive("number of columns")
    rows = get_even_positive("number of rows")
    prob = get_probability("vapor")
    puts <<-EOF
You want:
\t#{cols}\tcolums
\t#{rows}\trows
\t#{prob*100.0}\tas the initial probabilty for vapor in percent
IS THAT CORRECT? If so please answer with: yes
    EOF
    okay = gets.chomp
    puts "Please re-enter data." unless okay == "yes"
  end
  return { "cols" => cols, "rows" => rows, "prob" => prob }
end

#####################################################################
#
# generate initial state for simulation
#
#####################################################################

def initial_state(cols, rows, prob)
  a =
  Array.new(rows) do |row|
    Array.new(cols) do |elem|
      rand < prob ? 1 : 0
    end
  end
  a[rows/2][cols/2] = 2
  return a
end

#####################################################################
#
# output current simulation state
#
#####################################################################

def output_state(state, tick)
  home
  puts "Simulation tick #{tick}"
  filename = "tick_#{'%05d' % tick}.pgm"
  File.open(filename, 'w') do |file|
    file.puts <<-EOF
P2
# #{filename}
#{state.first.length} #{state.length}
2
    EOF
    state.each do |row|
      row.each do |elem|
        file.puts elem.to_s
      end
    end
  end
end

#####################################################################
# see if state is frozen out (i.e. no more vapor is present)
#####################################################################

class Array
  def frozen_out?
    not self.flatten.member?(1)
  end
end

#####################################################################
# the simulation itself
#####################################################################

settings = get_settings
cols = settings["cols"],
rows = settings["rows"],
prob = settings["prob"]
state = initial_state(cols, rows, prob)
tick =  0
cls
while true
  output_state(state, tick)
  break if state.frozen_out?
  tick += 1
  offset = (tick + 1) % 2
  i = offset
  while i < rows
    i1 = (i + 1) % rows
    j = offset
    while j < cols
      j1 = (j + 1) % cols
      if [ state[i][j],
           state[i][j1],
           state[i1][j],
           state[i1][j1] ].member?(2)
        state[i][j]   = 2 if state[i][j]   == 1
        state[i][j1]  = 2 if state[i][j1]  == 1
        state[i1][j]  = 2 if state[i1][j]  == 1
        state[i1][j1] = 2 if state[i1][j1] == 1
      else
        if rand < 0.5
          state[i][j],  state[i][j1],  state[i1][j], state[i1][j1] =
          state[i][j1], state[i1][j1], state[i][j],  state[i1][j]
        else
          state[i][j],  state[i][j1], state[i1][j],  state[i1][j1] =
          state[i1][j], state[i][j],  state[i1][j1], state[i][j1]
        end
      end
      j += 2
    end
    i += 2
  end
end

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Follows C implementation
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void cls(void)
{
  printf("\033[2J");
}

void home(void)
{
  printf("\033[1;1H");
}

int get_even_positive(char* desc)
{
  int n = 0;
  char s[21];
  while( n <= 0 || n/2*2 != n)
  {
    printf("Please enter %s (must be even and positive): ", desc);
    scanf("%20s", s);
    n = atoi(s);
  }
  return n;
}

double get_probability(char* desc)
{
  double p = -1.0;
  char s[21];
  while (p < 0.0 || p > 100.0)
  {
    printf("Please enter probability for %s (in percent, float): ",
           desc);
    scanf("%20s", s);
    p = atof(s);
  }
  return p / 100.0;
}

int **initialize_state(int cols, int rows, double prob)
{
  int i;
  int j;
  int **a;

  a = (int **) calloc(rows, sizeof(int *));
  for (i = 0; i < rows; i++)
  {
    a[i] = (int *) calloc(cols, sizeof(int));
  }
  for (i = 0; i < rows; i++)
  {
    for (j = 0; j < cols; j++)
    {
      a[i][j] = (rand() < RAND_MAX * prob) ? 1 : 0;
    }
  }
  a[rows/2][cols/2] = 2;
  return a;
}

void display_state(int **state, int tick, int cols, int rows)
{
  int i;
  int j;
  char filename[15];
  FILE *file;

  home();
  printf("Simulation tick %d\n", tick);
  sprintf(filename, "tick_%05d.pgm", tick);
  file = fopen(filename, "w");
  fprintf(file, "P2\n");
  fprintf(file, "# %s\n", filename);
  fprintf(file, "%d %d\n", cols, rows);
  fprintf(file, "2/n");
  for (i = 0; i < rows; i++)
  {
    for (j = 0; j < cols; j++)
    {
      putc("012"[state[i][j]], file);
      putc('\n', file);
    }
  }
  fclose(file);
}

int frozen_out(int **state, int cols, int rows)
{
  int i;
  int j;

  for (i = 0; i < rows; i++)
  {
    for (j = 0; j < cols; j++)
    {
      if (state[i][j] == 1)
      {
        return 0;
      }
    }
  }
  return 1;
}

int main(void)
{
  int okay = 0;
  int tick = 0;
  int offset;
  int cols;
  int rows;
  int i, i1;
  int j, j1;
  int h00, h01, h10, h11;
  double prob;
  char s[21];
  int **state;

  while (!okay)
  {
    cls();
    cols = get_even_positive("number of columns");
    rows = get_even_positive("number of rows");
    prob = get_probability("vapor");
    printf("You want:\n");
    printf("\t%d\tcolums\n", cols);
    printf("\t%d\trows\n", rows);
    printf("\t%f\tas the initial probabilty for vapor in percent\n",
           prob * 100.0);
    printf("IS THAT CORRECT? If so please answer with: yes\n");
    scanf("%20s", s);
    okay = !strcmp(s, "yes");
    if (!okay)
    {
      puts("Please re-enter data.");
    }
  }
  state = initialize_state(cols, rows, prob);
  cls();
  while(1)
  {
    display_state(state, tick, cols, rows);
    if (frozen_out(state, cols, rows))
    {
      return 0;
    }
    offset = (tick++ + 1) % 2;
    for (i = offset; i < rows; i += 2)
    {
      i1 = (i + 1) % rows;
      for (j = offset; j < cols; j += 2)
      {
        j1 = (j + 1) % cols;
        if (state[i][j]   == 2 ||
            state[i][j1]  == 2 ||
            state[i1][j]  == 2 ||
            state[i1][j1] == 2)
        {
          if (state[i][j]   == 1) state[i][j]   = 2;
          if (state[i][j1]  == 1) state[i][j1]  = 2;
          if (state[i1][j]  == 1) state[i1][j]  = 2;
          if (state[i1][j1] == 1) state[i1][j1] = 2;
        }
        else
        {
          h00 = state[i][j];
          h01 = state[i][j1];
          h10 = state[i1][j];
          h11 = state[i1][j1];
          if (rand() < RAND_MAX/2)
          {
            state[i][j]   = h01;
            state[i][j1]  = h11;
            state[i1][j]  = h00;
            state[i1][j1] = h10;
          }
          else
          {
            state[i][j]   = h10;
            state[i][j1]  = h00;
            state[i1][j]  = h11;
            state[i1][j1] = h01;
          }
        }
      }
    }
  }
  return 0;
}
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Even if you've never seen C before you ought to be able to understand
the C implementation by comparing it to the Ruby one.

Josef 'Jupp' Schugt
-- 
Blog available at http://www.mynetcologne.de/~nc-schugtjo/blog/
PGP key with id 6CC6574F available at http://wwwkeys.de.pgp.net/


--------------enig98EF0C3220500747A59F0A5A
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFF+UvDrhv7B2zGV08RAoJbAJ9WoquZDUpOXFnhHYmU/G0MCUHR6gCfThnV
GMBR6Xw3jqEv5iskhLxCgsEL9
-----END PGP SIGNATURE-----

--------------enig98EF0C3220500747A59F0A5A--