Tuesday, November 30, 2010

Ruby 1.9.2 and Ramaze

OK, I just found out something interesting about ruby 1.9.2. They've changed the default LOAD_PATH to not include "." (current directory). What's this actually mean? Well, for starters just about every example that I and most others have written will no longer work. Here's an example with something from the current Ramaze prototype (generated when you do a ramaze create foo

require 'model/user'

this will generate errors if you run it with ruby 1.9.2. What you'll need to do instead is either

__DIR__('user')

or

require_relative 'user'

The first version is compatible between 1.9 and 1.8 and the 2nd is 1.9 only. Both examples assume that the file this code is in is already in the model directory.

I should also note that Lee Jarvis has fixed the problem with the prototype already and it should be in the next update of Ramaze.

Like I said, most of my examples from previous posts are now wrong, but they should be pretty easy to fix once you know how. If you have any problems, be sure to let me know and I'll try to help get them worked out with you.

Wednesday, November 24, 2010

Ruby Book - $10

This is a pretty good deal for the latest Ruby pickaxe book from Dave Thomas and the Pragmatic Programmer group. It's $10 each for the paper or electronic version of the book. Head over here to grab it.

Saturday, October 16, 2010

Log Monitoring with a Ruby DSL

DSLs (Domain Specific Languages) are small languages built on top of general purpose languages to accomplish specific tasks. Examples of DSLs are things like rake/make for building executables, bc (the Unix/Linux calculator), and macro systems like the C/C++ precompiler and M4. Ruby, because of its syntax provides a great platform for building DSLs.

Recently, at work, we ended up needing to monitor a log file for a particular string. Our OPS group implemented this, but it turned out that we were getting quite a few false positives from the string by itself. We could however do a database check on a couple of items in the string to remove these false positives. The logging software we use didn't really allow this so we ended up putting together a .NET application (Windows box) that would be called when the string was found, it would do the database check, and then do the notifications as necessary. I started thinking that it would be nice if you could match a string and then provide some code to do whatever you'd like in a monitoring type system. Since I'd been looking at DSLs, this seemed like it might be a natural application for them.

Let's start out with a simple program to provide us a log file to monitor ...


while true
v = rand
if v < 0.1
s = "Error"
elsif v < 0.2
s = "Warn"
else
s = "Info"
end
puts "#{Time.new}: #{s}"
$stdout.flush
sleep 1
end


So essentially, do forever, get a random number, 1/10 of the time put out an Error, 1/10 of the time put out a Warning, and the rest of the time put out an Info. These will all be preceded by the date/time. Obviously, in a real system, you'd just use your own logs. For this, I just ran this and redirected the output to mylog.txt.

OK, here's the DSL we'd like to implement. I put it in monitor.mon and when we run the program, we'll "interpret" this file. Here it is ...


monitor "Er.*r" do |line, match|
puts "Error in: #{line} "
end

monitor "Warn" do |line, m|
puts "Warning in: Match: #{m[0]}: #{line} "
end

monitor "Info"


So in the first item to monitor, we look for something like an "Error" (the ".*" is in there really just to show this can really be a regular expression. The second thing to monitor is the word "Warn", and finally the work "Info". In the first two cases we print a message, with the 2nd one actually showing the "match". We don't give a block to the 3rd one, but the default is to print a message too. Now even though we've done something pretty simple here, there is nothing preventing us from doing whatever we'd like in them that we can do in Ruby. Here, I'm thinking of things like emailing using possibly mailit) or database access as in our above problem using Sequel. At this point, we can "shell out" to the general purpose programming language of Ruby.

So, now we need to interpret the above file. Here's the code for this


require 'file/tail'

class MonitorLog

def initialize(filename, number)
@filename = filename
@number = number
@monitors = []
end

# Add a new monitor (regex/block).
def add_monitor(monitor)
@monitors << monitor
end

# Monitor the log using the filename passed in. For each
# line we'll check for a monitor match.
def monitor
File::Tail::Logfile.open(@filename) do |log|
log.backward(@number).tail do |line|
@monitors.each do |m|
m.match line
end
end
end
end

end

# The Monitor class which is a type of Regexp with a block given for checking.
class Monitor

# Create a new monitor with a regex and a block.
def initialize(regex, block)
@regex = Regexp.new regex
@block = block
end

# Match a line. If we match, then we'll call the block
# with the line and the MatchData.
def match(line)
m = @regex.match(line)
@block.call(line, m) if m != nil
end
end

# This will normally come from the monitor file where there will be a regular
# expression and a block to execute when it is found. If no block is given,
# we'll just print the line.
def monitor(regex, &block)
if block_given?
$monitor_log.add_monitor Monitor.new(regex, block)
else
$monitor_log.add_monitor Monitor.new(regex, lambda { |l, m| puts "Match: #{l}" })
end
end

if __FILE__ == $PROGRAM_NAME

require 'getoptlong'

def usage
puts "Usage #$0 [-n number] [-f filename] [-m monitor_filename]"
end

# Set up the command line options
opts = GetoptLong.new(
["--number", "-n", GetoptLong::REQUIRED_ARGUMENT],
["--filename", "-f", GetoptLong::REQUIRED_ARGUMENT],
["--monitor_file", "-m", GetoptLong::REQUIRED_ARGUMENT],
["--verbose", "-v", GetoptLong::NO_ARGUMENT],
["--help", "-h", GetoptLong::NO_ARGUMENT]
)

# Set the default values for the options
number = 10
filename = 'monitor.log'
monitor_filename = 'monitor.mon'
$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 usage.
begin
opts.each do | opt, arg|
case opt
when "--number"
number = arg.to_i
when "--filename"
filename = arg
when "--monitor_filename"
monitor_filename = arg
when "--verbose"
$verbose = true
when "--help"
usage
exit
end
end
rescue
usage
exit
end


# Create the montior log. We make it global as it's used for the monitor()
# creation method above.
$monitor_log = MonitorLog.new(filename, number)

# Load in the monitor file DSL.
load(monitor_filename)

# Start monitoring.
$monitor_log.monitor

end



