Route 55 (and Route 19)

(Stackoverflow reputation down to 2232 after they cleaned up some over-voted stuff from the early days, sniff)

While I prevaricate over all kinds of things, including a redesign of the xlUnit interface, I have been enjoying Michael‘s series of articles on Project Euler solutions in VBA, posted at Daily Dose of Excel. There are some ingenious solutions to long-standing VB/VBA deficiencies, not least the absence of built-in facilities for handling arbitrarily large numbers beyond double precision variables.

I have an abiding fondness for the “classic” VB family – not least because it was the skill that fed and housed me and my family for a good 15 years or more. But boy, it can look a bit tired these days.

As it happens, I’d been taking a few shots at the Euler problems myself, but in Ruby, since that’s my language of choice these days (not least because much of my working day is currently spent working on intranet applications using Rails). So it was interesting to compare the two.

Let’s take problem 55. I took Michael’s code (with the neat little large number AddAsStrings routine) into Excel on my whizz-bang dual-dual-Xeon machine and it solved the problem in 0.554 seconds, which, considering the amount of string-based arithmetic that’s going on, is a testament to the speed of modern PCs.

Below is my Ruby version, which takes a rather different approach. Firstly, in Ruby we have support for arbitrarily large numbers, via the built-in Bignum class, so the string adding business is taken care of. Secondly, classes in Ruby, even compiled standard ones, are open to modification, via a technique colloquially known as monkey-patching. So I could patch in a method directly to the Integer class, which seems appropriate, since we’re looking for a property of the number.

Here’s the code:

class Integer
  def lychrel?(max = 50)
    temp = self
    max.times do
      temp = temp + temp.to_s.reverse.to_i
      return false if temp.to_s == temp.to_s.reverse
    end
    true
  end
end
puts (1..9999).inject(0) { |t, i| t + (i.lychrel? ? 1 : 0) }

That took 0.410 seconds on the same machine. I can see at least one inefficiency: calling to_s twice on the same number, which is expensive.

On the other hand, VBA has the edge on problem 19. I spotted a little optimisation in Michael’s code, which gave me this in VBA, which is about 20 times faster at 0.0019 seconds than the original:

Dim Start   As Date
Dim Answer  As Long
Start = DateSerial(1901, 1, 1)
Do While Start < DateSerial(2001, 1, 1)
   If Weekday(Start) = vbSunday Then
      Answer = Answer + 1
   End If
   Start = DateSerial(Year(Start), Month(Start) + 1, 1)
Loop
Debug.Print Answer

Ruby’s Date class doesn’t do anything clever with months outside the 1 to 12 range, so I had to inject a little logic, but otherwise we’re pretty much in synch, algorithmically:

d = Date.new(1901,1,1)
end_date = Date.new(2000,12,31)
until d > end_date do
  res += 1 if d.cwday == 7
  y, m = d.year, d.month + 1
  y, m = y + 1, 1 if m > 12
  d = Date.new(y, m, 1)
end
puts res

Not much in it, lines-of-code wise as you’d probably expect, but the Ruby code takes about 0.36 seconds, which is a hell of a difference.

Call it one-all for now.