One Dimensional Cellular Automata

While in Texas on a recent business trip, I picked up a copy of "Cellular Automata, A Discrete View of the World" by Joel L. Schiff from Half Priced Books in Richardson, TX. I haven't finished the book yet, but I did write a bit of code to generate one dimensional cellular automata. There are many different varieties of these explored in the book, but we're going to look a simple set where the cells can have two values, in our case black or white, and to generate the next generation, we only look at the cell and it's two immediate neighbors. In this case we're going to end up with 2**8 (or 256) rules for generating the next generation. Here is a good writeup on this type of cellular automata.

Here's the code:

#!ruby
# == Synopsis
# Runs the CA program
#
# == Usage
# ruby CA.rb [-g max_generations] [-r rule] [-c num_cells] [-s] [-v] [-h]
# 
# == Author
# Scott LaBounty
#
# == Copyright
# Copyright(c) 2010 Scott LaBounty
#
#

require 'getoptlong'

def usage
    puts "Usage: ruby CA.rb [-g max_generations] [-r rule] [-c num_cells] [-s] [-v] [-h]"
end

# The cellular automata class. This is a one-dimensional cellular automata and 
# will use the rules as defined by Wolfram and that I got from Joel L. Schiff's 
# "Cellular Automata, A Discrete View of the World".
class CA

    # Initialize the cellular automata with the number of cells, the rule we'll
    # use to update each time next is called and whether to initialize the
    # first generation with a single black cell in the middle or a random mix
    # of "W" and "B" cells.
    def initialize(num_cells, rule, random_init=false)
        @rule = rule

        # We add a cell at each end that will always be white.
        @total_cells = num_cells+2 

        # Initialize the current generation (in this case the first) and
        # the next_cell array (explained more fully in initialize_next_cell).
        initialize_current_gen(random_init)
        initialize_next_cell(rule)
    end

    # Calculate the next generation from the current generation.
    def next
        # Initialize the next generation array.
        next_gen = Array.new(@total_cells, "W")

        # Calculate the next generation based on the current generation and the
        # rule we're using.
        @current_gen.each_with_index do |cell, i|
            # Skip the ends which will by definition always be white.
            next if (i == 0) || (i == @total_cells-1)

            # Calculate the next_gen[i] by using the i cell and the two next to
            # it. Get the next value from the next_cell array.
            next_gen[i] = 
                case @current_gen[i-1, 3].join
                when "WWW"
                    @next_cell[0]
                when "WWB"
                    @next_cell[1]
                when "WBW"
                    @next_cell[2]
                when "WBB"
                    @next_cell[3]
                when "BWW"
                    @next_cell[4]
                when "BWB"
                    @next_cell[5]
                when "BBW"
                    @next_cell[6]
                when "BBB"
                    @next_cell[7]
                end
        end

        # Set the current_gen to the next gen.
        @current_gen = next_gen
    end

    def to_s
        @current_gen.join
    end

    private

    # Initialize the current_gen array with either a
    # single "B" cell in the middle or with a random
    # mix of "B" and "W" cells.
    def initialize_current_gen(random_init)
        @current_gen = Array.new(@total_cells, "W")
        if random_init
            @current_gen.each_index do |i|
                @current_gen[i] = (rand < 0.5) ? "W" : "B"
            end
        else
            @current_gen[@total_cells/2] = "B"
        end
    end
        
    # Initialize the next_cell array based on the rule we're using. If the ith
    # bit is a 0, we'll set it to a "W" and if it's a 1, we'll set it to be a
    # "B". See the "next" method for how this array is actually used. If the
    # cell and its two neighbors are "W" (white), then we use next_cell of 0,
    # If the cell is "W" and its neighbor to the left is "W" and its neighbor
    # to the right is "B" then we use next_cell of 1, and so on.
    def initialize_next_cell(rule)
        @next_cell = Array.new(8)
        @next_cell.each_index do |i| 
            @next_cell[i] =  (rule % 2 == 0) ? "W" : "B"
            rule /= 2
        end
        puts "@next_cell = #{@next_cell.join}" if $verbose
    end

end

# Only run this if this is the main program. This way we
# can use the CA class above from other programs with a 
# require.
if __FILE__ == $0

# Set up the command line options
opts = GetoptLong.new(
    ["--max_generations", "-g", GetoptLong::REQUIRED_ARGUMENT],
    ["--rule", "-r", GetoptLong::REQUIRED_ARGUMENT],
    ["--num_cells", "-c", GetoptLong::REQUIRED_ARGUMENT],
    ["--random_init", "-R", GetoptLong::NO_ARGUMENT],
    ["--verbose", "-v", GetoptLong::NO_ARGUMENT],
    ["--help", "-h", GetoptLong::NO_ARGUMENT]
    )