Our first class is MonitorLog which takes a filename to monitor and a number the number of lines to start back in the file. We also have an array for the different monitors we define in the monitor.mon file. There's a add_monitor which takes a monitor and adds it to the array and finally, the monitor (I know too many monitor variables) which uses the file-tail gem. This method will simply tail the file and for each line call each of the monitors. The Monitor class contains a regular expression to match and a block to execute on a match. In the match method, we check the regular expression and if it matches, we'll call the block with the line we matched and the MatchData. Here, if we had a more interesting regex than I've shown so far, you could grab out things like login IDs or similar from the MatchData if you needed it for something rather than reparsing the line.

Now comes the "interesting" piece, the monitor (I know, I know). Note that this matches with the monitor.mon name and indeed this is what gets called when that file is loaded (see below). The two parameters are the regex and potentially a block. If the block is given we create a Monitor using them and if there's no block, as in the Info then we'll create a lambda that will print out "Match" and the line.

The rest of the code is the "main" program, getting the command line arguments, creating a new $monitor_log (made global for use in the monitor method, here, I'd be interested in a better way to do this), loading the monitor.mon file, and finally starting the monitoring.

Here's how to run this code ruby Monitor.rb -n 20 -f mylog.txt -m monitor.mon.

There's quite a bit missing here to make this a truely useful application. Certainly adding email would get you a long way towards this and is really easy to do. The slightly more difficult thing is to make this work with rotating log files or even multiple log files and these are left as an exercise for the reader ;-).

Let me know if you have questions or comments.

Tuesday, October 12, 2010

Zeller's Congruence and Five Fr/Sa/Su in October

I saw a comment from one of my Facebook friends that October 2010 had five Fridays, Saturdays, and Sundays and that this occurred only once every 823 years. Now this didn't sound exactly right to me and it didn't take much time to figure out why. Take a look at the following calendar


Su Mo Tu We Th Fr Sa
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31


You can see pretty easily from this, that a) we'll have the five Fr/Sa/Su anytime we start October on a Friday and b) no other configuration will have this. Now just thinking about this off the top of my head, I figured that this should happen about ever 7 years (disregarding leap years).

Now as it happens, I'd also just finished a short ruby method for Zeller's Congruence that I'd written from an article on Programming Praxis. So, I combined the two and came up with the following ...


# Zeller’s Congruence is a simple mathematical method for determining the day
# of the week for a given date.
#
# In the 1880s, Christian Zeller, a German mathematician, noticed that, if you
# run a year from March through February, the cumulative number of days in each
# month forms a nearly straight line; that works because February, which would
# normally perturb the straight line, is moved to the end. He worked out the
# formula ⌊(13m−1)/5⌋ to give the number of weekdays that the start of the
# month moves each month, where m is the month number.
#
# Then it is easy to calculate the day of the week for any given day: add the
# day of the month, the offset for the number of months since March, an offset
# for each year, and additional offsets for leap years and leap centuries
# (remembering to subtract one year for dates in January and February), taking
# the whole thing mod 7. It’s fun to work out the arithmetic yourself, but if
# you don’t want to take the time, the whole formula is shown in the solution.
#
# Your task is to write a function that uses Zeller’s Congruence to calculate
# the day of the week for any given date. 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.#
#
# f = k + floor(13m - 1) / 5) + d + floor(d / 4) + floor(c / 4) - 2c mod 7
#
# Su Mo Tu We Th Fr Sa
# 1 2
# 3 4 5 6 7 8 9
# 10 11 12 13 14 15 16
# 17 18 19 20 21 22 23
# 24 25 26 27 28 29 30
# 31
#
#
#
def zeller(year, month, day)
months = %w[march april may june july august september october november december january february]
weekdays = %w[Sunday Monday Tuesday Wednesday Thursday Friday Saturday]
k = day
m = months.index(month.downcase) + 1
y = (m <= 10) ? year : year-1
d = y % 100
c = y / 100
f = (k + (((13*m) - 1) / 5).floor + d + (d/4).floor + (c/4).floor - (2*c)) % 7
weekdays[f]
end

1900.upto(2300) do |y|
puts "Five Friday, Saturday, and Sundays for October, #{y}" if zeller(y, "october", 1) == "Friday"
end


Here, we'll just go through the years from 1900 to 2300 or about 400 years and see how many times the five Fr/Sa/Su pattern occurs. If we run this and pipe it through wc -l, we end up with 56. Interestingly enough, 400 / 7 is 57 which is what we originally calculated above ignoring the leap years.

Let me know if you have any questions or comments.

Wednesday, September 22, 2010

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.

Tuesday, September 21, 2010

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.

Monday, September 13, 2010

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.

Wednesday, September 8, 2010

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.

Saturday, September 4, 2010

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.

Thursday, September 2, 2010

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.

Friday, August 13, 2010

Ramaze, GitHub, and Heroku

I first heard of Heroku from, I believe, a rant by Zed (if you're offended by profanity, this is probably not for you). It looked pretty interesting and so I decided to give it a try. This was actually a bit more involved than I thought, not hard, but for the first time you have more than a few steps to get through. What I'm going to show is how to a) get Git running, set up GitHub, create the Ramaze application, load it to GitHub, and finally load it to Heroku. Strictly speaking, you don't need GitHub to get the app running on Heroku, but I'm going to start putting some of my posts up there and so I thought I might as well show it too.

Let's start with getting git up and running. On my Ubuntu system, simply type sudo apt-get install git-core. After that type git --version (my shows git version 1.7.2.1) to make sure everything installed correctly.

Next, let's set up a GitHub account. Go to http://github.com/plans and create yourself a free account (or move up to a paid account if you want). Next, you're going to need to generate a SSH key which will be used by both GitHub and Heroku. You can go to http://help.github.com/linux-key-setup/ if you're running Linux or http://help.github.com/windows-key-setup/ if you're on Windows (probably similar for you Mac users). Follow the directions and you should now have access to your GitHub account. Here's the command on Linux ssh-keygen -t rsa -C "yourusername@youremailprovider.com" to create the keys.

Now you'll want to configure git with a few your user name and email. The commands for this are:

