SteamCode

Rails / Ajax / Autocomplete

2012-01-29T16:34:00.000-08:00

As you all know if you're regular readers here, I started out in the Ruby web framework world with Ramaze and I'm definitely glad that I did. However, it doesn't seem like there's much of a job market for Ramaze programmers, so I've taken up using Rails, specifically Rails 3.1. There's a number of great books for Rails and the one I'd recommend is Ruby on Rails 3 Tutorial by Michael Hartl. In this book, he develops a Twitter like application in Rails starting with basic pages and moving on to more complex topics.

I've been working on a simple project for a greeting card application and I came up with a little something that might be interesting. The cards have a recipient and can have multiple signers. I added autocomplete for the recipient, but it was a bit harder for the comma separated list of signers. What I ended up doing was was simply grabbing the last piece of the list in the controller and passing that back to the view.

Here's the view code ...


 Create a Card 

<%= image_tag "card_images/#{@template.image_name}", :size => "200x200" %>
<%= form_tag ("create_from_image") do %>

    <%= label_tag("Add the recipient's email: ") %>
    <%= text_field_tag(:recipient_email, "#{@recipient_email}")%>


    <%= label_tag("Add A Greeting: ") %>

    <%= text_field_tag(:greeting, "#{@greeting}")%>


    <%= label_tag("Add the signers' emails (comma separated): ") %>

    <%= text_field_tag(:signers_email, "#{@signers}")%>


    <%= hidden_field_tag :template_id, @template.id %>

    <%= submit_tag("Preview the card!") %>
    <%= submit_tag("Send the card!") %>
<% end %>

There's nothing very interesting in here, but the main field we're interested in is the :signers_email text field.

Here's the javascript code for it ...


$(document).ready(function(){
    // Below is the name of the textfield that will be autocomplete
    $('#recipient_email, #signers_email').autocomplete({
        // This shows the min length of charcters that must be 
        // typed before the autocomplete looks for a match.
                    minLength: 2,
        // This is the source of the auocomplete suggestions. In this case a 
        // list of emails from the users controller, in JSON format.
                    source: '/users/index.json'
    })

});

What this says is that for both the recipient_email and signers_email fields, use autocomplete, send when we have two characters, and use the /users/index.json function to get the data we need.

Finally, we have the controller code ...


    def index
        @title = "All users"
        @suggestion = "Pick someone and send them a card!"
        if params[:term]
            search_term = params[:term].split(",").last.strip
            @users = User.find(:all, :conditions => ['email LIKE ?', "#{search_term}%"])
            @users_hash = []
            @users.each do |user|
                @users_hash << { "label" => user.email }
            end

        else
            @users = User.where(:active => true).paginate(:page => params[:page])
        end

        respond_to do |format|
            format.html

            # Here is where you can specify how to handle the request for "/people.json"
            format.json { render :json => @users_hash }
        end
    end

Here, we have a couple of things going on ... for the Ajax side, we'll get the params[:term] field so we know that we need to get the constrained list. First, we're going to grab the params[:term] value, which should look something like "abc@test.com, def". Here we'd like to look for emails that start with the "def" and ignore the "abc@test.com" piece. So ... we split on the comma, grab the final element in the array, and then remove any leftover spaces at the end or beginning of the string. Next, we'll create an array where each element is a hash of the form { "label" => "defghi@test.com" }. This is the form that the jquery autocomplete needs. Finally, we use the respond_to section to send this back as json.

As always, let me know if you have questions.

Majority Voting

2011-12-18T18:22:00.000-08:00

I saw this one over at Programming Praxis. It's pretty simple with ruby, but there's one slightly interesting piece in there that might come in handy sometime. Here's the code ...


def majority(l)
    h = Hash.new(0)
    l.each { |v| h[v] += 1 }
    max = h.max {|a,b| a[1] <=> b[1]}
    max[1] >= l.length / 2.0 ? "#{max[0]} won with #{max[1]} out of #{l.length} total votes" : "No winner"
end

v1 = %w[A A A C C B B C C C B C C]
v2 = %w[A B C A B C A]

puts "v1 = #{majority(v1)}"
puts "v2 = #{majority(v2)}"

OK, so we create a Hash where the value in the key/value pair is initialized to 0 and we add one each time time we see a vote. Here's the cool part, we use the max function from Enumerable knowing that max itself uses each which will give us the key/value pair as a two element array. So, we set the function to compare the second element, the value, of the pair. The max that gets returned will also be a two element array and we use that to calculate whether there's a winner or not.

These types of problems are great for sharpening your programming skills in general and your ruby skills in particular. They're exactly the types of questions that end up on programming interview tests.

Let me know if you have questions or comments.

Centroids

2011-11-14T19:52:00.000-08:00

Here's another one from my clustering code, slightly modified for explanatory purposes. This post was spurred by a conversation with a couple of friends when we were talking about programming, who said that programming languages mostly had the same things (i.e. everything old is new again). While I'm not completely in opposition to that, I think that some of the newer languages (read Ruby) do have a lot to offer when it comes to compactness.

Here the problem is to find the centroid of a number of points. Basically, we want the averages of all the first values of the points, the second values of the points, etc. Let's show an example ...