# Set the default values for the options
max_generations = 100
rule = 100
num_cells = 31
random_init = false

$verbose = false

# Parse the command line options. If we find one we don't recognize
# an exception will be thrown and we'll rescue with a RDoc::usage
begin
    opts.each do | opt, arg|
        case opt
        when "--max_generations"
            max_generations = arg.to_i
        when "--rule"
            rule = arg.to_i
        when "--num_cells"
            num_cells = arg.to_i
        when "--random_init"
            random_init = true
        when "--verbose"
            $verbose = true
        when "--help"
            usage
        end
    end
rescue
    usage
end

puts "max_generations = #{max_generations} rule = #{rule} num_cells = #{num_cells}" if $verbose

# Create a new cellular automata using the correct
# number of cells (width) and rule.
ca = CA.new(num_cells, rule, random_init)

1.upto(max_generations) do |g|
    puts "#{ca} Generation: #{g}"
    ca.next
end

end

We start out with a comment header (leftover from the days when rdoc/usage would work. We'll skip over the CA class itself for now and then we see the line if __FILE__ == $0
. This lets ruby know that we shouldn't run this if it's not the "main" routine as $0 will be the file that is run on the command line. Next, we set up our command line options for the number of generations to run, which rule (we'll discuss this more later), the number of cells in our automata, and whether to initialize with a single cell in the middle (the default) or to initialize the automata with a random mix of black and white cells. Then we process the command line options, create a new CA using the various options, and then run the CA up to the appropriate number of generations. We should get a long number of lines with a mix of "B" and "W" characters followed by the generation. Obviously, for doing any real work, we'd like a better display, but this will let us get started.

Let's go back and look at the CA class now. We start out with our initialize method which takes a few of the command line options and creates the CA with them. We create the CA with two extra cells, one on each end, that are always "W". This allows us to have the correct number of cells in the CA. We then initialize the current generation with either the single black cell in the middle or a mix of black and white cells. Finally, we initialize the next_cell array. This array contains, based on the rule that's passed in, the new value of the cell based on the cell's current value and the value of its neighbors. It's calculated from the rule based on the rule's binary representation where if the rule has a one in a particular bit position, we will put a "B" in the corresponding position in the next_cell array otherwise a "W". For example let's take a look at rule say Rule 30. Its binary representation is "00011110" and our next_cell array will be "WWWBBBBW". We'll use this array to as we check the cell and its neighbors to decide what should be in that cell in the next generation. For "WWW" we'll use next_cell[0], for "WWB", we'll use next_cell[1] and so on up to "BBB" where we'll use next_cell[7]. This leads us back to the next method which is the heart of the program. We create a next_gen array first that is of size total_cells initialized with all "W" (recall the ends are going to always be white). Then we loop through all the cells, skipping the first and last, and using our next_cell array and the current_gen array to generate the next_gen array. The case statement with the join will create a string based on the cell and its neighbors that we'll use to decide which of the next_cell values to use. Finally, we'll assign current_gen to next_gen and return. The last method to_s just returns a string version of the current_gen for display purposes.

As always, let me know if you have questions or comments.

Kaprekar Numbers

I saw this one over on Programming Praxis and thought that it would be a good ruby problem and probably something that I might use as an interview question for a programmer. Once again, like our post on Happy Numbers, it has both math and string work plus it can be done relatively quickly. Here's the introduction from Programming Praxis ...

Wolfram’s MathWorld describes Kaprekar numbers like this:

Consider an n-digit number k. Square it and add the right n digits to the left n or n-1 digits. If the resultant sum is k, then k is called a Kaprekar number. For example, 9 is a Kaprekar number since 92 = 81 and 8 + 1 = 9 and 297 is a Kaprekar number since 2972 = 88209 and 88 + 209 = 297.

Your task is to write a function that identifies Kaprekar numbers and to determine the Kaprekar numbers less than a thousand. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

And here's the ruby code for this ...

# Wolfram’s MathWorld describes Kaprekar numbers like this:
# 
#     Consider an n-digit number k. Square it and add the right n digits to the
#     left n or n-1 digits. If the resultant sum is k, then k is called a
#     Kaprekar number. For example, 9 is a Kaprekar number since 92 = 81 and 8
#     + 1 = 9 and 297 is a Kaprekar number since 2972 = 88209 and 88 + 209 =
#     297.
# 
# Your task is to write a function that identifies Kaprekar numbers and to
# determine the Kaprekar numbers less than a thousand. When you are finished,
# you are welcome to read or run a suggested solution, or to post your own
# solution or discuss the exercise in the comments below.

def kaprekar?(k)
    # Get the number of digits in k.
    n = k.to_s.length

    # Get the number squared and convert it to a string.
    k_sqr_str = (k**2).to_s

    # Get the right side of n digits. Here we use the ruby array function that
    # starts from the end of the array and counts back n digits and then grabs
    # n digits.
    right = k_sqr_str[-n, n]

    # Grab the remaining n or n-1 digits.
    left = k_sqr_str[0, k_sqr_str.length-right.length]

    # Sum the left and right sides.
    sum = left.to_i + right.to_i

    # Check if the sum that we just computed is the same
    # as k that we passed in. If so return true for a kaprekar
    # number otherwise false.
    sum == k ? true : false
end

# Find the kaprekar numbers up to 1000 and print 
# the ones we find.
1.upto(1000) do |k|
    puts "#{k} is a kaprekar number" if kaprekar?(k)
end

This is a relatively "naive" implementation and you can see that the implementations given on the Praxis site are a bit more interesting. This though is something like what I'd expect someone to come up with as part of an interview. Also, I managed to misspell Kaprekar when I did this over at Praxis and this contains the correct spelling.

Let me know if you have questions or comments.

Snippet Highlighting with Ramaze and Sequel

A few days ago I saw this post on creating a pastie "clone" using Sinatra and Datamapper. I thought that it might be cool to try something similar in Ramaze and Sequel. It actually ended up being pretty easy (and similar to the other post (especially since I "stole" most of his CSS, etc.)), so I thought I'd share it here. If you've read much of this blog, then you should be pretty familiar with most of this, so I won't go through all of the code here but just hit the highlights. Here's the controller, controller/main.rb:

# controllers/main.rb
#
# The MainController has methods for index/main (to create a new snippet) and show (to show
# an existing snippet).

# Require syntaxi for syntax highlighting.
require 'syntaxi'
Syntaxi::line_number_method = 'floating'
Syntaxi::wrap_enabled = false
Syntaxi::wrap_at_column = 120

class MainController < Controller

    # The main/index page that shows a text area where we can put in a 
    # title and a snippet. We'll grab the title and snippet text, create a new
    # snippet, and then go to the snippet display page to see it.
    def index
        @title = "Snippet!"

        # We've got a post, so grab the title and the snippet and then create
        # a new Snippet with them and the current time. We'll then go ahead and 
        # redirect to the show method with the id that we get from the snippet.
        if  request.post?
            title = request[:title]
            snippet_text = request[:snippet]
            snippet = Snippet.create(:title => title, :body => snippet_text, :created_at => Time.now)
            redirect rs(:show, snippet.id)
        end
    end

    # The show page that shows an existing snippet. It takes the id of an existing 
    # snippet and if it exists shows it nicely highlighted. If it doesn't exist, we'll
    # just go back to the main page after setting the flash.
    def show(id)
        @title = "Show Snippet!"

        # Find the snippet if it exists
        @snippet = Snippet[id]

        if @snippet != nil
            # Get some text we can use to substitute for the "[/code]" text so that it doesn't
            # mess up Syntaxi.
            replacer = Time.now.strftime('[code-%d]')

            # Do the syntax highlighting of the text with Syntaxi after we've done our
            # substitution.
            @snippet_highlight = Syntaxi.new("[code lang='ruby']#{@snippet.body.gsub('[/code]', replacer)}[/code]").process

            # Substitute the '[/code]' back in for our replacement text.
            @snippet_highlight = "#{@snippet_highlight.gsub(replacer, '[/code]')}"
        else
            # The snippet doesn't exist, so set a message and just redirect
            # to the main/index page.
            flash[:message] = "Snippet #{id} not found."
            redirect rs :index
        end
    end
end

We start out requiring syntaxi which can be used with a sudo gem install syntaxi. The next three lines set a few variables which can be read about at the link. The index method will all the user to put in a snippet in a text area and then we'll create the Snippet (see model/models.rb and dbMigration/001_RamazeSnippet.rb for the information in this table/model). After we've created the new snippet, we'll redirect to the show method with the id of the new snippet.

The show method takes the id of the snippet and then displays the syntax highlighted version of it. It grabs the snippet from the database and if the snippet is not nil, it creates a "replacer" for [/code] which signals syntaxi to quit highlighting. We then substitute this replacer for the a [/code] and process the snippet. When this is complete, we resubstitute the [/code] for replacer and save it so the view can get to it. The view/show.xhtml is pretty simple and just displays the title, the highlighted snippet, and the creation date.

Like I said, not too much other than the syntax highlighting that we haven't seen before here. You can check all of the code on GitHub and run the code on Heroku.

Let me know if you have questions.

Sequel Models one_to_one Associations

We looked in the past at both one to many/many to one and many to many/many to many associations, but we haven't looked at one to one associations yet. I was looking at this for addresses where a couple of different classes would use them so I wouldn't want to embed them in each table. The documentation here is good, but I needed a bit of help (and straightening out) from Jeremy Evans and the Sequel group, so I thought this might be a good topic. Here's the code we'll be using ...

require 'rubygems'
require 'sequel'

# Create an in-memory database.
DB = Sequel.sqlite 

# Create a businesses table with a name an address.
DB.create_table :businesses do 
    primary_key :id
    String :name, :text=>true, :unique=>true
    foreign_key :address_id
end

# Create a people table with a name and an address.
DB.create_table :people do 
    primary_key :id
    String :name, :text=>true, :unique=>true
    foreign_key :address_id
end

# Create a table of addresses that can be used by both people
# and businesses. This is just an example and real addresses would
# be done with street addresses, cities, states, countries, etc.
DB.create_table :addresses do
    primary_key :id
    String :address
end

# From the documentation ...
# Differences Between many_to_one and one_to_one
# If you want to setup a 1-1 relationship between two models, you have to use
# many_to_one in one model, and one_to_one in the other model. How do you know
# which to use in which model?  The simplest way to remember is that the model
# whose table has the foreign key uses many_to_one, and the other model uses
# one_to_one:  
#
# For our case, the people and businesses have the foreign key and use the many_to_one and
# addresses will use one_to_one for both.

# The business model backed by the businesses table. Note the
# many to one for addresses.
class Business < Sequel::Model
    many_to_one :address # Note this is singular.
end

# The person model backed by the people table. Note the
# many to one for addresses.
class Person < Sequel::Model
    many_to_one :address # Note this is singular.
end

# The address model backed by the addresses table. Note the
# one to one for both business and person.
class Address < Sequel::Model
    one_to_one :business # Note this is singular.
    one_to_one :person # Note this is singular.
end


# Create a new business and person.
business = Business.create(:name => "The Business")
person = Person.create(:name => "Bob")

# Create new addresses for each of the above.
address_1 = Address.create(:address => "123 W. Lane, Anytown, CA 91110")
address_2 = Address.create(:address => "124 W. Lane, Anytown, CA 91110")

# Add the addresses for each of the above. Note that these use setter methods and not the 
# add_ that you would see for many_to_one and many_to_many relationships.
business.address = address_1
person.address = address_2

# Print them out to show we got them correct.
puts "Business: #{business.name} at #{business.address.address}"
puts "Person: #{person.name} at #{person.address.address}"

We start out creating the database and the tables we'll use. The businesses and people tables both contain foreign keys to the addresses table and a name (in real life, these would be much more complex). The addresses table simply contains the address. Next we have the models that represent the tables. Be sure to read the comments that come directly from the documentation and that will help your understanding. Basically, in the table that has the foreign key (in this case businesses and people), the corresponding models will have a many_to_one association with the other model (in this case addresses). Note that both the many_to_one and one_to_one associations should take a singular identifier. After this, we'll create a business and a person, a couple of addresses, and then link them together. Here, we need to use the setter method (.address and not add_address() as I first tried (once again, it's in the documentation, but I obviously missed it)). Finally, just to make sure we print everything out.

Let me know if you have questions or comments.

Ramaze and Partial Rendering

Over on the Ramaze list, we had quite a conversation going on about the MVC paradigm. In response to that, I ended up doing some research on partial rendering (rendering a piece of a view using another view). I ended up writing some code and it's available on GitHub here. The original code was generated using ramaze create RenderPartial and then modified to its present form.

class MainController < Controller
  # the index action is called automatically when no other action is specified
  def index
    @title = "Welcome to Ramaze!"
  end

  def page_1
    @title = "Page 1"
    @colors = ["blue", "brown", "hazel"]
  end

  def page_2
    @title = "Page 2"
    @colors = ["blue", "brown", "hazel"]
  end

end

The colors are predefined here in the controller, but in a real example, you would normally get them from a model probably from a database. The use of colors itself comes from the question in the email trail about dolls and the different color of eyes they could be. There's nothing particularly complex in here, we've seen it quite a few times, there's an index method and then two additional page methods where the latter are pretty much exactly the same.

The views are where the interesting part is though. Here's the page 1 view contained in view/page_1.xhtml


<p>
Page 1
#{ render_partial :color }
</p>


and the page 2 view, view/page_2.xhtml


<p>
Page 2
#{ render_partial :color }
</p>



and finally, the view/color.xhtml, the partial that we render:


<ul>
<?r @colors.each do | color | ?>
<li> #{color} </li>
<?r end ?>
</ul>


Here, we simply take the colors that were defined in the controller methods and use them to generate a list (obviously, we could have done whatever we wanted with them). The lines in the two page views #{ render_partial :color } tells the view to fill in this spot with the view/color.xhtml code. Although, we haven't here, you can also pass parameters to the partial. Here's a post that shows how to use that feature.

Hopefully, this is all pretty clear, but if not, as always, feel free to leave questions in the comments section.

Sequel and Heroku

Well, this turned out to be a bit harder than I expected, but with quite a bit of help from the Sequel, Ramaze, and Heroku lists, I got it worked out. The source code for this particular exercise is here. I'm only going to show a couple of files here as everything else you've already seen. First, here's how to do the migration in a rakefile ...

namespace :db do
    require 'rubygems'
    require 'sequel'
    Sequel.extension :migration

    task :migrate do
        m = Sequel::Migrator
        db = Sequel.connect(ENV['DATABASE_URL'] || 'sqlite://library.sqlite')
        dir = "dbMigration"

        target = ENV['TARGET'] ? ENV['TARGET'].to_i : nil
        current = ENV['CURRENT'] ? ENV['CURRENT'].to_i : nil

        m.run(db, dir, :target => target, :current => current)
    end
end

We create a sequel migrator and connect to the database. The database connection line contains two parts. The first side is if there's an environment variable named DATABASE_URL then we'll use that to connect to the database. This is an environment variable set by Heroku. If this isn't set, then we'll go ahead and connect to a sqlite database, library.sqlite. We use the Sequel.connect command rather than Sequel.sqlite as we don't know which type of database we're going to be using. On Heroku, it will be PostgreSQL and locally, we use sqlite. Next up, we set the directory where we'll keep our migrations, in this case, dbMigration which is my standard. After that, there's two lines used for telling sequel which version we're going to, target, and starting from, current. Finally, we run the migrator with the database, directory, target and current. The final two are part of a hashtable that's used by this migrator. You could also use m.apply where the first two parameters are the same and then pass the target and current as integers, but the migrator code seems to imply that the run version is preferred. To run this locally, simply do a rake db:migrate and it should migrate to the latest version. To move to a different version you can run rake TARGET=0 db:migrate to remove everything from the database. If you just want to move to the latest version, don't put a target or current in, they'll be nil, and it should just migrate to the latest. Now, to run it on Heroku and migrate the database there simply add heroku in front of the command as in heroku rake db:migrate after you've pushed all the code up to Heroku with a git push heroku master as we saw in the last post.

I haven't talked about rake before, so I should probably give a little background for it. It's a ruby version of the Unix make. It has tasks and commands to do them. The homepage for it is here and here is a nice article on using it.

OK, now let's take a look at our model file model/models.rb.

# The database should have been set up using the database migrations in
# the dbMigration directory. 
require 'rubygems'
require 'ramaze'
require 'sequel'

# Open the library's database. This must be done before we access the models
# that use it.
Sequel.connect(ENV['DATABASE_URL'] || 'sqlite://library.sqlite')

#
# This is the model for the authors and is backed by the :authors table in the
# database. 
#
# Create the Author model. 
class Author < Sequel::Model 
    many_to_many :books
end

#
# This is the model for the book and is backed by the :book table in the
# database. 
#
# Create the Book model. 
class Book < Sequel::Model 
    many_to_many :authors
end

This looks exactly like our previous models with a couple of exceptions. Here, we've moved our database connection into here from start.rb. It probably makes more sense here and keeps all of our Sequel code in one place (I got this idea from the Ramaze generated code). The connection itself looks surprisingly like our connection that was used in the rakefile. We end up using either a DATABASE_URL environment variable (supplied by Heroku) or the sqlite library.sqlite. After that, there are a couple of models that are in the database that we can use. The tables for the database and some data are created in the dbMigration/001_LibraryMigration.rb file.

You can see the end result of all of this here.

All of the code for this is up on github and as always, if you have questions, leave them in the comments.