Configure git with user and email
git config --global user.name "yourusername"
git config --global user.email "yourusername@youremailprovider.com"


We're going to put our code up on GitHub first, so let's create an application first. Let's just use the default ramaze application and upload that (not exactly what I've done, but close enough). First go to your Dashboard on GitHub and create a new repository and call it "foo". This is where the application will live on GitHub. Now, run ramaze create foo to create an application called foo in the current directory. Then cd foo and we'll get the application ready to upload. We do need to add one file for Heroku and that's a .gems file. This file will contain a list of all the gems used by your application. In this case, the file should have the single line ramaze. If you're using Sequel say, the file would also contain a line sequel. In general it should have a line for each gem and the gem name should be what you would do by a sudo gem install xxx. Here we're going to run some git commands. I'm just learning git myself, but here's a book that should help you get started. The maintainer of this book, Scott Chacon, also has a dead tree book called "Pro Git" that is also quite good. So assuming we're in the foo directory already, type git init. This will get the application ready for git. Next we need to add the files with a git add . to add all the files in this directory and all of it's subdirectories into the repository. Now we need to do a "commit" of the files with a git commit -m 'first commit for foo'. Next, we'll tell git where we're going to save this with a git remote add origin git@github.com:slabounty/foo.git and finally, we'll push it to GitHub with git push origin master. You should now be able to go to your GitHub dashboard, see this repository and look at the files in there. Also, since this is a "public" repository, others will also be able to view and download these files, so don't use this for proprietary code unless you're using a non-free plan.

