Showing posts with label ruby. Show all posts
Showing posts with label ruby. Show all posts

Sunday, January 29, 2012

Rails / Ajax / Autocomplete

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.

Sunday, December 18, 2011

Majority Voting

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.

Monday, November 14, 2011

Centroids

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.

Tuesday, November 1, 2011

Ruby Distance Calculation

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.

Wednesday, October 5, 2011

Heaps

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.

Tuesday, September 13, 2011

Tetrahedral Numbers

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.

Thursday, August 11, 2011

Hett's Problem

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.

Saturday, May 28, 2011

Array.zip() and Upside Up Numbers

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.

Wednesday, April 20, 2011

All True

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.

Friday, March 25, 2011

Nanoc and Multiple Layout Templates

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.

Tuesday, January 25, 2011

Ruby and Rational Numbers

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.

Monday, January 24, 2011

Webby and Static Web Sites

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.

Tuesday, November 30, 2010

Ruby 1.9.2 and Ramaze

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

require 'model/user'

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

__DIR__('user')

or

require_relative 'user'

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

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

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

Wednesday, November 24, 2010

Ruby Book - $10

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

Saturday, October 16, 2010

Log Monitoring with a Ruby DSL

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

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

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


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


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

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


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

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

monitor "Info"


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

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


require 'file/tail'

class MonitorLog

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

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

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

end

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

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

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

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

if __FILE__ == $PROGRAM_NAME

require 'getoptlong'

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

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

# Set the default values for the options
number = 10
filename = 'monitor.log'
monitor_filename = 'monitor.mon'
$verbose = false

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


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

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

# Start monitoring.
$monitor_log.monitor

end



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

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

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

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

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

Let me know if you have questions or comments.

Tuesday, October 12, 2010

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

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


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


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

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


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

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


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

Let me know if you have any questions or comments.

Wednesday, September 22, 2010

One Dimensional Cellular Automata

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

Here's the code:


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

require 'getoptlong'

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

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

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

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

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

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

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

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

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

def to_s
@current_gen.join
end

private

# Initialize the current_gen array with either a
# single "B" cell in the middle or with a random
# mix of "B" and "W" cells.
def initialize_current_gen(random_init)
@current_gen = Array.new(@total_cells, "W")
if random_init
@current_gen.each_index do |i|
@current_gen[i] = (rand < 0.5) ? "W" : "B"
end
else
@current_gen[@total_cells/2] = "B"
end
end

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

end

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

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

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

$verbose = false

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

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

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

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

end


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

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

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

Tuesday, September 21, 2010

Kaprekar Numbers

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

Wolfram’s MathWorld describes Kaprekar numbers like this:

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

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


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

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

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

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

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

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

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

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

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


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

Let me know if you have questions or comments.

Monday, September 13, 2010

Snippet Highlighting with Ramaze and Sequel

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


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

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

class MainController < Controller

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

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

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

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

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

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

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



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

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

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

Let me know if you have questions.

Saturday, September 4, 2010

Ramaze and Partial Rendering

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


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

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

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

end



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

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


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


and the page 2 view, view/page_2.xhtml


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



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


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


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

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