If we have [[x0, y0, z0], [x1, y1, z1], ... [xn, yn, zn]] as our points then the centroid would be the point given by [sum(x's) / n, sum(y's)/n, sum(z's) / n] (and here I'm too lazy to figure out how to create the capital Sigma for sum). Think about how you might solve this in your favorite programming language. In C/C++ anyway, you'd need to know in advance how many points and how many dimensions (the example above uses three, but it could be more or less). In Java, you don't need that, but I don't think you could do something like this ...


    def centroid(x)
        x[0].zip(*x[1..x.length-1]).map { |v| v.inject(:+) / v.length.to_f }
    end

OK, so what's going on here? First up we're going to take the first element of the array (above the [x0, y0, z0]) and zip it with the rest of the array with *x[1..x.length-1]. This should give us, once again from the example above [[x0, x1, ...xn], [y0, y1, ... yn], [z0, z1 ... zn]]. So basically, a new array with all the x's gathered together, the y's, etc. Now comes map. Here, we'll take each element, which is itself an array and then use inject to run through each of the items, say [x0, x1, ... xn] and sum them together. Finally, we'll divide by the length of the element to get an average. If it's hard to see this, break it into pieces and then run it through using irb. It should be a bit easier to see there.

So, what's the point here. Well, essentially you could this in any programming language or in fact any Turing machine, but the language itself can make it easier freeing you to do other things or harder.

Let me know if you have any questions or comments.

Monty Hall Problem

2011-11-11T13:45:00.000-08:00

A friend of mine got asked this question in an interview yesterday and I thought it'd make an interesting programming problem. It goes something like this ... Suppose you're on a game show and are offered the choice of one of three doors. Behind one of the doors is a car and behind the other two are goats. Let's say you choose door number three (see Jimmy Buffet song). At this point Monty Hall shows you that behind door number one is a goat and offers to let you switch to door number two. The question is, should you do it? The easy (and incorrect answer) is that it doesn't matter. The correct answer is that, yes you should. Why? I'll let you look it up or you can just run the following program ...


possible_doors = [:goat, :goat, :car].permutation.to_a
bad_choice = 0
tries = 100000
1.upto tries do |mc|
    test_doors = possible_doors[Random.rand(possible_doors.length)]
    bad_choice += 1 if test_doors[Random.rand(test_doors.length)] == :car
end
puts "bad_choice percent = #{bad_choice.to_f / tries.to_f * 100} good_choice percent = #{100.0 - (bad_choice.to_f / tries.to_f * 100)}"

First up, we get a list of all the possible ways the doors could be arranged and set the number of times that switching would be a bad choice to 0. We'll run this 100000 times in a Monte (not Monty) Carlo loop. In the loop we get one of the possible arrangements of test doors randomly selected and then increment the bad_choice variable if the door we pick contains the car (in other words switching from where we are would be a "bad choice"). When we run this program we see that switching is a bad choice only about 33% of the time and a good choice about 66% of the time (one might guess that these are really 33.333333...% and 66.6666666%). So, then answer in this case is that yes you should switch.

Let me know if you have questions or comments.

Ruby Distance Calculation

2011-11-01T18:30:00.000-07:00

I was just looking at a clustering algorithm and needed a distance calculation between two points in n-dimensional space. If you remember your high school geometry (or even earlier) the distance between two points in the xy plane is the sqrt((x1 - x2)**2 + (y1-y2)**2). Where the two points are represented by (x1, y1) and (x2, y2). For more dimensions, just add values inside the sqrt as in (z1-z2)**2 for a third dimension. Given that here's a one line function that I came up with


def distance(a, b)
    Math.sqrt(a.zip(b).inject(0) { |d, c| d + (c[0] - c[1]) ** 2 })
end

It's a bit tricky, so let's go through it. First we have the Math.sqrt which will just take the square root of whatever is inside it. Next the a.zip(b) will take two arrays (here the input parameters) and take the first values of each of the arrays, create a new array from them and then add that to the output array (see also this post for more information on zip). Same with the second values of the arrays and so on. For example if we have [x1, y1, z1].zip([x2, y2, z2]) this will return [[x1, x2], [y1, y2], [z1, z2]] (hopefully, this looks like something we can use to you). Next we're going to use inject to run through this array with a starting value of 0 (d) and add to it the square of the difference of the two values in the array. Finally as noted before, take the square root and return.

If you have any problems with this, break it up into multiple lines and check the intermediate values. As always, let me know if you have any questions.

Heaps

2011-10-05T18:35:00.000-07:00

I noted in my last post that I had a technical phone interview. When it was scheduled, the HR person told me that it would include "data structures, algorithms, and architecture". I decided that it wouldn't be a bad idea to review a bit and so I got a copy of Steven Skiena's "The Algorithm Design Manual" and started rummaging through it.

One of the data structures that I came across was a heap (as in heapsort if you've forgotten). A heap is a binary tree data structure that has the property that the parent is smaller for a min-heap or larger for a max-heap than its children. They can be used for priority queues as the minimum or maximum is always at the top of the heap or for sorting assuming that you a) take the top element and then b) recalculate the tree.

The code here follows Skiena's pretty closely excepting he starts his array at 1 and I use the more natural (for me anyway) 0 start. This code also implements only a min-heap, but you should take a bit of time to see if you can figure out how to make it either a min-heap or a max-heap as an initialization parameter. A couple of other things aren't that pretty (extract_min! in particular bugs me), but mostly it's not bad and is straight forward.

So ... here's the code


class Heap
    def initialize(a)
        @q = []
        a.each { |v| insert(v) } if a
    end

    def parent(n)
        n == 0 ? -1 : (n-1) / 2
    end

    def young_child(n)
        (2 * n) + 1
    end

    def insert(v)
        @q << v
        bubble_up(@q.size-1)
    end

    def bubble_up(n)
        return if parent(n) == -1 # Root of heap, no parent 
        if @q[parent(n)] > @q[n]
            swap(n, parent(n))
            bubble_up(parent(n))
        end
    end

    def swap(n, pn)
        @q[n], @q[pn] = @q[pn], @q[n]
    end

    def min
        @q.first
    end

    def extract_min!
        m, @q[0] = @q.first, @q.last
        @q.pop
        bubble_down(0)
        m
    end
 
    def bubble_down(n)
        c = young_child(n)
        min_index = n

        0.upto(1) { |i| min_index = c+i if ((c+i) <= @q.size-1) &&(@q[min_index] > @q[c+i]) }

        if (min_index != n)
            swap(n, min_index)
            bubble_down(min_index)
        end
    end

    def sort!
        a = []
        while v = extract_min! do a << v end
        a
    end
end

h = Heap.new([12, 14, 6, 10, 8, 27, 1, 4, 9])
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "min = #{h.min}"
puts "min = #{h.min}"
puts "sort! = #{h.sort!}"

Let me know if you have any questions or comments and if you make improvements, post those too.

Phone Interview - 1

2011-10-04T10:10:00.000-07:00

I had a phone interview with a great company yesterday and thought I'd share some of the questions, my answers, what I think might have been better answers, and some additional potential questions that might have been asked. First, this was for a manager position and the fact that they're asking technical questions as part of the interview process and as the first interview really impressed me. It shows that they value technical abilities and respect their engineers and developers enough to hire managers that are technically capable as a top priority. We started out, as is usually the case with a bit of small talk about myself, the interviewer, and the company. Nothing too interesting there. I don't recall the actual order of the questions, but I think I got them all.

1. What are horizontal and vertical scaling? Here I knew what horizontal scaling was, but I don't believe I've heard the term vertical scaling. Horizontal scaling means adding more servers to give more processing power while vertical scaling (as I learned when I looked it up) is beefing up the capabilities of an existing server by adding say memory, CPUs, or CPU power. A reasonable follow up to this would have been to discuss the advantages and disadvantages to each.

2. What is object oriented programming? Here I discussed encapsulation and inheritance. I probably should have mentioned polymorphism and message passing. The Wikipedia article is pretty decent and wouldn't be a bad place to do a high level review for this sort of question. I was a little surprised that I didn't get a question on a specific problem. I always would as someone to list out objects and methods for a card game or for a file system (stolen I believe from Steve Yegge if I remember correctly).

3. Given an unsorted list, how would you find a duplicate element. This one was interesting because it had recently appeared on Programming Praxis. I solved it there and used a hash table. The idea is to run through each element of the list and put it on the hash table. If when you go to put it on the hash table, there's something already there, then you've found the duplicate and should return it.

4. In the above question, what's the complexity using Big O notation. Here, since we're running through the list just once, it should be O(n) where n is the size of the list.

5. How does a hash table work or how is it implemented "under the hood"? There are actually a couple of ways of implementing hash tables. I gave the answer of an array of linked lists. You have an array of size n and then use the element that you're going to put on the table to generate a hash value using a hash function. Then use this mod n and add it to the linked list that's at that element.

6. How would you count the number of 1's in an integer? This is pretty classic. Probably the easiest is to use a shift/and technique. You would "and" the value with "1" and if it's non-zero (actually it'll be 1) then add one to the bit count. Shift right and repeat until the value is 0.

7. The final question was about Design Patterns and whether I knew about them and why they're useful. My response was that they're useful in that they give us a way to discuss our designs with a common language. People were using design patterns before the GoF book, but they codified the patterns and gave them names. This makes it much easier to talk about these things.

I think that was all of the questions. We then talked a bit about the position and the company in general. As I said, I was very impressed with them and their "corporate culture".

So ... what sorts of things do you ask or have you been asked in technical phone interviews? Anything interesting or unique? Let us know in the comments.

Tetrahedral Numbers

2011-09-13T20:03:00.000-07:00

Here's another one from Programming Praxis this one on tetrahedral numbers. I'll leave you to read the description and just jump straight into the ruby solution. The interesting thing here is to use a lambda to create a method that we can pass around. Here's the entire program ...



def linear(target, f)
    n = 1
    while ( f.call(n) != target)
        n = n + 1
    end
    n
end

def binary(target, f)
    low, high = 1, 2
    while (f.call(high) < target) do high = high*2 end
    mid = (high + low) / 2
    while (fmid = f.call(mid)) != target do
        fmid < target ?  (low, mid = mid, (mid + high) / 2) : (high, mid = mid, (low + mid) / 2)
    end
    mid
end


tetrahedral = lambda { |n| n * (n + 1) * (n + 2) / 6 }

1.upto(10) { |i| puts tetrahedral.call(i) }

puts linear(169179692512835000, tetrahedral)
puts binary(169179692512835000, tetrahedral)

We start out with two methods linear and binary which are pretty straightforward with the exception that both take a function (in this case f) as a parameter. For linear, we start at 1 and continue calling f until the value of f(n) is the same as target. binary is similar, but here we keep doubling the high value until we're above the target and then we calculate the fmid and use it as a high or low value until we converge.

The tetrahedral function itself is created with a lambda so that we can pass it to the other two methods. The next lines are simply tests. Note how much longer the linear method takes than the binary.

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

Two String Exercise via Programming Praxis

2011-09-03T17:10:00.001-07:00

Here's another one (or two rather) from Programming Praxis. Let's take a look at the second one first as it's trivial in ruby. If we're given a string, how do we replace multiple spaces with single spaces. F/or example the string

"a    b       c" would become "a b c". For both of these, we're going to monkey patch the string class. Here's the code ...




class String

    def remove_consecutive_spaces

        self.gsub(/ +/, " ")

    end

end





All we do is do a global substitution of one or more spaces with a single space. This would be quite a bit trickier in C say which is why it ends up in interview questions.



The second (or first) problem is to remove duplicate characters from a string. For example, "aaaabbbb" becomes "ab" and "abcbd" becomes "abcd". This one is a bit trickier but shows another good example of how useful inject() can be. Here's the code ...




class String

    def remove_duplicate_characters

        self.split(//).inject([]) { |a, c| a << c if !a.include?(c); a }.join

    end

end





Going through it from left to right, we have first the split(//) which will turn the array into a string of characters. With that string of characters we do an inject([]) which a) initializes a new empty array (sometimes called the "memo") and then runs through the character array adding a character "c" to the array "a" if it's not already there include?. The ; a returns the current array back to the inject. Finally, we recreate the string by doing a join on the character string array.



Let me know if you have questions or comments.



Hett's Problem
2011-08-11T17:04:00.000-07:00
Sorry for not writing for a while, I've been busy looking for a new job. If you've got one, you can contact me here or at slabounty at large search company that starts with "g".



Anyway ... over at Programming Praxis there's a problem via PrologSite concerning lists. Here's the problem statement ...

1.28 (**) Sorting a list of lists according to length of sublists

a) We suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa.



Example:

?- lsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).

L = [[o], [d, e], [d, e], [m, n], [a, b, c], [f, g, h], [i, j, k, l]]



b) Again, we suppose that a list (InList) contains elements that are lists themselves. But this time the objective is to sort the elements of InList according to their length frequency; i.e. in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.



Example:

?- lfsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).

L = [[i, j, k, l], [o], [a, b, c], [f, g, h], [d, e], [d, e], [m, n]]



Note that in the above example, the first two lists in the result L have length 4 and 1, both lengths appear just once. The third and forth list have length 3; there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length.



So how can we solve these two problems in Ruby? The first one is pretty much trivial. Here's the code ...




list = [%w[a, b, c], %w[d], %w[e, f], %w[g, h, i, j, k], %w[l], %w[m, n, o]]

list_sort_length = list.sort {|a, b| a.length <=> b.length}

p list_sort_length





All we're going to do is use the option to sort that takes a block. The block will get two values and instead of the default, we're going to use the values length. Run this and you should see ...

[["l"], ["d"], ["e,", "f"], ["a,", "b,", "c"], ["m,", "n,", "o"], ["g,", "h,", "i,", "j,", "k"]].



The next piece is a bit trickier. Here, we can't do just a one-liner (that I could see anyway). Here's the code ...




hist = Hash.new{|h, k| h[k] = []}

list.each { |l| hist[l.length] << l }

list_sort_hist = []

hist.sort {|a,b| a.length <=> b.length}.each { |key, value| value.each {|e| list_sort_hist << e } }

p list_sort_hist





We start out creating the histogram hash and passing a block so that each element is initialized with an empty array. Then, we work through the list and add each element to an array at the appropriate histogram hash location. Next, create the empty sorted histogram array. Finally, we're going to sort the histogram the same way that we did in the earlier problem (we can do this because they both are Enumerable. We take the result of that and do and each for every item in the histogram. For each of the values (which remember are arrays), we add them to the list_sort_hist array. Finally, we print that out. If it makes it easier to see, split that long line in two. First create a sorted histogram array and then for each value loop through the value and add it to the list_sort_hist array. 



Let me know if you have any comments, questions, or jobs.


Array.zip() and Upside Up Numbers
2011-05-28T15:08:00.000-07:00
I've known about the zip method for arrays but have never really found much of a use for it. I was working a problem on Programming Praxis the other day and saw some Python solutions that used it, so I decided to give it a try in my solution. Let's start out with how it works.

In the simplest case, we have an array and we zip it with an array of the same size. Here's what it looks like ...


a = [1, 2, 3]
b = [4, 5, 6]
a.zip(b) => [[1,4], [2,5], [3,6]]


We can see that we end up with an array that's the same size as the original arrays made up of elements of each of the arrays. We can also zip multiple arrays ...


a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]
d = %w[a, b, c]
a.zip(b, c, d) => [[1, 4, 7, "a,"], [2, 5, 8, "b,"], [3, 6, 9, "c"]] 


