Roland's blog

The previous post was using the 1990 cencus data. I got the new data from
http://www.census.gov/geo/www/gazetteer/places2k.html
and updated the script.

Download: counties_in_states2.zip

For a project I was trying to figure out all the Counties in each state in the United States.
First I got a list at http://www.census.gov/datamap/fipslist/AllSt.txt.

The data is not very well formatted so I wrote a ruby script to import the data. According to this site http://www.usgs.gov/faq/list_faq_by_category/get_answer.asp?id=785 There are "3,141 counties and county equivalents in the 50 States and the District of Columbia". Well the list above is not very accurate if this is the case. I was able to get find parse out only 2954 counties. The Census site says the data was collected in January 1, 1990. Hmm, that's really out of date information. However, I am posting the code that I wrote to parse the file. You will need a mysql database and activerecord to run the script.

Download: counties_in_states.zip.

require "soap/wsdlDriver"

wsdl = "http://aitl-test.uc.edu/Roland/login/app/controllers/UserWSController.cfc?wsdl"

factory = SOAP::WSDLDriverFactory.new(wsdl)

driver = factory.createDriver

driver.login

Displays the login screen.

Dr. Paul describes in his book the OptimalSearchTree algorithm. Here's it's implementation in ruby.

def print_matrix(m)
  print m.collect{|row| row.join("t")}.join("n") + "n"
end

def optimal_search_tree(p, q)
  n = p.size
  root = Array.new(n){Array.new(n){0}}
  a = Array.new(n){Array.new(n){0}}
  sigma = Array.new(n){Array.new(n){0}}
  for i in 0..(n-1)
    root[i][i] = i
    sigma[i][i] = p[i] + q[i] + q[i+1]
    a[i][i] = sigma[i][i]
  end
  for pass in 1..(n-1)
    for i in 0..(n-1-pass)
      j = i + pass
      sigma[i][j] = sigma[i][j-1] + p[j] + q[j+1]
      root[i][j] = i
      min = a[i+1][j]
      for k in (i+1)..j
        sum = a[i][k-1] + (a[k+1][j] rescue 0)
        if sum < min
          min = sum
          root[i][j] = k
        end
      end
      a[i][j] = min + sigma[i][j]
    end
  end
  [a, root, sigma]
end

And test out the functions:

p = [15, 10, 20, 30]
q = [5, 5, 0, 5, 10]
a, root, sigma = optimal_search_tree(p, q)
print_matrix a; print "n"
print_matrix root; print "n"
print_matrix sigma; print "n"

Results:

a:
25      50      110     195
0       15      55      135
0       0       25      90
0       0       0       45
root:
0       0       1       2
0       1       2       3
0       0       2       3
0       0       0       3
sigma:
25      35      60      100
0       15      40      80
0       0       25      65
0       0       0       45

I finally managed to implement the many detail lacking description Dr. Paul wrote in his book. Here's the code.

def print_matrix(m)
  print m.collect{|row| row.join("t")}.join("n"), "n"
end

def optimal_parenthesization(d)
  n = d.size - 1
  m = Array.new(n){Array.new(n){0}}
  first_cut = Array.new(n){Array.new(n){0}}

  for diag in 1..(n-1)
    for i in 0..(n-1-diag)
      j = i + diag
      min = m[i+1][j] + d[i]*d[i+1]*d[j+1]
      temp_cut = i
      for k in (i+1)..(j-1)
        temp = m[i][k] + m[k+1][j] + d[i]*d[k+1]*d[j+1]
        if temp < min
          min = temp
          temp_cut = k
        end
      end
      m[i][j] = min
      first_cut[i][j] = temp_cut
    end
  end
  [m, first_cut]
end

Now, say we get the following list of matrices: 20x10, 10x50, 50x5, 5x30.
Now here is how we invoke the functions:

d = [20, 10, 50, 5, 30]
m, s = optimal_parenthesization(d)
print_matrix m
p "="*80
print_matrix s

Note that d is the number of rows in the first matrix, followed by the number of cols in all matrices.

When using the * to quickly create arrays.. you may encounter problems... see below

irb(main):001:0> n = 5
=> 5
irb(main):002:0> m = [[nil]*n]*n
=> [[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil]]
irb(main):003:0> m[0][0] = 0
=> 0
irb(main):004:0> m
=> [[0, nil, nil, nil, nil],
[0, nil, nil, nil, nil],
[0, nil, nil, nil, nil],
[0, nil, nil, nil, nil],
[0, nil, nil, nil, nil]]

However if the array is created element by element then the problem no longer holds.

irb(main):001:0> n = 5
=> 5
irb(main):002:0> m = []
=> []
irb(main):003:0> for i in 0..(n-1)
irb(main):004:1>   m[i] ||= []
irb(main):005:1>   for j in 0..(n-1)
irb(main):006:2>     m[i][j] = nil
irb(main):007:2>     end
irb(main):008:1>   end
=> 0..4
irb(main):009:0> m
=> [[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil]]
irb(main):010:0> m[0][0] = 0
=> 0
irb(main):011:0> m
=> [[0, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil],
[nil, nil, nil, nil, nil]]

To enable autocomplete in irb enter this in .irbrc

IRB.conf[:AUTO_INDENT] = true
IRB.conf[:USE_READLINE] = true
IRB.conf[:LOAD_MODULES] = []  unless IRB.conf.key?(:LOAD_MODULES)
unless IRB.conf[:LOAD_MODULES].include?('irb/completion')
  IRB.conf[:LOAD_MODULES] << 'irb/completion'
end

Details: http://wiki.rubyonrails.org/rails/pages/TipsAndTricks

So I wrote a little ruby code to get me the three first levels of the variable state space tree for my assignment.

You will need Graphviz/dot to actually plot this.

The code generates the state space tree for backtracing for the 0/1 Knapsack problem. (jargon eh?)

Execute with:
ruby dec.rb > graph.dot && dot -x graph.dot -Tpng -o out.png

dec.rb

i = (0..6).to_a
v = [25, 45, 12, 7, 6, 10, 5]
w = [5, 11, 3, 2, 2, 7, 4]
c = 15
class Node
  attr_accessor :w, :v, :e, :children, :parent
  def initialize(w, v, e=0, parent=nil)
    @e = e
    @w = w
    @v = v
    @children = []
    @parent = parent
  end
end

def print_edge(x, y)
  print "\"(#{x.w},#{x.v})\" -> \"(#{y.w},#{y.v})\" [label=#{y.e}]; n"
end

s = Node.new(0, 0)
print "digraph T {n"
print "node [shape=box];n"
# level 1
for a in i
  n = Node.new(s.w+w[a], s.v+v[a], a, s)
  s.children << n unless s.children.include? n
  print_edge(s, n)
end
# level 2
for child in s.children
  for a in i
    if a > child.e and (child.parent ? child.parent.w <= c : true)
      n = Node.new(child.w+w[a], child.v+v[a], a, child)
      child.children << n
      print_edge(child, n)
    end
  end
end
# level 3
for parent in s.children
  for child in parent.children
    for a in i
      if a > child.e and child.w < c
        n = Node.new(child.w+w[a], child.v+v[a], a, child)
        child.children << n
        print_edge(child, n)
      end
    end
  end
end

print "}n"