[SUMMARY] Cellular Automata (#134)

Discussion in 'Ruby' started by Ruby Quiz, Aug 16, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    I chose this quiz because I felt it was easy and interesting. It seems the jury
    is still out on the easy aspect though. I believe there were only two correct
    solution this week. Most of them had problems with at least some rules,
    including my own code. Let's have a look at what went wrong.

    The issue is that any rule which sets the one's bit, creates a case where 000
    activates the middle cell. Since all cells not on are off and our area of cells
    is theoretically infinite in width, that means those rules create long strands
    of active cells on the very first step.

    This is only a problem because many of us tried a shortcut like my own code of:

    options[:steps].times do
    cells << "00#{cells.last}00".scan(/./).
    inject("") { |nc, n| nc + RULE_TABLE[n.join] }

    However, adding two zeros to either end is not enough to properly display these

    A better approach is to create a viewing window of the cell space large enough
    to show the interesting parts of the pattern. We will get the idea of the
    infinite spans when we see the cells running off the edges of such a window.

    It was Simon Kröger who pointed out these issues in the discuss and I believe
    his solution was the first correct submission, so let's take a peek at that
    code. Here's the setup:

    require 'optparse'

    rule, steps, cells = 145, 20, '1'

    OptionParser.new do |opts|
    opts.on("-r RULE", Integer) {|rule|}
    opts.on("-s STEPS", Integer) {|steps|}
    opts.on("-c CELLS", String) {|cells|}

    # ...

    You can see Simon require the OptionParser library here and put it to work.
    Take a close look at just how the parameters are assigned though, because the
    code is tricky.

    First, some defaults are setup in normal variables. Then the OptionParser code
    gets run, passing the user's settings into blocks that don't seem to do anything
    with the values. Note though that those block variables have the same names as
    the variables where the defaults were placed. In Ruby 1.8.x this will actually
    change the value of the outer variable.

    This is probably a good habit to start breaking now, if you catch yourself using
    it. A future version of Ruby will change these variable assignment rules and
    break code like the above.

    Now that the variables are assigned, Simon creates the current row of cells:

    # ...

    size = steps + cells.size + steps
    line = cells.center(size, '0')

    # ...

    This is just the starting cells padded with zeros. The key though is the amount
    of padding. There are only two cases for how the cells grow. We've talked
    about the infinite growth for rules with the one's bit on already, but all other
    rules can growth at most one cell in either direction each step. That's the
    padding Simon adds, step zeros to either side.

    Now we are ready for the application code:

    # ...

    steps.times do
    puts line.tr('01', ' X')
    widened = line[0, 1] + line + line[-1, 1]
    line = (0...size).map{|i| rule[widened[i, 3].to_i(2)]}.join

    This code loops over the requested number of steps. At each step, it prints the
    current row of cells.

    Now the widening step is another clever trick. Remember, we have two growth
    rates, one cell at a time and infinite growth. In the first case, we will have
    zeros at both ends and beyond that there should be more zeros. In the latter
    case, all the cells on the edges will be ones to represent the infinite growth.
    Beyond those would be more ones. By expanding the grid with what is already on
    each end, both cases are covered.

    The final line of the iterator does the actual change of cells. It walks the
    widened row, but takes the cells three at a time. This will drop the two extra
    cells at the end back off and give us the proper row length.

    The actual application of the rule is done here with bit indexing. By treating
    the three cells as a bit pattern and converting them to an Integer, we get the
    index for the rule that will fetch the proper zero or one for that pattern.

    You may want to work through this code with a pencil and paper until it all
    clicks. I did. There's a lot going on in that tiny bit of code.

    My thanks to all of the others who submitted as well. These other solutions
    were interesting as well, despite my claims that they weren't completely
    correct. Most of them worked on all of the rules that didn't expand infinitely
    and that includes the interesting rules. Do browse through those.

    Tomorrow we will fiddle with with an Erlang problem I found interesting...
    Ruby Quiz, Aug 16, 2007
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pleg
  2. defcon8
    Jun 24, 2006
  3. Replies:
    May 14, 2006
  4. defcon8
    Jun 24, 2006
  5. +mrcakey
    Jul 23, 2008
  6. Ruby Quiz

    [QUIZ] Cellular Automata (#134)

    Ruby Quiz, Aug 10, 2007, in forum: Ruby
    Yossef Mendelssohn
    Aug 15, 2007
  7. James Koppel
    James Koppel
    Aug 15, 2007
  8. defcon8
    Jun 24, 2006