With that here's the documented code for the upside_up program including, at the beginning, the original requirements from Programming Praxis ...


# An “upside up” number is a number that reads the same when it is rotated
# 180°. For instance, 689 and 1961 are upside up numbers.

# Your task is to find the next upside up number greater than 1961, and to
# count the number of upside up numbers less than ten 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.
#
# Create an array of pairs that can match. We should end up with
# UPSIDE_DICT = [[0, 0], [1, 1], [6, 9], [8, 8], [9, 6]] 
UPSIDE_DICT = %w[0 1 6 8 9].zip(%w[0 1 9 8 6])

# Open the Integer class and add the upside_up? method that returns true/false
# based on whether the integer is an upside number or not.
# Let's take this a piece at a time:
# 1) self.to_s.split(//) will give us an array of characters for the given number
#    such as [1, 9, 6, 1]
# 2) zip this array with
# 3) self.to_s.split(//).reverse will give us the array above reversed ...
#    [1, 6, 9, 1]
# 4) and zipping the two together should give us something like ...
#    [[1, 1], [9, 6], [6, 9], [1, 1]]
# 5) Now, we'll loop through the above zipped array using inject and make sure that every pair
#    in it is also in the UPSIDE_DICT array. If all of them are, then we'll return
#    true otherwise the inject() will return false.
class Integer
    def upside_up?
        self.to_s.split(//).zip(self.to_s.split(//).reverse).inject(true) { |r,v| r && UPSIDE_DICT.include?(v) }
    end
end

# Find all the upside values up to 10000 and print them.
(1..10000).each do |v|
    puts "#{v} is an upside number" if v.upside_up?
end


Be sure to let me know if you have questions or comments.


Interviewing
2011-05-18T05:57:00.000-07:00
I had a young person come in for an internship interview a couple of days ago and it made me realize that I've never posted anything outside the programming world. I'm going to try to do a few different posts on the subject of interviews and resumes to hopefully help give some perspective to the hiring process from someone who actually hires rather than someone who tries to get you hired (head hunter). Is my perspective better than theirs? No probably not, but it may be a bit different.

With any interview there are going to be both soft questions and hard questions. By this I don't mean easy and hard but personality questions and technical questions. Let's start by looking at some of the soft questions you might get and why they're asked in the first place. The first thing to remember here is that you're going to be part of a group (as an aside, I hate the term "team" unless you're all dressed the same). Because of this, the hiring manager is going to want to know how you're going to fit in with the rest of the group and the soft questions will be used to try to ascertain that.

One question that seems to get asked is "Tell me about yourself". This is where you should discuss your interests related to the job. Since the interviewer is most likely going to ask about job related items later, now is a good time to bring up any outside projects that might relate. Open source projects that you've done or contributed to or a blog that you write (programming/technical related) are things that will get the interviewer's attention. Just about anything technically related is a good thing to bring up.

You're also almost certain to get a question on a group project that you worked on. Here, it won't matter if you're a developer with 20 years experience or a new grad, you'll probably have to talk about working with other people. The question may be as straight forward as "Tell me about a project that you worked on with other people." or it may be more subtle "Tell me about your last project" with the expectation that this involved other people. As you talk about this project, you may get follow on questions such as "Were there any personal issues between people in the group?" or "Was there anyone in the group who didn't pull their weight?". Then these will be followed up with "How did these issues get resolved?". All of these questions are geared towards finding out how well you will fit in in a group situation. And, as a subtext, the interviewer will be looking for your "leadership" capabilities. All of these questions are a chance for you to show that you will work well in a group and not just work well but make the whole group work better. In the example of someone not pulling their weight, stating that you noticed that Fred wasn't doing what was expected, you could tell how you talked with Fred and let him know that you'd noticed his work wasn't as good as it had been and then worked with him to get him back up to speed. In the case of personality issues, discuss how in a meeting where things were getting tense, you played the peacemaker by making sure that both sides got heard and then working through the issues.

There's probably more, but these are the types of questions that I'll usually pursue, these (or similar ones) and then follow ons based on the responses I receive. The thing to remember though is that all of these soft questions are designed for better or worse to figure out if you will fit in the group structure. Try to approach them in this way and you should do fine.

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


All True
2011-04-20T06:28:00.000-07:00
I was working a problem on Programming Praxis yesterday and ended up writing a little piece of code that returned true if every element in a hash was true. It used inject and I thought it would be worth posting a generalized version here.


module Enumerable
    def all_true
        self.inject(true) { |r, v| r && (yield v) }
    end
end


We start by monkey patching the Enumerable module which will make it available for Arrays, Hashes, etc., basically anything that includes Enumerable. Next, we define the method all_true. The only line in the method is an inject which we initialize with true and then give it a block with two parameters, the r(esult) and the v(alue). We then and/&& the r(esult) with whatever the yield of the v(alue) returns.

You can test it with the following code ...


puts "#{[2, 4, 6, 8].all_true { |n| n%2 == 0 }}"
puts "#{[2, 4, 7, 8].all_true { |n| n%2 == 0 }}"

puts "#{{ 2=>2, 4=>4, 6=>6, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"
puts "#{{ 2=>2, 4=>4, 7=>7, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"


The first two of each set will return true, the second false.

As I've been doing the Programming Praxis problems, I've found myself using inject and its close relative map/collect more and more. I think this is partly because of the types of problems posted there and the influence of the solutions that are generated which tend to be functional programming based. At any rate, having a good understanding of both inject and map/collect will serve you well and simplify many of your day to day programming tasks.

Let me know if you have questions or comments.


Nanoc and No Compiling or Routing
2011-03-29T14:02:00.001-07:00
Here's a short post on using nanoc with files that you just want copied from the content directory to the output directory unchanged. For these types of files, it's best if you have them in their own subdirectory (say images or css). Let's say we have some images (.jpg, .png, etc.). First just put them in an images directory under content. Then we need to add a couple of rules to our Rules files ...


compile '/images/*/' do 
  # Leave everything in the images directory as is.
end 


and then a bit later on in the routing section ...


route '/images/*/' do 
    # Make sure that /images/some_image/ is routed to 
    # /images/some_image.jpg or /images/some_image.png or so 
    item.identifier.chop + '.' + item[:extension] 
end 


I didn't do an actual project and put it up on GitHub for this one, but if this isn't clear, then let me know and I can do that too.


Nanoc and Multiple Layout Templates
2011-03-25T09:21:00.000-07:00
A while back we took a quick look at nanoc for generating static web sites. I've been using it a bit both experimenting and for a simple web site for an author friend of mine. I'm going to do a few short articles on using it, documenting what I've learned in much the same way I've tried to do with Ramaze. 

Let's start with some simple code that uses multiple layout templates. You have this often with web sites where there's a home page that uses a different layout than the rest of the pages of the site. Let's start with creating a new site. We do that the same way we did last time with ...

nanoc create_site multiple_templates

and let's add a couple of pages to go along with them ...

nanoc create_item page1
nanoc create_item page2

We didn't really talk about the Rules in the last post and I'm only going to touch on them now. You should take a few minutes and read a bit about them here. We'll discuss them a bit more as we go through future posts.

Now, we need to modify the Rules file to tell it to use an alternate layout for the content/page[12].html files. I'm not going to show the entire file, just the compile rule for these ...


compile '/page*/' do
  filter :erb
  layout 'page'
end


What this rule says is that when we "compile" files in our content/ directory, we should first run them through the erb (embedded ruby) and then use the page template in the layouts directory.

Here's the default which will get use by everything else (essentially our main page at content/index.html).


compile '*' do
  filter :erb
  layout 'default'
end


This along with the code for all of this up on github should be enough to get you started. As always though, let me know if you have questions or comments.


Inkscape
2011-03-01T14:05:00.000-08:00
This one is going to be short since I'm not a designer. I've been reading "Web Design for Developers" by Brian P. Hogan and he recommends using Illustrator for parts of his book. Since the cost was a bit umm... prohibitive for learning purposes, I started looking around for a suitable alternative. What I found was Inkscape. This is a nice little program for generating SVG (Scalable Vector Graphics) files. You can use it for generating files for say logos or banners on websites. While I won't say it's simple to use (and this probably says more about me than the program), with the tutorials available, you shouldn't have too much problem getting it to work. Additionally, there's a book on it that's reviewed on Slashdot. I haven't read the book yet but do have it on order and if it seems worthwhile, I'll post here about it.

To install ...

sudo apt-get install inkscape 

and you should have an inkscape selection Applications/Graphics or at least on Ubuntu.

Once again, I'm not sure how much I'll be able to help, but if you have questions, be sure and let me know.


Nanoc and Static Web Sites
2011-01-28T05:43:00.000-08:00
A few days ago we looked at Webby for generating static web sites. I had a couple of issues with it, including the fact that it didn't work with ruby 1.9.2 and it hasn't been updated for a couple of years now. Someone on the Ramaze email list suggested that I should take a look at nanoc too. It seems to have many of the same features as webby, but is actively maintained and runs on ruby 1.9.2. So let's take a look at getting it up, running, and generating a site. First, we'll need to add a few gems ...


gem install nanoc
gem install kramdown
gem install adsf


Here we're installing nanoc itself, kramdown, which is a Markdown converter, and adsf, which is used as a web server for showing the site.

With that out of the way, let's go ahead and create a new site ...

nanoc create_site my_site

This should create a new site in the directory my_site that has a few different files and directories. Go ahead and cd into the directory and then

nanoc compile

which should "compile" the site. In this case, compile will create an output directory where the resulting HTML files will reside. OK, now we can start a web server with 

nanoc view 

and then point our browser at http://localhost:3000. At this point you should see the default site for nanoc. For viewing, you could also use

nanoc autocompile

which will also compile a file when changes are made to the site automatically. For "real" work, this is probably the option to use. 

OK, let's take a look at the content directory. This is where nanoc will keep the files that will get compiled and moved to the output directory. Go ahead and open up content/index.html in your favorite text editor and make a few changes. Go back to the browser, reload, and you should see your changes there. Now, take a look at layout/default.html. If you make a change in there, say adding an h1 tag before the h2 Documentation tag, it will appear in all the pages that are generated. 

Finally, we're going to need to add new pages if this is going to be useful. Try this ...

nanoc create_item test

This will create a test.htnml in the content directory and when it gets compiled, you should be able to go to http://localhost:3000/test/ (don't forget the final "/") and see the page. A couple of things to note here. In the output directory, this will be output/test/index.html. 

This should be enough to get you started. Definitely check out the nanoc site for more information. I'm going to use this to generate a personal site, so I'll let you know how it goes and what good/bad things I see.

Let me know if you have questions or comments.


Ruby and Rational Numbers
2011-01-25T18:07:00.000-08:00
Here's a problem over on Programming Praxis that for whatever reason I wasn't having much luck posting there. Their loss, your gain ;-). Here's the code ...


class Fraction

    attr_reader :n, :d

    def initialize(n, d)
        raise "Can't have zero denominator." if d == 0 

        n, d = -n, -d if d < 0

        g = n.gcd(d)
        if g == 1
            @n = n
            @d = d
        else
            @n = n / g
            @d = n / g
        end
    end

    def plus(f)
        Fraction.new((@n*f.d)+(@d*f.n), @d*f.d)
    end

    def minus(f)
        Fraction.new((@n*f.d)-(@d*f.n), @d*f.d)
    end

    def times(f)
        Fraction.new(@n*f.n, @d*f.d)
    end

    def divide(f)
        Fraction.new(@n*f.d, @d*f.n)
    end

    def to_s
        "#{@n}/#{@d}"
    end
end

f1 = Fraction.new(1, 3)
f2 = Fraction.new(-1, 7)
puts "#{f1} + #{f2} = #{f1.plus(f2)}"
puts "#{f1} + #{f2} = #{f1.minus(f2)}"
puts "#{f1} + #{f2} = #{f1.times(f2)}"
puts "#{f1} + #{f2} = #{f1.divide(f2)}"


Nothing too awfully complex here, but if you have questions, let me know.


Webby and Static Web Sites
2011-01-24T19:13:00.001-08:00
I was trying to figure out recently how to build a static site with Ramaze and didn't really come up with anything, but someone pointed me in the direction of Webby that's designed with just this use case in mind. It seems pretty cool, so I thought I'd document how to get it up and running on Ubuntu. 

First I tried just doing a gem install, but that didn't work because I'm using ruby 1.9.2 so ...

rvm install 1.8.7

to get the right ruby (assuming you're using rvm to manage this). Then, you'll need to set the correct ruby with 

rvm 1.8.7

to add the following gems for ruby 1.8.7


gem install webby
gem install RedCloth


The RedCloth gem is needed for the default, but if you decide to use a different templating system, you don't need to install it.

OK, let's create a web site now.

webby-gen website my_site

There should now be a directory called my_site with a few different directories. Now you can

cd my_site
webby


and this should create a new directory called output with some HTML files and the css for the site. If you modify the file index.txt in the content directory, and then rerun the webby command, you should see the output/index.html change. 

Since you've been reading this blog, you probably have a pretty good idea of how templating works, so there really shouldn't be too much here that you haven't seen in general even if you haven't looked at the RedCloth templating. webby also supports a number of other templating systems that you can use by setting a filter in the content file. This is documented in the User Manual.

To be honest, I just started looking at this today, so I'm not sure how much help I'm going to be with questions, but let me know if you have any and I'll give them a shot.


Ruby 1.9.2 and Ramaze
2010-11-30T05:52:00.000-08:00
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.


Ruby Book  - $10
2010-11-24T08:52:00.000-08:00
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.


Log Monitoring with a Ruby DSL
2010-10-16T14:17:00.000-07:00
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.


Zeller's Congruence and Five Fr/Sa/Su in October
2010-10-12T05:35:00.000-07:00
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.


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

Here's the code:


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

require 'getoptlong'

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

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

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

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

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

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

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

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

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

    def to_s
        @current_gen.join
    end

    private

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

end

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

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

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

$verbose = false

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

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

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

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

end


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

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

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


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

Wolfram’s MathWorld describes Kaprekar numbers like this:

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

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


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

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

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

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

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

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

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

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

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


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

Let me know if you have questions or comments.


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


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

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

class MainController < Controller

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

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

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

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

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

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

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



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

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

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

Let me know if you have questions.


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


require 'rubygems'
require 'sequel'

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

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

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

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

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

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

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

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


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

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

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

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


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

Let me know if you have questions or comments.


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


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

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

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

end



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

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


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


and the page 2 view, view/page_2.xhtml


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



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


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


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

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


Sequel and Heroku
2010-09-02T17:08:00.000-07:00
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.


Ramaze, GitHub, and Heroku
2010-08-13T12:49:00.000-07:00
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.


Sequel Trees Redux
2010-07-28T05:24:00.000-07:00
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
2010-07-14T05:42:00.000-07:00
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
2010-07-09T13:28:00.000-07:00
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
2010-07-05T10:19:00.000-07:00
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
2010-07-01T15:33:00.000-07:00
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.


The N Queens Problem in Ruby
2010-06-26T10:45:00.000-07:00
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.


Simple Webrick Server and shjs Syntax Highlighting
2010-06-23T19:13:00.000-07:00
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.


145 Puzzle
2010-05-30T10:24:00.000-07:00
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.


Installing Ubuntu, Ruby, Ramaze, Sequel, Vim, and More on an HP dm3-1130us
2010-05-27T19:22:00.000-07:00
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.


Passing Classes as Parameters
2010-04-21T05:56:00.000-07:00
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.


Metaprogramming Ruby - Review
2010-03-22T15:47:00.000-07:00
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.


Ruby and Simple Dynamic Programming V
2010-02-17T05:54:00.000-08:00
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.


Beginning a Program
2010-02-10T05:28:00.000-08:00
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.


Ruby and Simple Dynamic Programming IV
2010-01-20T05:44:00.000-08:00
After my last post, Gregory Brown, the author of Ruby Best Practices wrote in to note that not only was eval evil, it was not ever really necessary. He suggested that the attr_r, attr_w, and attr_rw could be better implemented by using define_method, instance_variable_get, and instance_variable_set. So, as I like to do after someone smart shows me a better way of doing things, I reimplemented our last piece of code using these methods. It's really pretty straightforward so there's not much to really talk about, so here it is:

# Open the class Class and add three new access methods, access_r, access_w, access_rw.
# These are really just reimplementations for attr_reader, attr_writer, attr_accessor.
# This version will use define_method, instance_variable_get, 
# and instance_variable_set to do this (based on a recommendation from Gregory Brown.
class Class

    # Provide read access only. Take a list of symbols and create a 
    # method that will all the user to access each symbol.
    def access_r(*symbols)
        symbols.each do |symbol|
            define_method(symbol) do  
                instance_variable_get("@#{symbol}")
            end        
        end
    end

    # Provide write access only. Take a list of symbols and create a 
    # method that will all the user to write each symbol.
    def access_w(*symbols)
        symbols.each do |symbol|
            define_method("#{symbol}=") do |val| 
                instance_variable_set("@#{symbol}", val)
            end
        end
    end

    # Provide read/write access. Take a list of symbols and create two
    # methods that will all the user to read and write each symbol.
    def access_rw(*symbols)
        symbols.each do |symbol|
            define_method(symbol) do  
                instance_variable_get("@#{symbol}")
            end        

            define_method("#{symbol}=") do |val| 
                instance_variable_set("@#{symbol}", val)
            end
        end
    end

end

if __FILE__ == $PROGRAM_NAME

# Using the new attribute accessor methods.
class Foo
    access_r :bar
    access_w :qux
    access_rw :baz, :quux

    # Since bar is read only from the outside, we'll just initialize
    # it here.
    def initialize(bar)
        @bar = bar
    end

    # Since qux is write only, we'll create a method that lets us view
    # it.
    def show_qux
        puts "qux = #{@qux}"
    end

end


# Create a new foo and initialize bar (read only) with goodbye.
# Show that we can then access it.
foo = Foo.new ("goodbye")
puts "foo.bar = #{foo.bar}"


# Set and then access the two variables we set to 
# read/write.
foo.baz = "hello"
puts "foo.baz = #{foo.baz}"

foo.quux = "world"
puts "foo.quux = #{foo.quux}"

# Set the write only field and then display it using the show_qux
# method.
foo.qux = "test"
foo.show_qux

# Try to access the write only field for reading. This should
# fail with an undefined method.
puts foo.qux

end



Like I said, it's all pretty straightforward. Also, here's a link to someone who's done something very similar using the same technique (there's some other good posts in there, so take some time and read a bit of it).

As always, let me know if you have questions or comments and thanks to Gregory Brown for starting me down this path.


Ruby and Simple Dynamic Programming III
2010-01-01T11:26:00.000-08:00
In my last couple of posts, here and here, I began talking about dynamic programming using Ruby. In this post, I'm going to continue on the same lines and this time we're going to discuss using the eval series of methods, specifically class_eval. Before getting started however, here's a word of warning. Gregory Brown in Ruby Best Practices describes eval (and related methods) as "evil". The truth is that you need to be pretty careful about using these methods as they offer ample opportunity for a user to do some pretty bad things to your system. With that said ...

As you know, Ruby offers three convenience methods for read, write, and read/write access to variables and these are attr_reader, attr_writer, and attr_accessor respectively. Let's take a look at how we could implement these if they hadn't already been thoughtfully provided. 

Here's the code:

# Open the class Class and add three new access methods, access_r, access_w, access_rw.
# These are really just reimplementations for attr_reader, attr_writer, attr_accessor.
class Class
    # Provide read access only. Take a list of symbols and create a 
    # method that will all the user to access each symbol.
    def access_r(*symbols)
        symbols.each { | symbol |
            class_eval "def #{symbol}() @#{symbol}; end" 
        }
    end

    # Provide write access only. Take a list of symbols and create a 
    # method that will all the user to write each symbol.
    def access_w(*symbols)
        symbols.each { | symbol |
            class_eval "def #{symbol}=(val) @#{symbol} = val; end"
        }
    end

    # Provide read/write access. Take a list of symbols and create two
    # methods that will all the user to read and write each symbol.
    def access_rw(*symbols)
        symbols.each { | symbol |
            class_eval "def #{symbol}() @#{symbol}; end"
            class_eval "def #{symbol}=(val) @#{symbol} = val; end"
        }
    end

end

if __FILE__ == $PROGRAM_NAME

# Using the new attribute accessor methods.
class Foo
    access_r :bar
    access_w :qux
    access_rw :baz, :quux

    # Since bar is read only from the outside, we'll just initialize
    # it here.
    def initialize(bar)
        @bar = bar
    end

    # Since qux is write only, we'll create a method that lets us view
    # it.
    def show_qux
        puts "qux = #{@qux}"
    end

end


# Create a new foo and initialize bar (read only) with goodbye.
# Show that we can then access it.
foo = Foo.new ("goodbye")
puts "foo.bar = #{foo.bar}"


# Set and then access the two variables we set to 
# read/write.
foo.baz = "hello"
puts "foo.baz = #{foo.baz}"

foo.quux = "world"
puts "foo.quux = #{foo.quux}"

# Set the write only field and then display it using the show_qux
# method.
foo.qux = "test"
foo.show_qux

# Try to access the write only field for reading. This should
# fail with an undefined method.
puts foo.qux

end



We start out opening Class as this is where we're going to add our new methods, access_r, access_w, and access_rw. We're going to take a list of symbols, represented here with "*symbols" and covert each of the symbols into a new method. For access_r, we'll loop through the symbols and then generate a method with the name "symbol" that returns symbol. For example if we have a symbol :x, we'll get a method that looks like def x() @x; end. The access_rw will give us, for the same symbol :x, def x=(val) @x=val; end. Finally, the access_rw will give us both methods (there's probably a clean way to refactor this so we don't have duplicated code, but this is left as an exercise for the reader). 

Finally, we create a class Foo, that uses all three access methods and then some code that exercises each one. The final call is a read access to a write only field and should fail with an undefined method.

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


Ruby and Simple Dynamic Programming II
2009-12-26T17:27:00.001-08:00
In my last post, we went over using method_missing in Ruby to do some simple dynamic programming. In this post we'll take a look at using the Singleton Class (not the Singleton pattern) to do a bit more dynamic programming. Most of this is a rehash of a couple of great posts by Ola Bini here and Peter Jones here.

So, what is the Singleton Class? A Singleton Class is where methods for an individual object are stored. What's this mean? Let's just look at some code.

# Create a class, Foo, that has a single method bar. We'll also
# add a method_missing so that we can see what's called that 
class Foo
    def bar
        puts "Called bar"
    end

    # Put this in so we can see what gets called in foo2 below that's not available.
    def method_missing(name, *args, &block)
        puts "You tried to call #{name} with #{args.inspect}. There is no method with that name."
    end
end


# Create a new Foo
foo = Foo.new

# Call the method that does exist.
foo.bar

# Add a new method to foo. This method, baz, will be added to 
# foo's singleton class.
def foo.baz
    puts "Called baz"
end

# Call the method we just added.
foo.baz

# Another way to add a new method to foo. This method, baz, will be added to 
# foo's singleton class.
class << foo
    def qux
        puts "Called qux"
    end
end

# Call the method we just added.
foo.qux

# Show that we don't have either baz or qux for any other Foo objects.
foo2 = Foo.new
foo2.bar # Should be there
foo2.baz # Should not be there
foo2.qux # Should not be there

# Add two class methods to Foo.
class Foo
    class << self
        def quux
            puts "Called quux"
        end
    end

    def self.quuux
        puts "Called quuux"
    end
end

foo3 = Foo.new
foo3.quux
foo3.quuux

Foo.quux
Foo.quuux



First we define a class Foo (here we're going to use metasyntactic variables, a phrase I just learned here). Anyway, class Foo has two methods, bar and method_missing (see last post). bar just prints out the fact that it was called and method_missing shows any methods called that aren't available. Nothing too awfully interesting here, we've seen things like this a million times. Next, we'll just create a new Foo called foo and then call the bar method on it. After that, we're going to do something a bit new, we're going to add a new method, baz, to foo (note that we're adding it to the object foo and not the class Foo. We'll call foo.baz to show that it works. Following, we're going to add a method qux using a different syntax, but it will do exactly the same thing as the last addition. Then we're going to call qux on foo to show that it works. Where were these methods added? Well, you can see from the next few statements, that they weren't added to all Foos. The fact is they were added to foo's Singleton Class. The Singleton Class sits between the object foo and its class Foo (see Jones' post to see this represented graphically). 

Since a class has a class Class (OK, that may have made very little sense), it makes sense that the class Foo itself might have a Singleton Class and if you guessed that, then you guessed correctly. In the next section, we add a couple of methods using two different techniques to Foo (notice that we just reopen it), as class methods. In the same way as happened above, these methods are added to the Foo Singleton Class. We create a new foo3 variable and show that we can't call these new methods using an instance of foo, then we call them using Foo. 

OK, so all of this is very interesting and ... so what? What can we do with this. Well, one use for the Singleton Class is for mocking (once again shown in Jones' post).

# Create a class, User, that has a single method get_buy_power. In
# real life a user would have many, many more methods than this.
class User
    def get_buy_power
        # Normally, this would be a complex call to 
        # the database, but here we'll just return
        # a random number * 10000.0. This should give
        # us a number between 0 and 10000.
        rand * 10000.0
    end
end

# A "normal" user. 
user_normal = User.new
puts "user_normal buy power = #{user_normal.get_buy_power}"


# Create a new User
user_small_bp = User.new

# Change the user_small_bp's get_buy_power method to return a small value. This will be
# added to the user_small_bp's singleton class.
class << user_small_bp
    def get_buy_power
        20.0
    end
end

# Print out the buy power for the user_small_bp
puts "user_small_bp buy power = #{user_small_bp.get_buy_power}"


# Create a new User
user_large_bp = User.new

# Change the user's get_buy_power method to return a large value. This will be
# added to the user's singleton class.
class << user_large_bp
    def get_buy_power
        200000.0
    end
end

# Print out the buy power for the user_large_bp
puts "user_large_bp buy power = #{user_large_bp.get_buy_power}"


# We can now use user_small_bp and user_large_bp to run tests on buying stocks 
# without enough buy power or with quite a bit of buy power.


# Create a simple OrderManager that will place orders and send orders. The place_order
# method will check a user's buy power before sending an order through. If the buy power isn't
# large enough, it will simply print a message, otherwise it will send the order and it
# will also print a message.
class OrderManager
    def place_order(user, shares, stock, price)
        if user.get_buy_power > price*shares
            send_order(stock, price, shares)
        else
            puts "Not engough buy power for #{shares} of #{stock} at #{price}"
        end
    end

    private

    def send_order(stock, price, shares)
        puts "Order sent for #{shares} of #{stock} at #{price}"
    end
end

# Create a simple order manager.
order_manager = OrderManager.new

# Place an order for 200 shares of apple at $210.0 with user_small_bp. This should fail.
order_manager.place_order(user_small_bp, 200, "AAPL", 210.0)

# Place an order for 200 shares of apple at $210.0 with user_large_bp. This should succeed.
order_manager.place_order(user_large_bp, 200, "AAPL", 210.0)



Take a look at the code above. In the world that I live in (stock trading software), users have a certain amount of buy power that they can use to purchase stocks. Normally, this value would come out of the database and would be incremented (selling a stock) and decremented I(buying a stock) with each trade (OK, this sentence is incredibly simplistic, but will do for now). We're going to use Singleton Class to change our get_buy_power method (rather than adding as we did earlier). In one case, we'll give the user very little buy power and in the other, quite a bit more. After that, we'll create simple order manager that will allow us to place an order for a user that will check their buy power before sending it. 

So there you have it, the Singleton Class and its usage. As always, let me know if you have any questions or comments.


Ruby and Simple Dynamic Programming
2009-12-16T09:35:00.000-08:00
I've been reading"Ruby Best Practices" by Gregory T. Brown and it's well worth checking out for anyone interested in Ruby. I'm in the middle of Chapter 3, "Mastering the Dynamic Toolkit" and thought I'd share a some simple bits of code that actually use dynamic programming.

We actually make use of the fact that with Ruby you can add a method_missing method to any class that allows you to capture calls to any method that are ... well missing. Here's a simple example that shows how it works.

# Create a class with the method_missing method. If a method 
# is called on this class and it's not found, then this method
# will be called. We'll then print whatever was passed in along
# with the fact that it's not there.
class MM
    def x
        puts "Called x"
    end

    def y
        puts "Called y"
    end

    def method_missing(name, *args, &block)
        puts "You tried to call #{name} with #{args.inspect}. There is no method with that name."
    end
end

if __FILE__ == $PROGRAM_NAME

    # Create a new MM
    mm = MM.new

    # Call the two mehtods that do exist.
    mm.x
    mm.y

    # Call z (which doesn't exist) both with and without 
    # paramaters.
    mm.z
    mm.z 1, 2, 3
end



This code creates a simple class called MM with three methods, x, y, and method_missing. The first two only print out the fact that they were called and the third will print out any other method that gets called, say z 1,2, 3 and will print out the name and parameters that get passed in to it. The main code just creates a new MM and calls a few methods (existing and not) on it.

Admittedly, this isn't too awfully interesting, but in our next example, we'll actually use method_missing to save ourselves some work. Here's the second bit of code:

# Create a class MM1. The x and y methods require calling
# setup before and teardown after. This means that everytime
# we have to add a new method (say z()), we end up having to
# duplicate this code. 
class MM1

    def setup
        puts "Setup"
    end

    def teardown
        puts "Tear down"
    end

    def x
        setup
        puts "Called x"
        teardown
    end

    def y
        setup
        puts "Called y"
        teardown
    end
end

# Create a class with the method_missing method. Here we
# still require x and y to have setup and teardown called, but
# we wrap it in method_missing as setup_x_teardown or setup_y_teardown.
# This allows us to also add z without having to worry about remembering
# the setup/teardown.
class MM2

    def setup
        puts "Setup"
    end

    def teardown
        puts "Tear down"
    end

    # The method_missing() does all of the work here. We check if the 
    # name is setup_something_teardown and if it is, we call setup,
    # call something with the parameters passed in, and then call teardown.
    # If the method isn't of this form, we just pass it along.
    def method_missing(name, *args, &block)
        case (name)
        when /^setup_(.*)_teardown/
            setup
            send($1, *args, & block) 
            teardown
        else
            super
        end
    end

    def x
        puts "Called x"
    end

    def y
        puts "Called y"
    end
end

if __FILE__ == $PROGRAM_NAME

    # Create a new MM1
    mm1 = MM1.new

    # Call the two mehtods that do exist.
    mm1.x
    mm1.y

    # Create a new MM2
    mm2 = MM2.new
    mm2.setup_x_teardown
    mm2.setup_y_teardown
end



There's two classes here that both "do" the same thing. The first class MM1 has two methods, x and y that require a setup before they are called and a teardown after they are called.

The second class, MM2, has the same requirements, but we're going to handle them a bit differently. We have the same setup and teardown, but we don't have x and y call them directly. Instead we use  method_missing to handle the setup and teardown. What we're going to do is use method_missing and then check the name parameter. If it matches something that looks like setup_X_teardown, then we'll call setup, call the method using send, and finally, call teardown. If we don't match the pattern, then we just pass the call up the chain. The main code here creates both an MM1 and an MM2 and shows a bit of how to use them.

Here, in this simple example, you probably wouldn't bother with this. In the book Brown gives a much better use case, but this should give you some ideas at least.

Let me know if you have questions or comments.


Ramaze - Forgot Password II
2009-11-28T16:09:00.000-08:00
Edit 2009-11-30

This in from Jeremy Evans
------------------------------
Looks better, but I recommend a few more changes:

1) You need to salt your password hashes.  Unsalted hashes are better
than storing the password in plaintext, but most common hash
algorithms probably already have large rainbow tables that will allow
an easy lookup of most passwords given an unsalted hash.

2) I would recommend at least including random data when generating
the random key for password resets.  Your use of the username and
Time.now makes it guessable if you know roughly when the user
requested/will request a password change.  encrypt_password is a
poorly named method, since you are hashing, not encrypting (encrypting
implies the possibility of decrypting, while hashing is one way).

3) I generally put a time limit on password resets.  That way if
someone requests one, but then remembers their password and doesn't
change it, they are not vulnerable to someone else changing it next
year.
------------------------------------------------

So, add the salt for the password, modify the generate_rand_key() to add a random component (possibly just add a #{rand(1000000)} to the end of the string to add in a 6 digit random component, rename encrypt_password to say hash_password, and finally add a time limit. Here, you'll need to add a date to the user table, add a date when you generate_rand_key(), and check this in change_password() when you also test the existence of a user with the key.

Thanks for the improvements Jeremy.

------------------------------------------------

After my last post, I received, as I noted, some rather stern comments on a) saving passwords in plaintext in the database and b) sending them in plaintext via email. So, I decided to fix the example up to make it a bit better. We'll be saving the password as a hash in the database and also when the user forgets their password, we'll send a link to let them change it. One other suggestion was to add a salt for the password hash which is easy enough to do, but I've left it as an exercise for the reader. I should note that some of the ideas in this post were stolen (and I mean that in the good sense) from JustKez. This post is definitely worth reading over as are others on the site.

OK, let's get started. We'll start out with the database migration.


# dbMigration/001_ForgotPassword.rb
#
# This is the "new" way to do migrations by using the Class.new form. 
# It means that a new class name is not required and so there is no chance
# of creating a second class in the migration files that is the same as the 
# first causing problems.
Class.new(Sequel::Migration) do
    def up
        # Create the users table.
        create_table(:users) do
            primary_key :id
            String :user_name
            String :password
            String :email
            String :rand_key
        end

    end

    def down
        # Remove the two tables.
        drop_table(:users)
    end
end



This is a bit simpler than in the previous example. We're only going to have a users table with the user_name, password (which will be encrypted), an email address, and a random key (used for sending the user their password).  The down method will just drop the users table. To generate the password, simply type sequel -M dbMigration/ sqlite://forgot.db. This will create the database we'll use for the project.

The model for this is pretty simple too.

# models/models.rb
#
# Create the User model. Each user can have a single challenge question.
require 'digest/sha1'
class User < Sequel::Model 

    # Return an encrypted password based on the one passed in.
    def self.encrypt_password(password)
        Digest::SHA1.hexdigest(password)
    end

    # Generate a random key based on the username and the current time in
    # rand_key and save the model back to the database. We'll use this to email
    # the user so that they can changer their password.
    def generate_rand_key
        self.rand_key = Digest::SHA1.hexdigest("#{@username} -- #{Time.now}")
        save
    end
end



The only model we have is for the User. We have a couple of methods. The first is a Class level method for encrypting the password. We create a hash of the password using SHA1 and return the value (it will be used for creation of the user and changing the password). The second method is for generating a random key which will be passed as part of a link to the user in case they forget or lose their password.

Here's our start code

# start.rb
#
# This is the main program for the example. It loads the Sequel database,
# loads the controllers and models, and then starts up Ramaze. 
#
# The database should have been set up using the database migrations in
# the dbMigration directory. 
require 'rubygems'
require 'ramaze'
require 'sequel'

# Required for mailing.
require 'net/smtp'
require 'mailit'

# Create the mailer.
MAILER = Mailit::Mailer.new(:server => 'MailServer.MyCompany.COM', :port => 25, :username => 'ApplicationName', 
                            :password => 'ApplicationPassword')


# Open the forgot password database. This must be done before we access the
# models that use it.
DB = Sequel.sqlite("forgot.db") 

# Load the controllers and models.
require 'models/models'
require 'controllers/main_controller'

# Start Ramaze.
Ramaze.start



This is pretty much the same as most of our start files. We add in the code for mailit, open the database, and then require our models and controllers. Finally, we start ramaze.

Next up our only controller.

# controllers/main_controller.rb
#
# The mainController has a single method index. First map to / for 
# the view. Next, set the layout to page so that we use the layout/page.xhtml for our 
# layout. 
class MainController < Ramaze::Controller

    # The Main controller will be accessed using "main" as in:
    # http://localhost:7000/main.
    map '/'

    # Use page.xhtml in the layout directory for layout except 
    # for when we're doing AJAX.
    layout(:page) { !request.xhr? }

    # Set up a helper to check if we're logged in and only allow access
    # to the :logged_in page if we are. This is probably the hard way to 
    # do this for only the single page but will make much more sense if 
    # we add more pages as we'd do in a real application.
    helper :aspect
    before(:account_settings, :main) { 
        unless logged_in? 
            # Set the flash message which will only be available in the next
            # screen. In this case that will be the logged_in screen.
            flash[:message] = "You must log in before accessing the requested page."
            redirect rs(:index)
        end
    }

    # You can access it now with http://localhost:7000/
    def index
        @title = "SteamCode - User"
    end

    # Placeholder for real content.
    def main
        "<h2>Main</h2>"
    end

    # Placeholder for real content.
    def about
        "<h2>About</h2>"
    end

    # Placeholder for real content.
    def help
        "<h2>User Help</h2>"
    end

    # Register a new user with SteamCode. We will get here from the
    # views/register.xhtml page where the user will put in their (requested)
    # login, password, and email address.  First find if the user already
    # exists, if it does, then we'll set a message to tell the user so and
    # redirect them back to the register screen. If not, we'll go ahead and add
    # them to the database with the appropriate login, password, and email
    # address. We'll then send them to the login screen to let them log in to
    # SteamCode.
    def register
        @title = "Register with SteamCode"
        # Make sure we're getting here from a post request.
        if request.post?
            # Check the login and password.
            # if we find the Account based on the login and password. If we find it
            # we'll save the login ID in the session variable and we can use that
            # to show if the Account is currently logged in or not. If we can't
            # find the Account, we'll set the flash message, set the session to nil
            # and just stay on this page.
            unless User.find(:user_name => request[:user_name])
                # This account does not exist. Grab the user_name, the password,
                # and the email and create a new Account with them.
                user_name = request[:user_name]
                password = request[:password]
                email = request[:email]

                # Create the account with the user_name, password, and email given.
                user = User.create(:user_name => user_name, :password => User.encrypt_password(password), :email => email)
                Ramaze::Log.debug "New User Added: user_name = #{user.user_name} password = #{user.password} email = #{user.email}"

                # Redirect to the login page.
                redirect rs(:login)

            else
                # This user already exists. Set the flash message for them to
                # try again.
                flash[:message] = "Login #{request[:user_name]} already used. Please select another."
                
                # Stay on the register page.
                redirect rs(:register)
            end
        end
    end

    # Login to Steamcode. If the request is a post, then we'll try to find the
    # user. If we succeed then we'll set some session variables and redirect to
    # the main page (which the user can only access if they're logged in). If they
    # can't be logged in, we'll set a flash message, reset the session, and redirect
    # back to the login page.
    def login
        @title = "Login to SteamCode"
        if request.post?
            if user = User.find(:user_name => request[:user_name], :password => User.encrypt_password(request[:password]))
                # Use the name= portion of the input form to grab the data
                # from the request variable and save it in the session
                # hash table.
                session[:user_id] = user.id
                session[:user_name] = user.user_name

                # Redirect to the main screen.
                redirect rs(:main)
            else
                # The login could not be authorized. Set the flash message
                # and stay on this page (index/login). Set the session loginID 
                # to nil also. This will effectively log the user out. This would 
                # be reasonable if they are logged in and then try to log in with
                # a new login/password.
                flash[:message] = "Incorrect user name or password, please try again!!!"
                session[:user_id] = nil
                session[:user_name] = nil

                # Stay on the login page.
                redirect rs(:login)
            end
       end
    end

    # Let the user change account settings. For now this is
    # just the email and password.
    def account_settings
        @title = "Account Settings for SteamCode"
        user = User[session[:user_id]]
        if request.post?
            user = User[session[:user_id]]
            user.email = request[:email]
            user.password = User.encrypt_password(request[:password])
            user.save
            flash[:message] = "New email and/or password saved."
            redirect rs(:main)
        end
        @current_email = user.email
    end

    # Logout of the system. Set the flash message and then
    # set the session values to nil. Finally, redirect back to the 
    # index page.
    def logout
        @title = "Logout from SteamCode"
        flash[:message] = "#{session[:user_name]} Logged out"
        session[:user_id] = nil
        session[:user_name] = nil
        redirect rs(:index)
    end

    # The user has requested that we email their password back to them. Generate
    # a random key and email it to them to allow them to change their password.
    def forgot_password
        if request.post?
            # Final submit.
            if user = User.find(:user_name => request[:user_name])
                
                # Generate a key and associate it with the user_name.
                user.generate_rand_key

                # Create the mail message and fill it in with the appropriate
                # information (to/from/subject/text). Then send it off.
                mail = Mailit::Mail.new
                mail.to = user.email
                mail.from = "Steamcode@MyCompany.com"
                mail.subject = "Steamcode Password"
                mail.text = "To change your password: http://localhost:7000/change_password/#{user.rand_key}"

                # Send the mail message via the MAILER (created in start.rb).
                MAILER.send(mail)

                # Just go back to the login page.
                redirect rs(:login)
            else
                flash[:message] = "Could not find user: #{request[:user_name]}"

                # Could not find user with this user_name.
                redirect rs(:forgot_password)
            end
        end
    end

    # The key will be the key that we created above when the user asked
    # for the password change. It will be passed as a parameter when the user
    # clicks on the link that was emailed to them.
    def change_password(key)
        # Check to make sure that there's a user with this key.
        user = User.find(:rand_key => key)
        if user
            if request.post?
                # We got here from a post and there's a user with the key. Go ahead
                # and a) change the password, b) reset the random key, and c) save
                # the new user information. Then set the flash message and put them 
                # on the login screen.
                user.password = User.encrypt_password(request[:password])
                user.rand_key = nil
                user.save
                flash[:message] = "Your new password saved."
                redirect rs(:login)
            end
        else 
            # There wasn't a user with this random key. Just flash a message
            # and then redirect to the login screen.
            flash[:message] = "This does not appear to be a valid request."
            redirect rs(:login)
        end
    end

    private

    # If the user is logged in, the session will
    # contain a non nil user id.
    def logged_in?
        session[:user_id] != nil
    end
end



This is very similar to many of our other controllers from our past posts. We map to '/', Add the layout (which won't be used for AJAX calls (not used here anyway)), and then the aspect which will prevent the user from going to certain pages unless they're logged in to the system. The next four methods, index, main, about, and help are really just place holders. Index is where the user will end up initially and main is where they will end up after logging in. Then we have the register page. This will check if it's a post and if it is, try to find the user. If it can't find the user (note the use of "unless" here. To a certain extend, I'm trying to decide if it helps or hinder readability. Let me know what you think) it will create a new one with the parameters from the request hash. If the user already exists, we'll just flash a message back and redirect them back to the register page. Next we have the login method. We check to make sure this is from a post, then check to see if we can find the user based on their user name and password (using the model's encrypt_password method). If we find them, we go ahead and log them in (set the session variables) and redirect them to the main page. If not, we flash a message, reset the session variables, and redirect them back to the login page. The account_settings page let's the user reset their email and password. The logout page resets the session variables and then redirects back to the index page. Looking at it now, I'd recommend refactoring the session resets here and in login to their own private method (once again we'll leave that as an exercise). The forgot_password method is the reason for all of this. We check that it's a post and contains a valid user. If so, we generate a random key for the user (using the model method) and then create an email with the link containing this key. If we can't find the user, we'll flash a message and redirect back to the same page. Finally (for the pages anyway), we have the change_password page. This checks to see if we have user with this rand_key (from the link generated above) and if we do, we check if this is a post and change their password appropriately, reset the random key (so it's used only once), flash a message and redirect them back to the login page. If there wasn't a user with that random key, we simply flash a message and redirect them back to the login page. Finally, we have the private method that's used to check if a user is logged in to the system.

Here's our layout page.xhtml

<!-- view/page.xhtml -->

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
    <head> 
        <!-- Use the page.css in the public directory and set title based on
        what's set in the associated method.
        -->
        <link rel="stylesheet" type="text/css" href="/page.css"/>

        <title>#@title</title> 
    </head>
    <body>
        <div id="whole_page">
            <div id="header">
                <h1>SteamCode</h1>
            </div>

            <div id="nav">
                <!-- Main/User controller -->
                <!-- Move this next section over to the right side of the screen. It
                will contain the Login/Register if we're not logged in and the Logout
                if we are.  -->
                <span style="float: right">
                    <!-- We're going to use the private method logged_in? here to test if 
                    we want to show the Login/Register links or the Logout link -->
                    <?r if !logged_in? ?>
                        <a href="#{r(:login)}">Login</a>
                        <a href="#{r(:register)}">Register</a>
                    <?r else ?>
                        <a href="#{r(:account_settings)}">Account</a>
                        <a href="#{r(:logout)}">Logout</a>
                    <?r end ?>
                </span>

                <!-- These next three will be on the left side and always there -->
                <a href="#{r(:index)}">Home</a> |
                <a href="#{r(:about)}">About Us</a> |
                <a href="#{r(:help)}">Help</a>
            </div>

            <div id="content">
                <!-- Display the actual content. This will come from the method or the
                associated view/*.xhtml file
                -->
                #@content
            </div>

            <!-- Set the footer in the center of the screen. -->
            <div id="footer" style="text-align: center;">
                <h5> Powered by Ramaze </h5>
            </div>
        </div>
    </body>
</html>



It's stripped down a bit from the last post and has all of the administration stuff removed. Since you've seen this in past posts, I won't go through it. It's mostly just code for the navigation with some content and a header and footer tossed in for good measure.

Let's take a look at the views for the project. They're really simple this time. No JavaScript and no AJAX. Here's the index.

#{flashbox}
<h2>Welcome</h2>



Here's the login page

#{flashbox}
<a href="#{r(:forgot_password)}">Forgot your password?</a>
<br/>

<form id="login" method="post">
    <fieldset>
        <legend> Login </legend>
        <div>
            <!-- for= goes with id=, the name= is placed in the request variable. -->

            <!-- Input for the user_name. -->
            <label for="user_name">User Name:</label>
            <input id="user_name" name="user_name" type="text" />
            <br/>

            <!-- Input for the user_name. -->
            <label for="password">Password:</label>
            <input id="password" name="password" type="password" />
            <br/>

            <!-- Submit the login request.  -->
            <input type="submit" value="Login" />
        </div>
    </fieldset>
</form>



There's just input boxes for the user name and password and a button for submitting.

Here's the registration page.

<!-- view/register.xhtml -->
<form id="register" method="post">
    <div>
        <!-- for= goes with id=, the name= is placed in the request variable. -->

        <!-- Input for the user_name. -->
        <label for="user_name">Login:</label>
        <input id="user_name" name="user_name" type="text" />
        <br/>

        <!-- Input for the password. -->
        <label for="password">Password:</label>
        <input id="password" name="password" type="password" />
        <br/>

        <!-- Input for the email. -->
        <label for="email">Email:</label>
        <input id="email" name="email" type="text" />
        <br/>

        <!-- Submit the new User -->
        <input type="submit" value="Register" />
    </div>
</form>



As above boxes for user name, password, and email plus the submit button.

Here's the page for changing the account settings.

<!-- Let's the user change their email and/or password -->
<form id="change_password" method="post">
    <fieldset>
        <legend> Change Settings </legend>
        <div>
            <!-- Input for the email address. -->
            <label for="email">Email:</label>
            <input id="email" name="email" type="text" value=#{@current_email} />
            <br/>

            <!-- Input for the password. -->
            <label for="password">Password:</label>
            <input id="password" name="password" type="password"/>
            <br/>

            <!-- Submit the new email and/or password -->
            <input type="submit" value="Submit" />
        </div>
    </fieldset>
</form>



This contains boxes for password and email (the user can't change their user_name) and the submit button.

Next is the forgot_password.xhtml.

<h2>Forgot Password</h2>
#{flashbox}

<form id="forgot_screen" method="post">
    <fieldset>
        <legend> Forgot Password </legend>
        <div id='forgot_password'>

            <!-- for= goes with id=, the name= is placed in the request variable. -->
            <!-- Input for the user_name. -->
            <label for="user_name">User Name:</label>
            <input id="user_name" name="user_name" type="text" value="User Name" />
            <br/>

        </div>

        <!-- Once they've put in the challenge answer, they will select -->
        <!-- this and the system will send their password via email. -->
        <input type="submit" value="Send Password" />
    </fieldset>
</form>
<br/>



This has a box for the user_name and the submit button. When the user puts in their user_name and submits, an email is generated (see above) that provides a link to change their password. This page is the change_password.xhtml.

<!-- view/register.xhtml -->
<form id="change_password" method="post">
    <div>
        <!-- for= goes with id=, the name= is placed in the request variable. -->

        <!-- Input for the password. -->
        <label for="password">Password:</label>
        <input id="password" name="password" type="password" />
        <br/>

        <!-- Submit the new User -->
        <input type="submit" value="Change Password." />
    </div>
</form>



Once again, dead simple with the password box and a submit (you'd probably want a confirmation password that would be checked using JavaScript, but we'll just assume that the user won't make any mistakes.

That's pretty much everything except for the CSS which is in public/page.css


#whole_page {
  width: 50em;
  margin: auto;
  padding: 0;
  text-align: left;
  border-width:  0 1px 1px 1px;
  border-color:  black;
  border-style:  solid;
}

#content {
  height: 100%;
  background:  white;
  padding: 1em 1em 1em 1em;
}


/* Header CSS */
#header {
    background:#9DA9EE;
    color: white;
    margin-bottom: 0;
    padding: 0.25em;
}

#nav {
    background:#9DA9EE;
    color: black;
    padding: 0.5em;
}


/* Footer CSS */
#footer {
    background:#9DA9EE;
    color: black;
}


So, I hope this works out for everyone a bit better than the last version and gets at least a bit closer to what you might use in a "real" project. Let me know if you have questions or comments.