Oct 27, 2008 Software Perl

Synchronising two directory trees - tree-sync 2.4

tree-sync.pl has had a little update thanks to a contribution from Dave Stafford.

• Added option 'diff' to view only changes


• Added option 'ignore' to exclude certain extensions


• Added option 'brief' to remove src/dest directories in report view to make cleaner output

In the 2.4 release I've also added the 'force' option to control read-only file handling.

tree-sync.pl is a bit of a geeky tool, suitable for cases where you want detailed control over a file-based copy/mirror/backup process from the command-line. There are many flashier solutions available these days, but if tree-sync scratches your itch - go for it!

tree-sync.pl continues to be available on CPAN, but from the 2.4 release I have moved the source to github. If you have changes to suggest or bugs to fix, please go ahead and join this project.
read more and comment..

Oct 20, 2008 Ruby

Rolling Project Euler on Ruby

I first heard about Project Euler last week on the stackoverflow podcast. Michael Pryor (fogcreek co-founder) makes a quick side reference in discussion with Joel Spolsky, Jeff Atwood and the rest of the SO team.

Well I checked it out last week, got hooked and spent most of the weekend earning my "level 1" badge;-)

Aside from dusting off some long-forgotten and arcane knowledge from my youth, I found it a fantastic opportunity to stretch my fundamental ruby chops. In fact, I'd recommend a few questions at Project Euler as a right-of-passage whenever you are learning a new programming language.

I've only been using ruby for a year or so, and in that time thought I had picked up a fair bit. But I was still able to amaze myself at just how many of the problems were knocked over in just 1 or 2 lines with a bit of duck punching and liberal use of blocks with Enumerables.

I'm late to the Project Euler craze, so you will already find many people posting hints for specific questions if you just google. I thought I'd share some of the "common code" I've been building up as I go through the questions.

I put a recent copy of the source up on github for anyone who is interested (MyMath.rb), but what follows a sampling of some of the more interesting pieces.

First thing you will note is that I have written all these "common" routines as extensions to some of the fundamental classes in the ruby library: Integer, Array, String.

It doesn't have to be this way, and for less trivial activities you might be right to be concerned about messing with the behaviour of the standard classes. Maybe I'm still enjoying my ruby honeymoon period, but I do get a thrill out of being able to write things like

1551.palindrome?
=> true

Integer Extensions

It's just so easy to code up simple calculation and introspection routines..

class Integer
  # @see project euler #15,20,34
  def factorial
    (2..self).inject(1) { |prod, n| prod * n }
  end

  # sum of digits in the number, expressed as a decimal
  # @see project euler #16, 20
  def sum_digits
    self.to_s.split('').inject(0) { |memo, c| memo + c.to_i }
  end

  # num of digits in the number, expressed as a decimal
  # @see project euler #25
  def num_digits
    self.to_s.length
  end
  
  # tests if all the base10 digits in the number are odd
  # @see project euler #35
  def all_digits_odd?
    self.to_s.split('').inject(0) { |memo, s| memo + ( s.to_i%2==0 ? 1 : 0 ) } == 0
  end
  
  # generates triangle number for this integer
  # https://en.wikipedia.org/wiki/Triangle_number
  # @see project euler #42
  def triangle
    self * ( self + 1 ) / 2
  end
end

Prime numbers feature heavily on Project Euler, and I think calculating a prime series was my first lesson on why you can't brute-force everything;-) Enter the Sieve of Eratosthenes and related goodness..

class Integer 
  # https://en.wikipedia.org/wiki/Prime_factor
  # @see project euler #12
  def prime_factors
    primes = Array.new
    d = 2  
    n = self      
    while n > 1
     if n%d==0
        primes << d
        n/=d
      else
        d+=1
      end
    end
    primes
  end
  
  # https://en.wikipedia.org/wiki/Divisor_function
  # @see project euler #12
  def divisor_count
    primes = self.prime_factors
    primes.uniq.inject(1) { |memo, p| memo * ( ( primes.find_all {|i| i == p} ).length + 1) }
  end
  
  #
  # @see project euler #12, 21, 23
  def divisors
    d = Array.new
    (1..self-1).each { |n| d << n if self % n == 0 }
    d
  end

  # @see project euler #
  def prime?
    divisors.length == 1 # this is a brute force check
  end
  
  # prime series up to this limit, using Sieve of Eratosthenes method
  # https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  # @see project euler #7, 10, 35
  def prime_series
    t = self
    limit = Math.sqrt(t)
    a = (2..t).to_a
    n = 2
    while (n < limit) do
      x = n*2
      begin
        a[x-2]=2
        x+=n
      end until (x > t )
      begin
        n+=1
      end until ( a[n-2] != 2 )
    end
    a.uniq!
  end

  # @see project euler #23
  def perfect?
    self == divisors.sum
  end

  # @see project euler #23
  def deficient?
    self > divisors.sum
  end

  # @see project euler #23
  def abundant?
    self < divisors.sum
  end