OK, let's move on to getting this up and running on Heroku. Start by creating an account on Heroku at http://heroku.com/. Once you have an account, you can sudo gem install heroku to get the Heroku gem. Next we'll do a heroku keys:add (this uses the same keys we created above to allow us to upload our files to Heroku. The one thing to make sure of is that you've created the .gems file as described above. Start with these two commands

git remote add origin git@github.com:slabounty/SimpleHeroku.git
git push origin master


Next we'll create an application on Heroku (we don't need to go to the website to do it, we'll just use the gem) with heroku create (creates an application on Heroku and let's you know where it's at. In my case it was http://smooth-stone-75.heroku.com) and finally we push it up to Heroku with a git push heroku master.

You can then point your browser where ever the application was created at, for example the web site above and you should see it running there. What is there is not the base Ramaze application that would be created but another simple one that I did. You should be able to see the code on GitHub.

There quite a bit of information here and if any of it is unclear, let me know.

Wednesday, July 28, 2010

Sequel Trees Redux

In a previous post, I discussed Sequel Trees. I had a question from that post on viewing the tree in "tree order". There are a couple of ways to do this one is recursive, which we'll use here. The other, from Jeremy Evans, is to use the rcte_tree plugin and a database that supports it. The latter is completely beyond me, so we'll go with the former.

Here, we're going to start out the same way we did last time by building up a database for a company. We've added a few things though. First, we have a title for each of the employees and second, we've added another top level employee (President) and a few additional employees under him. Once we have the structure in place, we get the roots (Presidents) of the model using Employee.roots and then for each of those employees, we loop calling the put_management_chain function. put_management_chain will print the title and name of the employee and then call itself recursively with each of the employees direct reports, children. One nice thing to note here is the level parameter to the function which is used in the puts to give us the proper indentation by taking three spaces and multiplying it by the indentation level.

Here's the code for the full program:


require 'rubygems'
require 'sequel'

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

# Create the employees table with a name and parent_id.
DB.create_table :employees do
primary_key :id
foreign_key :parent_id, :employees
String :name, :text=>true, :unique=>true
String :title, :text=>true
end

# Create the Employee model.
class Employee < Sequel::Model
plugin :tree # Uses :parent_id field for parent
end

# Puts out the management chain for an employee recursively. The level is used
# to print out some spaces in front of the name to show the relationship.
def put_management_chain(e, level)
puts "#{" "*level}#{e.title}: #{e.name}"
direct_reports = e.children
direct_reports.each do | d |
put_management_chain(d, level+1)
end
end

# Create a top level employee, Alice.
alice = Employee.create(:name => "Alice", :title => "President")

# Create Alice's direct reports.
bob = Employee.create(:name => "Bob", :title => "Vice President", :parent_id => alice.id)

# Create Bob's direct reports.
charlene = Employee.create(:name => "Charlene", :title => "Manager", :parent_id => bob.id)
dave = Employee.create(:name => "Dave", :title => "Manager", :parent_id => bob.id)

# Create Charlene's and Dave's direct reports.
ellen = Employee.create(:name => "Ellen", :title => "Software Engineer 1", :parent_id => charlene.id)
frank = Employee.create(:name => "Frank", :title => "Software Engineer 2", :parent_id => charlene.id)
gerald = Employee.create(:name => "Gerald", :title => "Software Engineer 2", :parent_id => dave.id)

# Create another top level employee, Alvin.
alvin = Employee.create(:name => "Alvin", :title => "President" )

# Create Alvin's direct reports.
bill = Employee.create(:name => "Bill", :title => "Vice President", :parent_id => alvin.id)

# Create Bill's direct reports.
cedric = Employee.create(:name => "Cedric", :title => "Manager", :parent_id => bill.id)
dale = Employee.create(:name => "Dale", :title => "Manager", :parent_id => bill.id)

# Create Cedric's and Dale's direct reports.
edward = Employee.create(:name => "Edward", :title => "Software Engineer 1", :parent_id => cedric.id)
felicia = Employee.create(:name => "Felicia", :title => "Software Engineer 2", :parent_id => dale.id)

# Find all of the employees that don't have managers.
top_level = Employee.roots

# Print out the management structure for each of the top level managers.
top_level.each do | r |
put_management_chain(r, 0)
puts
end


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

Wednesday, July 14, 2010

Happy Numbers

Here's one that I saw on-line recently in an article on F#, Microsoft's function language (there was actually a nice flame war going on on the site with respect F# vs. Mathmatica's language M). Anyway, from Wikipedia, here's the definition of a happy number:
A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers[1]).


I actually used this recently as a programming interview question and was surprised how well it worked out. It's easy enough to work out in 15-20 minutes (or at least to get most of the main ideas), it contains both math and string work, and you need either a hash or a set as a data structure to contain the visited numbers.

The code itself is relatively straightforward. If we start down in the main part of the program, you'll see that we create an array to save the happy numbers and then loop to find all of the happy numbers less than or equal to 500 saving them in the array. Finally we print them out.

The function happy_number? takes a single parameter n and determines if it is a happy number. First, we create a hash table to save values that we've seen before so that we can detect loops. Then we start a loop that goes until we converge on 1 or until we detect a loop. The heart of the program is the next line which (reading the methods left to right) a) converts n to a string, b) creates an array of the digits as strings using split, and finally uses inject to sum the squares of the digits (appropriately converted back to integers). If we detect a loop, the value that we generated is already in the visited hash, then we return false. If not, we add v to visited and set n to v for the next round. If we exit the loop with a 1, we'll return true.

Here's the code ...


# A function that determines whether a number passed in is a happy number or not. From Wikipedia:
#
# A happy number is defined by the following process. Starting with any
# positive integer, replace the number by the sum of the squares of its digits,
# and repeat the process until the number equals 1 (where it will stay), or it
# loops endlessly in a cycle which does not include 1. Those numbers for which
# this process ends in 1 are happy numbers, while those that do not end in 1
# are unhappy numbers (or sad numbers[1]).
#
def happy_number?(n)

# visited is a Hash that will keep track of numbers we've already found.
visited = {}

# Loop until we converge on 1 (or exit in the middle of the loop if
# we find a value that we've already visited.
while n != 1

# Convert n to a string, then split to get an array of characters. Use
# inject to calculate the sum of their squares and put it
# in v.
v = n.to_s.split(//).inject(0) { |sum, digit| sum += digit.to_i ** 2 }

# If we've already seen this value v, then we're in a
# loop and should return flase.
return false if visited.has_key? v

# Add v to the visited list
visited[v] = true

# Set n to v for next round.
n = v
end

# n is 1, so it's a original value was a happy number.
return true
end

# Place where we'll store the happy numbers
happy_numbers = []

# Find and save the happy numbers up to 500.
1.upto(500) do |i|
happy_numbers << i if happy_number?(i) == true
end

# Print out the happy numbers that we found.
happy_numbers.each { |n| puts "Happy number #{n}" }


If you have questions or comments, be sure to let me know.

Friday, July 9, 2010

RPN Calculator

Here's another one from Programming Praxis. It's an RPN (reverse Polish calculator) problem that I've chosen to implement in Ruby. The text from Praxis is the header comment of the program.

The first thing we do is open up the Array class and alias last with a new method called peek which returns the the last element of the array. Obviously, we could just use last, but the "norm" for stacks is peek. Next we actually create the stack using an Array. We could probably create our own stack with only the appropriate methods, but that's probably overkill for this little project (as I suppose you could argue creating peek is). Next, we'll just loop forever, printing a prompt,reading a line of text, and then processing it. The processing consists of taking a line apart and grabbing either a number, the first regular expression, or an operator, the second. For a number, we simply push it on the stack. For an operator, we pop the top two items off the stack and perform the operation on them. Then we push the result back on the stack. Finally, we strip whatever we just found, either number or operator, off the line and continue. When we finish processing the line, we print the top of stack and then continue on to the next line.

Here's the actual code


# Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3
# / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds
# with 85.2974. The program should read expressions from standard input and
# print the top of the stack to standard output when a newline is encountered.
# The program should retain the state of the operand stack between expressions.


# Open up the Array class so we can add a
# method to look at the "top of the stack".
class Array
alias :peek :last
end

# Create the stack we'll use for processing.
stack = Array.new
while true

# Print the prompt.
print ">> "

# Get the line to process and remove the trailing \n.
line = gets.chomp

while line.size > 0

# Check for a number first so that we don't grab a +/-
# and use it for an operator.
if line =~ /^\s*([-+]?[0-9]*\.?[0-9]+)\s*/
# Found an operand so we'll just push it
# on the stack after changing it to a float.
stack.push $1.to_f
elsif line =~ /^\s*([\+\-\*\/])\s*/ then
# The line has an operator (+/-*).
operator = $1

# Get the operands off the stack.
operand_2 = stack.pop
operand_1 = stack.pop

# Evaluate the expression and push it on to the stack.
stack.push case operator
when '+'
operand_1 + operand_2
when '-'
operand_1 - operand_2
when '*'
operand_1 * operand_2
when '/'
operand_1 / operand_2
end
end

# Replace whatever we just found with the empty string.
line.sub!($&, "")
end

# We've finished processing the line, so print out the
# top of the stack.
puts "Top of stack = #{stack.peek}"
end



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

Monday, July 5, 2010

World Cup Simulation

Here's another one from Programming Praxis. The goal is to simulate the world cup rounds using their calculations for winning expectation and thier elo values (read about their calculations). Here's the simulation:


class Team
include Comparable

attr_reader :symbol, :country, :initial_elo, :new_elo
attr_accessor :world_cup_wins

# Initialization of the team.
def initialize(symbol, country, initial_elo)
@symbol = symbol
@country = country
@initial_elo = initial_elo
@new_elo = initial_elo
@world_cup_wins = 0
end

# Defined for sorting.
def <=>(team_other)
@world_cup_wins <=> team_other.world_cup_wins
end

# Print out the team and a few statistics.
def to_s
"#{@symbol} #{@country} #{@initial_elo} Wins = #{@world_cup_wins}"
end

# Calculate the winning expectation between these two teasm.
def winning_expectation(team_other)
1.0 / (1.0 + 10.0 ** ((team_other.new_elo - @new_elo) / 400.0))
end

# Simulate a game based on the winning expectation between this team and
# the other team.
def game(team_other)
w_e = winning_expectation(team_other)
if rand <= w_e
# This team won so calculate appropriately the new elos.
calc_elo(w_e, 1.0)
team_other.calc_elo(w_e, 0.0)

# Return that this team won.
return true
else
# The other team won so calculate appropriately the new elos.
calc_elo(w_e, 0.0)
team_other.calc_elo(w_e, 1.0)

# Return that the other team won.
return false
end
end

# Reset the elo to the initial_elo for the start of a
# new simulation.
def reset_elo
@new_elo = initial_elo
end

# Calculate the elo based on the winning expectation and
# whether this team won or lost.
def calc_elo(w_e, win_loss)
@new_elo = @new_elo + 60.0 * 1.0 * (win_loss - w_e)
end
end

# Teams with their initial elo scores and ordered by the pairings (e.g. in the
# first round Uruguay will play Korea, and Spain will play Portugal.
initial_rankings = [

[ 7, "URU", "Uruguay", 1890],
[25, "KOR", "Korea", 1746],
[15, "USA", "United States", 1785],
[32, "GHA", "Ghana", 1711],
[ 3, "NED", "Netherlands", 2045],
[45, "SVK", "Slovakia", 1654],
[ 1, "BRA", "Brazil", 2082],
[ 8, "CHI", "Chile", 1883],
[ 4, "ARG", "Argentina", 1966],
[10, "MEX", "Mexico", 1873],
[ 6, "GER", "Germany", 1930],
[ 5, "ENG", "England", 1945],
[19, "PAR", "Paraguay", 1771],
[26, "JPN", "Japan", 1744],
[ 2, "ESP", "Spain", 2061],
[ 9, "POR", "Portugal", 1874],
]

# Create the teams array from the inital rankings above.
teams = Array.new()
initial_rankings.each do |r|
teams << Team.new(r[1], r[2], r[3])
end

# Each simulated World Cup
1.upto(1000000) do | sim |

# Start fresh by reinitializing the current_round with
# the teams and their elo.
current_round = teams
current_round.each { |t| t.reset_elo }

# Simulate the rounds
while current_round.size > 1 do
# Create the array where we'll store the winners for the next round.
next_round = Array.new

# Loop through the round 2 at a time. The winner will get stored in the next_round array.
i = 0
while i < current_round.size
# Add the winner to the next round.
next_round << (current_round[i].game(current_round[i+1]) ? current_round[i] : current_round[i+1])
i += 2
end

# Save the current round as the next round.
current_round = next_round
end

# Add to the winner's total.
current_round[0].world_cup_wins += 1
end

# Sort by the number of wins and then print out the counts.
teams.sort!
teams.each do | t |
puts "team: #{t} "
end



It should be commented well enough for you to figure everything out (assuming you also read the explanation over at Programming Praxis), but if you have any questions or comments, don't hesitate to ask.

Thursday, July 1, 2010

Sequel Trees

Edit: Jeremy Evans had a couple of suggestions which I've made in the code below. Use a real foreign key for the parent_id,use a portable text column, and finally don't give a parent_id for the root (Alice) of the tree.

In Sequel 3.13.0, Jeremy Evans has added a few new plugins. Most interesting to me was the one for trees, so I'm going to outline how to use it here.

Here's a program that sets up and uses an employee/manager tree structure. We do our normal set up of the database, create the model (including adding the :tree plugin), and create a few employees. Finally, we run through a few of the common tree functions. The code is pretty well commented, so I'll present it and you can ask questions if you have any.


require 'rubygems'
require 'sequel'

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

# Create the employees table with a name and parent_id.
DB.create_table :employees do
primary_key :id
foreign_key :parent_id, :employees
String :name, :text=>true, :unique=>true
end

# Create the Employee model.
class Employee < Sequel::Model
plugin :tree # Uses :parent_id field for parent
end

# Create the top level employee
alice = Employee.create(:name => "Alice")

# Create Alice's direct reports
bob = Employee.create(:name => "Bob", :parent_id => alice.id)
charlene = Employee.create(:name => "Charlene", :parent_id => alice.id)
dave = Employee.create(:name => "Dave", :parent_id => alice.id)

# Create Charlene's direct reports
ellen = Employee.create(:name => "Ellen", :parent_id => charlene.id)
frank = Employee.create(:name => "Frank", :parent_id => charlene.id)

# Find the top level employee for Ellen
president = ellen.root
puts "Ellen's president: #{president.name}"

# Find Ellen's management chain.
managers = ellen.ancestors
managers.each do | a |
puts "Ellen's manager: #{a.name}"
end

# Find Charlene's coworkers.
coworkers = charlene.siblings
coworkers.each do | s |
puts "Charlene's coworker: #{s.name}"
end

# Find Charlene's coworkers and Charlene.
self_coworkers = charlene.self_and_siblings
self_coworkers.each do | s |
puts "Charlene's coworker (or Charlene): #{s.name}"
end



Let me know if you have any questions or comments.

Saturday, June 26, 2010

The N Queens Problem in Ruby

The N Queens Problem was posed recently over at Programming Praxis. This is a pretty classic problem and typically uses a recursive solution. Here's what I came up with as a ruby solution.


# We present today a classic exercise that has been on my to-do list since the
# start of Programming Praxis.
#
# The n-queens problem is to find all possible ways to place n queens on an n ×
# n chess board in such a way that no two queens share a row, column, or
# diagonal. The diagram at right shows one way that can be done on a standard 8
# × 8 chess board.
#
# Your task is to write a program to find all such placements. 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.

class Board

# Create a new board, initialize with with all "b" and
# save the size of it.
def initialize(n)
@n = n
@board = Array.new(n)
@board.map! { Array.new(n, "b") }
end

# Print the current board.
def print_board
puts "Board:"
@board.each_index do |row|
@board.each_index do |col|
print "#{@board[row][col]}"
end
puts
end
end

# Check if the row is safe by looping through each of the
# columns in the row.
def safe_row(suggested_row)
0.upto(@n-1) do |col|
return false if @board[suggested_row][col] == "Q"
end

return true
end

# Check if the column is safe by looping through each of the
# rows in the row.
def safe_col(suggested_col)
0.upto(@n-1) do |row|
return false if @board[row][suggested_col] == "Q"
end

return true
end

# Loop through in one diagonal direction to determine if the
# suggested row and column are safe.
def safe_diag(suggested_row, suggested_col, row_mod, col_mod)
row,col = suggested_row+row_mod, suggested_col+col_mod
while true do

# Break out of the loop if the row or column is off the board.
break if (row >= @n) || (col >= @n) || (row < 0) || (col < 0)

# If this row or column has a queen, then it's not safe.
return false if @board[row][col] == "Q"

# Move in the appropriate direction.
row += row_mod
col += col_mod
end

# This direction is safe.
return true
end

def safe(suggested_row, suggested_col)

# Check the rows and columns for safe.
return false if !safe_row(suggested_row)
return false if !safe_col(suggested_col)

# Check the diagonals for safe.
return false if !safe_diag(suggested_row, suggested_col, 1, 1)
return false if !safe_diag(suggested_row, suggested_col, 1, -1)
return false if !safe_diag(suggested_row, suggested_col, -1, 1)
return false if !safe_diag(suggested_row, suggested_col, -1, -1)

# Should be OK.
return true
end

# Solve the n-queens problem by making a call to the recursive solve_1
# method with 0 (the first row of the board) to start.
def solve
solve_1(0)
end

# The recursive method (by row) that loops through the columns and checks
# if the row given and the column are "safe". If they are we add a "Q" to
# the position and if the row is 0, we print it out (everthing is
# complete). If it's safe adn we aren't at 0 we move to the next row
# recursively. Finally, we reset the position to "b" (blank) when we
# return from the recursive call or from printing the board. If it's not
# "safe" then we just move to the next column and try that one.
def solve_1(row)
0.upto(@n-1) do |col|
if safe(row, col)
@board[row][col] = "Q"
if row == (@n-1)
print_board
else
solve_1(row+1)
end
@board[row][col] = "b"
end
end
end
end


# Solve the problem for 8 queens. There should be 92
# solutions.
board = Board.new(8).solve


I've put quite a few comments in there, but if you have questions, don't hesitate to ask.

Wednesday, June 23, 2010

Simple Webrick Server and shjs Syntax Highlighting

Since I've upgraded my machine, maruku hasn't been able to do syntax highlighting for me. I'm now giving shjs a shot. Here's a simple webserver using webrick.


# Get webrick
require 'webrick'
include WEBrick

# Create the server.
server = HTTPServer.new(:Port => 9090, :DocumentRoot => Dir::pwd)

# Shutdown if we get an interrupt.
trap("INT") { server.shutdown }

# Start the server
server.start


Not to much going on here. We get webrick included and create the server. The port here is 9090 (obviously you can pick any one that you want). The HTML files will be served from the current directory and this can be modified also. Then we shut down the server when we see a ^C and finally, we start the server.

I actually lifted this from somewhere and forgot to grab the link to give credit. If it's yours or you know who's it is, let me know so I can acknowledge them.

Let me know if you have questions.

Sunday, May 30, 2010

145 Puzzle

I've just started reading a blog Praxis that features programming problems to solve and shows their solutions typically in scheme. You're encouraged to submit your own solutions there to for others to look examine. The ones that come from Bonsai Code in Haskell are nothing short of amazing in their brevity.

Anyway, one I've solved is the 145 puzzle. Here's the description from Praxis ...
Form all the arithmetic expressions that consist of the digits one through nine, in order, with a plus-sign, a times-sign, or a null character interpolated between each pair of digits; for instance, 12+34*56+7*89 is a valid expression that evaluates to 2539. What number is the most frequent result of evaluating all possible arithmetic expressions formed as described above? How many times does it occur? What are the expressions that evaluate to that result?
.

So here's my solution in Ruby:


#
# Consider this math puzzle:

# Form all the arithmetic expressions that consist of the digits one through
# nine, in order, with a plus-sign, a times-sign, or a null character
# interpolated between each pair of digits; for instance, 12+34*56+7*89 is a
# valid expression that evaluates to 2539. What number is the most frequent
# result of evaluating all possible arithmetic expressions formed as
# described above? How many times does it occur? What are the expressions
# that evaluate to that result?
#
# Your task is to answer the three questions. 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.

# Multi-combination. Takes the elements to combine, a "level" (how many ways
# will we do the combination), the current multi-combination, and a block that
# we'll yield to.
def mc(elements, level, current=[], &block)
elements.each do | e |
if level == 1 then
yield current << e
else
mc(elements, level-1, current << e, &block)
end
current.pop
end
end

# Main program.
digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']

# DON'T initialize the hash with "[]" (as I initially did). You'll end up with
# the same array in every hash position.
results = Hash.new()

# Generate each multi-combination in the 8 spots (between each of the digits.
mc(['*', '+', ''], 8) do | operators |

# Initialize the string to evaluate.
eval_string = ''

# Add the digits and operators to the eval_string.
0.upto(digits.length-2) { |i| eval_string << digits[i] << operators[i] }

# Add teh final digit.
eval_string << digits.last

# Evaluate the string and save the result in the hash. Create a new array
# if one doesn't exist at this position.
(results[eval(eval_string)] ||= []) << eval_string
end

# Get the results that occur the most times.
m = results.max { |a, b| a[1].length <=> b[1].length }

# Print out the answer.
puts "Most evaluated number = #{m[0]} Number of times evaluated = #{m[1].length} values = #{m[1]}"


Let me know if you have questions and take some time to explore Praxis and solve some of the problems yourself.

Thursday, May 27, 2010

Installing Ubuntu, Ruby, Ramaze, Sequel, Vim, and More on an HP dm3-1130us

Sorry for not posting recently. My trusty Sony VAIO passed away and I've been getting my new box, an HP dm3-1130us running Linux with all the tools that I normally use. I thought I'd document it in case anyone else needed to do it. To be honest, most of this should work on any system not just mine or even an HP. Here are the steps:
  • Create boot disks. Use the Recovery Manager.
  • Use http://unetbootin.sourceforge.net/ to create a bootable USB device.
  • Plug the USB drive in, reboot, and hit ESC (multiple times).
  • Select the USB device to boot
  • Ubuntu should load. Pick your name, language keyboard, time zone, and password (I think these are all that are asked for)
  • Install flash - sudo apt-get install flashplugin-nonfree
  • Add the following add ons to Firefox (you may have different favorites)- Colorful Tabs, Faviconize, Vimperator
  • Install Ruby 1.9 - sudo apt-get install ruby1.9.1-full (will load executable ruby1.9.1)
  • Create a symbolic link for ruby - sudo ln -s /usr/bin/ruby1.9.1 /usr/bin/ruby
    Install 7zip - sudo apt-get install p7zip
  • Install gvim - sudo apt-get install vim-gnome; Create an application launcher
  • Name-gvim Location-/usr/bin/gvim Change the icon to /usr/share/pixmaps/vim.svg
  • Install Ruby gems - sudo apt-get install rubygems1.9.1
  • Install mailit mail package for ruby - sudo gem install mailit
    Install gemcutter (A replacement for SourceForge and gethub as gem repositories) - sudo gem install gemcutter
  • Install sequel - sudo gem install sequel
  • Install sqlite3 - sudo apt-get install sqlite3 libsqlite3-dev
  • Install sqlite3-ruby gem - sudo gem install sqlite3-ruby
  • Install ramaze - sudo gem install ramaze
  • Put sequel into /usr/bin - sudo ln -s /var/lib/gems/1.9.1/bin/sequel /usr/bin
  • Put ramaze in /usr/bin - sudo ln -s /var/lib/gems/1.9.1/bin/ramaze /usr/bin
  • Add the sqlite manager to Firefox - https://addons.mozilla.org/en-US/firefox/addon/5817/
  • Download snipmate.vim - http://www.vim.org/scripts/script.php?script_id=2540
  • Unzip snipmate.zip from ~/Downloads - unzip snipMate.zip -d ~/.vim
  • Install irb *and* removed unused packages - sudo apt-get install irb1.9; sudo apt-get autoremove
  • Be able to use matchit (match ruby do/end etc.) in vim (may want to look at vim-addons for Debian/Ubuntu) - set rtp+=/usr/share/vim/addons/ (in the .vimrc file)
Vimperator is a Firefox add-on that if you use vim, you absolutely need. It makes Firefox behave like vim ("j" scrolls down, "k" scrolls up, etc.). For vim itself, you need to look at snipmate. It provides snippets (similar to TextMate I believe) and it will make your Ruby programming life much easier. The final step, for matchit, is a bit of a hack and you probably want to investigate the vim-addons tool which from my quick glance, looked like a gem type thing for vim add ons.

I'm keeping a list of everything I do system wise on this machine. I discovered that for the most part I had a ton of stuff that I wasn't using and sometimes had no idea what it was.

So, let me know if you have any questions or comments.

Wednesday, April 21, 2010

Passing Classes as Parameters

I've been playing around with genetic algorithms again and I'll post my work a bit later. But, I did realize something while I was doing it that I thought was interesting and completely makes sense, but I hadn't seen discussed anywhere before (that I remember anyway). You can actually pass Classes as parameters to methods, including initializers. Why's this interesting? It allows you to create factories and then pass those factories to other classes. Here's a very simple example, using my genetic algorithm terminology of Organisms.

# Create a basic organism.
class Organism
def speak
puts "I'm a basic organism"
end
end

# Derive an organism that modifies the speak method.
class OrganismOther < Organism
def speak
puts "I'm another organism"
end
end

# Create a "factory" that take a Class as a parameter and can
# generate organisms of that class.
class OrganismFactory
def initialize(organism_class)
@organism_class = organism_class
end

def generate_organism
@organism_class.new
end
end

if __FILE__ == $PROGRAM_NAME

# Create a basic and other factory for the two types of organisms.
organism_factory_basic = OrganismFactory.new(Organism)
organism_factory_other = OrganismFactory.new(OrganismOther)

# Generate an organism of each type.
organism = organism_factory_basic.generate_organism
organism_other = organism_factory_other.generate_organism

# Let them speak.
organism.speak
organism_other.speak
end



You can see that we create a basic Organism and then subclass it to get a slightly different organism. There's nothing too awfully interesting there. Next is the OrganismFactory where we show off our new technique. The initialize() method takes a Class as a parameter and saves it away in the @organism_class variable. We also have a method generate_organism() that will return an object of the type that was passed in. Finally, we have the main program that creates a couple of factories, one of each type, and then uses them to create objects of each type. Finally, we make sure they work by having them "speak".

Let me know if you have questions or comments on this.

Monday, March 22, 2010

Metaprogramming Ruby - Review

I wrote a review of Metaprogramming Ruby by Paolo Perrotta and much to my surprise, Slashdot published it. You can find it here. Feel free to post comments and thoughts.

Wednesday, February 17, 2010

Ruby and Simple Dynamic Programming V

I've been reading Paolo Perrotta's new book "Metaprogramming Ruby" recently and enjoying it thoroughly. In the first chapter, he talks about Monkey Patching, the ability to add methods to classes at runtime. This combined with a need recently for an iterator through an array that returns both the index and the value led me to come up with the following code:

# Open the Array class and add a new method "each_with_index".
# This will loop through the array using the each_index method
# and yeild the index and the value of the array at that index.
class Array
def each_with_index
self.each_index do | i |
yield i, self[i]
end
end
end

if __FILE__ == $PROGRAM_NAME

# Create a simple array
x = [ "hello", "world", 42, 3.14159, ["test", "an", "array"] ]

# Go through the array and print each index and value in the
# array.
x.each_with_index do | i, v |
puts "index = #{i} value = #{v}"
end


end



The code is pretty simple. We open the Arrary class, define the new method, and then close the class. There's a bit of test code after that to show that everything works as expected.

Even though I'm only through the first chapter, I can recommend Perrotta's book. It's an easy read (so far anyway) and clearly shows the concepts that it discusses. The form it takes is conversational and the narrative is that you're a programmer, new to Ruby, who is paired with a senior developer Bill. This format may not be for everyone, especially if you're looking for more "formality", but I think it works well here and it's not overdone.

Let me know if you have questions or comments.

Wednesday, February 10, 2010

Beginning a Program

A young friend (YF) of mine was having a problem with a programming assignment from a large local university (LLU) and gave me a call the other day for some help. We spent a couple of hours together going through the piece that he was having issues with and finally got everything pretty much working. This episode though showed me that we don't necessarily teach the right things in college concerning how approach a program. I thought I'd take a few posts and show how I might tackle a problem like this. Not everyone will find this way of doing things appropriate and I wouldn't use it in certain cases, but it may help some of you in some cases.

Here's the problem as given:


Assignment Details
Homework 1 - Non-GUI Tower Defender
Players start with a fixed amount of money, in less they are a returning player. In that case, they are to start with the money they ended up with, or they can start over, if they wish.

Towers:There are to be 4 types of towers. Each has a different capability - you get to decide. Each has a different price - that you decide. A player starts the game by deciding which towers they want and where they are to be put. Given that the path for Creeps is only from left to right, towers can be above, or below, the path. The player gets to decide that, and the "x-direction" for the tower location.

Since this first assignment is not graphical - only command line - the Creep path is straight from left to right. You are to use keyboard characters as your graphics to display what is happening - tower location, and Creep location.

Creeps:Creeps may move one, or more, squares, from left to right each "turn". You get to decide how big squares are. Too big, and Creeps will easily get to the base - which is on the right side of the window. Creeps start from the left side of the display window. You are to have three (3) types of Creeps. Their behavior is up to you, but just moving faster, or slower, does not qualify as a different Creep type. Each Creep is worth a different amount of money - depending on how hard they are to kill.

Statistics: You are to track the number of Creeps killed (for each Creep type), the total number of times this player has played, the total amount of money they have spent, and the total amount of money they have earned. You may choose to have additional statistics.


There are a few things here that are worth noting. First the requirements are pretty loose. You have some options for doing things how you like (this may be good or bad depending on your temperament. Second there are a couple of things that don't make sense. We have the "x-direction" for the tower location. I'm pretty sure that what's meant is the "x-position", but if I were doing this for a grade at LLU, I'd check with the prof. I checked with YF and it sounds like since the towers don't move, the x-position is what is meant.

As a first cut, I'd spend my time working on the "logistics" of the program. What do I mean by that? Well, we'll have a main program that loops getting input from a player. We're going to have to create a player, give her some money, be able to save her totals when she quits, and on initialization, we're going to have to check if she's played before and if so if she'd like to resume or start a new game.

With that out of the way, here's what I came up with (this is in Ruby, YF for LLU had to write this in Java).

# Assignment Details Homework 1 - Non-GUI Tower Defender Players start with a
# fixed amount of money, in less they are a returning player. In that case,
# they are to start with the money they ended up with, or they can start over,
# if they wish.
#
# Towers: There are to be 4 types of towers. Each has a different capability -
# you get to decide. Each has a different price - that you decide. A player
# starts the game by deciding which towers they want and where they are to be
# put. Given that the path for Creeps is only from left to right, towers can be
# above, or below, the path. The player gets to decide that, and the
# "x-direction" for the tower location.
#
# Since this first assignment is not graphical - only command line - the Creep
# path is straight from left to right. You are to use keyboard characters as
# your graphics to display what is happening - tower location, and Creep
# location.
#
# Creeps: Creeps may move one, or more, squares, from left to right each "turn".
# You get to decide how big squares are. Too big, and Creeps will easily get to
# the base - which is on the right side of the window. Creeps start from the
# left side of the display window. You are to have three (3) types of Creeps.
# Their behavior is up to you, but just moving faster, or slower, does not
# qualify as a different Creep type. Each Creep is worth a different amount of
# money - depending on how hard they are to kill.
#
# Statistics: You are to track the number of Creeps killed (for each Creep
# type), the total number of times this player has played, the total amount of
# money they have spent, and the total amount of money they have earned. You
# may choose to have additional statistics.
#

class Tower
end

class Creep
end

class Game
end

class Player

# Initialize a player.
def initialize(name)
@name = name
@dollars = 100
@file_name = "#{@name}.txt"

if File.exist?(@file_name)
print "Welcome back #{@name}. Would you like to resume(r) or start a new game(n)?"
command = gets.chomp
case command
when "r"
puts "Resuming from #{@file_name}"
File.open(@file_name, "r") do |player_file|
line = player_file.gets
if line != nil
name_f, @dollars = line.split(",")
puts "Resume: #{name_f}: Dollars" #{dollars_f}"
else
puts "Could not read line"
end
end
when "n"
puts "Starting new game"
end
end

end

# Save the players and stats to a file.
def save
player_file = File.new(@file_name, "w+")
player_file.puts "#{@name}, #{@dollars}"
player_file.close
end

# Convenience funtion to get the player and their current
# stats.
def to_s
"name: #{@name}, dollars: #{@dollars}"
end

end

if __FILE__ == $PROGRAM_NAME

# Get the player name
print "Name: "
name = gets.chomp

# Create a new player
player = Player.new(name)
puts "#{player}"

# Do forever (or until a 'q' command anyway)
while true do

# Get the command
print "Command: "
command = gets.chomp

# Check the command and execute it.
case command
when "q"
# Quit so go ahead and save the player then break out
# of the loop.
player.save
break
end
end
end



You can see that I put the requirements at the top so they're pretty much always available for checking (you obviously can't do this with really big requirements, but when you can, it's not a bad idea). There are place holders for the classes that I think we'll have, but those may change. The one that's filled out, the Player class, has just three methods. initialize(), sets the player up and checks if the do/don't already have a saved game, save() saves the players current data, and to_s() let's us print out their data in a readable format. As we go along, these may (really will) change and get refactored, but for now, they'll suffice. The main program asks the user for their name and creates a player. We then start the main loop that just gets a command (here only the quit command) and processes it. Quit simply saves the players data and breaks out of the loop which then exits.

This would probably take less than 1/2 an hour for someone who knows the language they're working in fairly well. What is does though is provide us with places to hang major pieces of the game going forward.

Let me know if you have questions or comments and look for the next edition where we'll add in a bit more functionality to the program.