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.

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.

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.

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.

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.