end

Next we visit the Collatz conjecture and an interesting routine to make numbers "speak english"..

class Integer     
  # https://en.wikipedia.org/wiki/Collatz_conjecture
  # @see project euler #14
  def collatz_series
    a = Array.new
    a << n = self
    while n > 1
      if n % 2 == 0
        n /= 2
      else
        n = 3*n + 1
      end
      a << n
    end
    a  
  end

  # express integer as an english phrase
  # @see project euler #17
  def speak
    case
    when self <20
      ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
       "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" ][self]
    when self > 19 && self < 100 
      a = ["twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"][self / 10 - 2]
      r = self % 10
      if r == 0
        a
      else
        a + "-" + r.speak
      end
    when self > 99 && self < 1000
      a = (self / 100).speak + " hundred"
      r = self % 100
      if r == 0
        a
      else
        a + " and " + r.speak
      end      
    when self > 999 && self < 10000
      a = (self / 1000).speak + " thousand"
      r = self % 1000
      if r == 0
        a
      else
        a + ( r <100 ? " and " : " " ) + r.speak
      end      
    else
      self
    end
  end
end

Calculating integer partitions is one of my favourites ... a nice, super-fast recursive algorithm. For problems like "how many ways to make $2 in change?"

class Integer 

  # calculates integer partitions for given number using array of elements 
  # https://en.wikipedia.org/wiki/Integer_partition
  # @see project euler #31
  def integer_partitions(pArray, p=0)
    if p==pArray.length-1
      1
    else
      self >= 0 ? (self - pArray[p]).integer_partitions(pArray ,p) + self.integer_partitions(pArray,p+1) : 0
    end
  end   
end

Finally, rotations and palindromes (base 2 or 10): methods that rely on some underlying String routines that come later...

class Integer 
  # returns an array of all the base10 digit rotations of the number
  # @see project euler #35
  def rotations
    self.to_s.rotations.collect { |s| s.to_i }
  end

  # @see project euler #4, 36, 91
  def palindrome?(base = 10)
    case base 
    when 2
      sprintf("%0b",self).palindrome?
    else
      self.to_s.palindrome?
    end
  end
end

Array Manipulations

Array handling is particularly important. Start with some simple helpers, then move onto greatest common factor and a couple of least-common multiple implementations. My favourite here - lexicographic permutations.

class Array

  # sum elements in the array
  def sum
    self.inject(0) { |sum, n| sum + n }
  end
  
  # sum of squares for elements in the array
  # @see project euler #6
  def sum_of_squares
    self.inject(0) { |sos, n| sos + n**2 }
  end
  
  # @see project euler #17
  def square_of_sum
    ( self.inject(0) { |sum, n| sum + n } ) ** 2
  end
    
  # index of the smallest item in the array
  def index_of_smallest
    value, index  = self.first, 0
    self.each_with_index {| obj, i | value, index = obj, i if obj<value  }
    index
  end

  # removes numbers from the array that are factors of other elements in the array
  # @see project euler #5
  def remove_factors
    a=Array.new
    self.each do | x | 
      a << x if 0 == ( self.inject(0) { | memo, y | memo + (x!=y && y%x==0 ? 1 : 0)  } )
    end
    a
  end

  # http://utilitymill.com/edit/GCF_and_LCM_Calculator
  # @see project euler #5
  def GCF
    t_val = self[0]
    for cnt in 0...self.length-1
      num1 = t_val
      num2 = self[cnt+1]
      num1,num2=num2,num1 if num1 < num2
      while num1 - num2 > 0
        num3 = num1 - num2 
        num1 = [num2,num3].max
        num2 = [num2,num3].min
      end
      t_val = num1
    end
    t_val
  end

  # http://utilitymill.com/edit/GCF_and_LCM_Calculator
  # @see project euler #5
  def LCM
    a=self.remove_factors
    t_val = a[0]
    for cnt in 0...a.length-1
      num1 = t_val
      num2 = a[cnt+1]
      tmp = [num1,num2].GCF
      t_val = tmp * num1/tmp * num2/tmp
    end
    t_val  
  end

  # brute force method:
  # http://www.cut-the-knot.org/Curriculum/Arithmetic/LCM.shtml
  # @see project euler #5
  def lcm2
    a=self.remove_factors
    c=a.dup
    while c.uniq.length>1
      index  = c.index_of_smallest  
      c[index]+=a[index]
    end
    c.first
  end

  # returns the kth Lexicographical permutation of the elements in the array
  # https://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation
  # @see project euler #24
  def lexicographic_permutation(k)
    k -= 1
    s = self.dup
    n = s.length
    n_less_1_factorial = (n - 1).factorial # compute (n - 1)!
    
    (1..n-1).each do |j|
      tempj = (k / n_less_1_factorial) % (n + 1 - j)

      s[j-1..j+tempj-1]=s[j+tempj-1,1]+s[j-1..j+tempj-2] unless tempj==0
      n_less_1_factorial = n_less_1_factorial / (n- j)
    end
    s
  end
  
  # returns ordered array of all the lexicographic permutations of the elements in the array
  # https://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation
  # @see project euler #24
  def lexicographic_permutations
    a=Array.new
    (1..self.length.factorial).each { |i| a << self.lexicographic_permutation(i) }
    a
  end
    
end

String Helpers

Last but not least, some String methods that just make things so much easier...

class String

  # sum of digits in the number
  # @see project euler #16, 20
  def sum_digits
    self.split('').inject(0) { |memo, c| memo + c.to_i }
  end

  # product of digits in the number
  # @see project euler #8
  def product_digits
    self.split('').inject(1) { |memo, c| memo * c.to_i }
  end
  
  #
  # @see project euler #4, 36, 91
  def palindrome?
    self==self.reverse
  end 

  # returns an array of all the character rotations of the string
  # @see project euler #35
  def rotations
    s = self
    rots = Array[s]
    (1..s.length-1).each do |i|
      s=s[1..s.length-1]+s[0,1]
      rots << s
    end
    rots 
  end
    
end

With all the above in place - and with the aid of a few brain cells - some deceptively complicated questions (like "How many different ways can £2 be made using any number of coins?") are essentially one-liners:

require 'benchmark'
require 'MyMath'

Benchmark.bm do |r|
  r.report {
    answer = 200.integer_partitions([200,100,50,20,10,5,2,1])
  }
end

Love it;-)
read more and comment..

Oct 20, 2008 Read

Thomas of Hookton and 1215, The Year of the Magna Carta

Bernard Cornwell is a master and commander when it comes to bringing alive European history from the last millenia. Where Patrick O'Brian has the sea, Cornwell has the land. I've read most of the Richard Sharpe novels, but I first encountered the grail quest series as audio books from audible. I must say that in combination with narration by Seán Barrett, I was absolutely hooked from the out. Together, they bring 14th century Europe to life like I have never heard before. Cornwell with his words that pump life into long dead stories, and Barret with his voice that just seems to call down through the ages. If only my 2nd form history lessons were like this. But how can history teachers brought up in the 1950's, using text books written by dainty scholars hope to convey a true sense of the times? It may look quaint in a tapestry, but battle with sword and bow is particularly brutal. But of course for the men of the time it was just all part of life. As Cornwell tells the tale of Thomas of Hookton, the grim reality of life leaps from the page with Barrett's voice. Seriously, the best way to "read" the grail quest series is to listen on audible. there are three volumes: Harlequin: The Grail Quest, Book I Vagabond: The Grail Quest, Book II Heretic: The Grail Quest, Book III

A great companion read is 1215: The Year of Magna Carta It is a fascinating - and less dramatic - study of England in the 13th century: the years of Prince John, the legend of Robin Hood and of course the Magna Carta.

It was only after reading this, and having been embued in the era thanks to the Grail Quest audible recordings by Seán Barrett, that I finally got a true sense of the complex relationship between France and England after the Norman conquests of Britain.

And then there is the Magna Carta. Probably more significant as a legend and ideal than an actual statement of rights. In its time, it seems to have been seen by some as a scandalous concession to the masses. Even Pope Innocent III condemned the charter as

..not only shameful and demeaning but also illegal and unjust, thereby lessening unduly and impairing his [the king's] royal rights and dignity

read more and comment..

Oct 7, 2008 Database Oracle

Best Oracle OpenWorld 2008 quote so far..

WSJ blogger Ben Worthen on the HP Oracle Exadata Storage Server:

Oracle now has a device that is kind of like an iPod except that it is a lot bigger and a lot more expensive and not as cool.

"... priced at US$4,000 per terabyte of storage, plus the database license costs" Oh my.
read more and comment..