Monthly Archives: July 2010

Project Euler 21: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 21

Though I could have used it to solve other problems, this problems made it obvious that I need to start caching results as they are calculated for quick look up later in the routine. I didn’t do that here, but I need to start working caching techniques into my solutions. I also need to look into the use of (1..10_000).each versus 10_000.times. I will do a few benchmarks to see which performs better. Feel free to spill the beans and spoil the surprise for me.

As always, any feedback is welcome.

# Euler 21
# http://projecteuler.net/index.php?section=problems&id=21
# Let d(n) be defined as the sum of proper divisors of n
# (numbers less than n which divide evenly into n).
# If d(a) = b and d(b) = a, where a != b, then a and b
# are an amicable pair and each of a and b are called
# amicable numbers.
# For example, the proper divisors of 220 are
# 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110;
# therefore d(220) = 284. The proper divisors of
# 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
# Evaluate the sum of all the amicable numbers under 10000.
require 'mathn'

timer_start = Time.now

class Integer
  def divisors_sum
    n = self
    sum = 1

    (2..Math.sqrt(n)).each do |i|
      sum += n / i + i if n % i == 0
    end

    sum
  end
end

sum = 0

(0..10_000).each do |a|
  b = a.divisors_sum
  sum += a if (a != b && b.divisors_sum == a)
end

puts sum
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"</div>

Two Minutes of Ruby

I love RubyThroughout the year I have introduced myself to a few programming languages and I am currently on my third week with Ruby. Let me start by sharing a few things you have already heard about Ruby. More accurately, let me share my interpretation of things you have already heard. First and foremost, Ruby is fun. You’ve heard this, right? This is usually closely followed by “Ruby is intuitive and concise.” There’s a summarizing statement which gets thrown around often – just write your Ruby code the way you think it should work and it will work. I have the impression that Ruby is magical. Pepper in comments about the language being easy to read, productivity gains, beer and rainbows and you get a pretty good sense of Ruby things. That’s the pro-Ruby spiel at least. Often anti-static-language-with-tooling-support talk gets thrown into the mix too. Don’t let that last sentence give you the wrong impression. This isn’t as much bashing as merely reinforcing ones fondness of Ruby by bringing attention to what some dislike about tools and languages like Visual Studio and C#. That’s right. IDEs are for chumps! Intellisense is your crutch! I’ve got your compiler right here! Okay, I’m having some fun here, but hopefully you get my point. Ruby is enticing on its own merit but, unmistakably, there’s something about other tools/languages which gives Ruby even more appeal.

There’s a rumor that I can explain what you can do in Ruby that’s not really possible in .NET in a mere 2 minutes. Full disclosure, that’s 2 minutes, in person, over lunch. That’s two minutes of me frantically waving my arms around like a crazed lunatic. That’s me holding your head in my heads, forcing you to look me deep into my eyes in search of the truth. That’s me slamming my fists down on the table trying to scare you into seeing the light. You get the picture. With that, start the clock:

The most important thing to know is everything stated in the introductory paragraph is true. Every little bit – even the magical part. You just can’t know that until you have experienced it for yourself or you’ve known me for way too long and my arm-waving, eye-gazing, fist-slamming rants are enough to move your cheese, as they say. Give yourself three weeks and 20 Project Euler Problems and you will believe. And then you can state convincing others over lunch… Go ahead. It’ll be fun. Ruby will feel just like home and your code will just work without an IDE, Intellisence or a compiler.

As I stressed to Jon (who has worked with Ruby), the heart of Ruby is its simplicity and it is found everywhere – in variable declaration, iterations, extending classes, everywhere… And, this, my friends, you just won’t find in C#.

Want to declare a variable in Ruby?

x

The interpreter will figure out the type for you – even if the type needs to change at runtime. In C#, there’s var (which isn’t the same at all), there’s reflection and there’s the dynamic keyword but you can’t easily get mimic this core Ruby functionality.

Want to create a range of values 1 to 10? In Ruby, it’s

(1..10)

In C#, the closest you can get is

Enumerable.Range(1, 10)

and you’re dealing with 3.5+ with Linq. Once you learn how to loop through ranges in Ruby, the thought of writing a C# For loop will make your fingers ache.

Want to extend a class? In Ruby, classes are always open so it’s as easy as

# There's no factorial method in Ruby, I guess.
class Integer
  def factorial
    (1..self).reduce(1, :*)
  end
end

I further shared with Jon how one can redefine or add to any object in Ruby. Jon’s responds was that you can do that in C# with extension methods. Of course, but we all know that extension methods only work if the C# class isn’t sealed and you can’t share the same signature as an existing method.  So it’s not really comparing apples to apples…

As I work with Ruby, I can’t help but consider what Rubyists who have followed C# over the years have been thinking. Even in the context of the trivial examples above, they have to be asking why C#, by comparison, is so verbose and so complicated.

Even in the throes of my current Ruby love fest, I’m not jumping ship. I love C# and I’ll likely stick with it for a while.   After all, it pays the bills.  But, to say the very least, Ruby turns me on and my experience with Ruby has been so eye opening that I encourage you to experience it for yourself.

Project Euler 20: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 20.

I read through this problem and problem 19 yesterday morning before starting off on a family trip from San Diego into the woods of Northern California. With a 19 month old climbing all over me for nearly the entire duration of the two short flights, I worked through the problems in my head and jotted down the solutions on our layover at SFO. There’s nothing mind-blowing going on in either solution, but I’m very pleased that I was able to work through both solutions on paper without having to lean on Google for help with correct Ruby syntax. If you read through my solution for problem 19 you will see that I took some liberties with a switch statement which one would/could never attempt with a language like C# and everything just worked. That’s cool.

The bummer is I misunderstood problem 20 and thought through the wrong solution while on the plane. It’s a subtle difference, but I remembered the problem asking for the sum of all factorial factors, if you will, for 100!. I left that solution commented out below along with the real solution. Don’t be distracted by the useless code please, but I had to keep it in place for memories sake. Someday I’m sure my now 19 month old and I will look back at this family vacation and we’ll talk of Ruby and how it can solve all types of problem — real or fake.

As always, any feedback is welcome.

# Euler 20
# http://projecteuler.net/index.php?section=problems&id=20
# n! means n x (n - 1) x ... x 3 x 2 x 1
# Find the sum of digits in 100!
timer_start = Time.now

class Integer
  # Get the sum of all factorial values up to n 
  def sum_of_factorials 
    f, sum = 0, 0
    
    1.upto(self) { |n| 
      f += n # factorial value of n    
      sum += f # sum of factorial values up to n
      #puts "#{(n)} #{(f)} #{(sum)}"     
      # 1 1 1
      # 2 3 4
      # 3 6 10
      # 4 10 20
      # 5 15 35
      # ...
      # 100 5050 171700     
    }
    
    sum
  end
  
  def factorial
    (1..self).reduce(1, :*)
  end
end

# puts 100.sum_of_factorials

# Correct interpretation of problem.
# Get 100! and get sum of digits
numbers = 100.factorial.to_s.split(//) \
  .map(&:to_i)

puts numbers.inject(:+)

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

Final note: Thanks to Jan Lelis for the valuable feedback on the map() and inject() argument syntax which is featured above and the suggestion to incorporate lambas into my solutions. Jan’s blog is a wealth of Ruby information (including alternate Euler Problem solutions.) If you have been keeping up with my posts, you should check out Jan’s as well — if you aren’t already.

Project Euler 19: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 19.

This problem turned me on about as little as problem 19. If you’re looking for a fancy algorithm, you won’t find it here. This is another brute force solution featuring a bloated yet terribly action-packed Ruby switch statement. I hadn’t used the switch syntax yet. This problem offered up the opportunity and I took abused it. Still focused on learning…

As always, any feedback is welcome.

# Euler 19
# http://projecteuler.net/index.php?section=problems&id=19
# You are given the following information, but you may 
# prefer to do some research for yourself.
#
# - 1 Jan 1900 was a Monday.
# - Thirty days has September,
#   April, June and November.
#   All the rest have thirty-one,
#   Saving February alone,
#   Which has twenty-eight, rain or shine.
#   And on leap years, twenty-nine.
# - A leap year occurs on any year evenly divisible by 4, 
#   but not on a century unless it is divisible by 400.
#
# How many Sundays fell on the first of the month during 
# the twentieth century (1 Jan 1901 to 31 Dec 2000)?
timer_start = Time.now

months_with_thirty_days = [4, 6, 9, 11]

# 1/1/1900 is a Monday (2)
m, d, y, dw = 1, 1, 1900, 2 

def leap_year? y
  return true if y % 400 == 0
  return false if y % 100 == 0  
  y % 4 == 0    
end

num_of_sundays = 0

while(y < 2001)
   # Keep track of Sundays starting in 1901
   num_of_sundays += 1 if (dw == 1 and d == 1 and y > 1900)
   
   #puts "#{(m)}/#{(d)}/#{(y)}, #{(dw)}" 
   
   dw += 1
   dw = 1 if dw == 8 # Reset to Sunday
      
   case d
    when 1..27
      d += 1 
    when 28 && m == 2 && leap_year?(y)     
      d += 1
    when 28 && m == 2 && !leap_year?(y) 
      d, m = 1, 3        
    when 28 
      d += 1      
    when 29 && m == 2
      d, m = 1, 3
    when 29
      d += 1      
    when 30 && months_with_thirty_days.include?(m)
      d, m = 1, d + 1      
    when 30
      d += 1      
    when 31 
      d, m = 1, m + 1
      m, y = 1, y + 1 if m == 13 # Move to 1/1 for next year               
   end   
end  

puts num_of_sunday
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

Project Euler 18: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 18.

I love how this problem description basically says, “Go ahead and brute force the answer but you’ll be sorry you did in about 50 problems from now.” Yikes. I haven’t thought that far ahead yet. I guess it’s comforting to know that someone is looking out for me!

All the same, I took the bait and found a scalable solution. Once again I needed to sketch and consider the problem for a while until the algorithm came to me. Actually, I discovered the solution rather quickly but spent a while trying to disprove my initial instincts. Looking back, there was no reason to doubt myself. Silly Ben…

As always, any feedback is welcome.

# Euler 18
# http://projecteuler.net/index.php?section=problems&id=18
# By starting at the top of the triangle below and moving 
# to adjacent numbers on the row below, the maximum total 
# from top to bottom is 23.
#
# 3
# 7 4
# 2 4 6
# 8 5 9 3
#
# That is, 3 + 7 + 4 + 9 = 23.

# Find the maximum total from top to bottom of the triangle below:

# 75
# 95 64
# 17 47 82
# 18 35 87 10
# 20 04 82 47 65
# 19 01 23 75 03 34
# 88 02 77 73 07 63 67
# 99 65 04 28 06 16 70 92
# 41 41 26 56 83 40 80 70 33
# 41 48 72 33 47 32 37 16 94 29
# 53 71 44 65 25 43 91 52 97 51 14
# 70 11 33 28 77 73 17 78 39 68 17 57
# 91 71 52 38 17 14 91 43 58 50 27 29 48
# 63 66 04 68 89 53 67 30 73 16 69 87 40 31
# 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

# NOTE: As there are only 16384 routes, it is possible to solve 
# this problem by trying every route. However, Problem 67, is the 
# same challenge with a triangle containing one-hundred rows; it 
# cannot be solved by brute force, and requires a clever method! ;o)
timer_start = Time.now

data = \
"3
7 4
2 4 6
8 5 9 3"

data = \
"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"

# Split on newline character
rows = data.split("\n")

# Split rows into two dimensions array and convert to int
triangle = rows.map { |x| x.split(" ") \
  .map { |x| x.to_i } }

# Loop through each row of the triangle starting at the base.
(triangle.length - 1).downto(0) { |a|
  0.upto(a-1) { |b|  
    # Get the maximum value for adjacent cells in current row.
    # Update the cell which would be one step prior in the path
    # with the new total. For example, compare the first two 
    # elements in row 15. Add the max of 04 and 62 to the first 
    # position of row 14.This provides the max total from row 14 
    # to 15 starting at the first position. Continue to work up 
    # the triangle until the maximum total emerges at the 
    # triangle's apex.    
    triangle [a-1][b] += [triangle [a][b], triangle [a][b+1]].max
    # puts triangle [a-1][b]
  }  
}

puts triangle [0][0]
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

Project Euler 17: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 17.

When I first read through this problem, I wasn’t excited in the least. Though I would bet there are very clever and elegant solutions, I knew I would end up brute forcing the answer and I questioned whether going through those motions would be worth my time. Truth told, I had decided to skip this problem altogether and then Jon convinced me to “just do it.” Though I am not particularly proud of my solution, I learned a few more things about Ruby so, yes, it was worth my time. With any luck, my discoveries are expressed fairly well in the comments.

If you have an alternate solution, even pseudo-code, I’d love to hear about it. As always, any feedback is welcome.

# Euler 17
# http://projecteuler.net/index.php?section=problems&id=17
# If the numbers 1 to 5 are written out in words: 
# one, two, three, four, five, then there are 
# 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
# If all the numbers from 1 to 1000 (one thousand) 
# inclusive were written out in words, how many letters 
# would be used?
#
# NOTE: Do not count spaces or hyphens. For example, 342 
# (three hundred and forty-two) contains 23 letters and 
# 115 (one hundred and fifteen) contains 20 letters. The 
# use of "and" when writing out numbers is in compliance 
# with British usage.
timer_start = Time.now

class Integer
  def to_word
    # Interesting, if I rearrange the unless clause to 
    # read unless self === (1..1000) the exception is
    # always raised.
    raise ArgumentError, "Integer must be between 1 " \
      + "and 1000" unless (1..1000) === self
      # self.between?(1,1000) would work too.
          
    h = { 1 => "one", 2 => "two", 3 => "three", 
      4 => "four", 5 => "five", 6 => "six", 
      7 => "seven", 8 => "eight", 9 => "nine", 
      10 => "ten", 11 => "eleven", 12 => "twelve",
      13 => "thirteen", 14 => "fourteen", 15 => "fifteen",
      16 => "sixteen", 17 => "seventeen", 18 => "eighteen",
      19 => "nineteen", 20 => "twenty", 30 => "thirty",
      40 => "forty", 50 => "fifty", 60 => "sixty",
      70 => "seventy", 80 => "eighty", 90 => "ninety",
      100 => "hundred", 1000 => "thousand" }
    
    word = ""
    
    # Reverse the numbers so position (ones, tens, 
    # hundreds,...) can be easily determined
    a = self.to_s.reverse.split(//).map { |char| char.to_i }

    # Thousands position
    if (a[3] != nil and a[3] != 0) 
      # This can only be one thousand based 
      # on the problem/method constraints
      word = h[a[3]] + " thousand "     
    end
    
    # Hundreds position
    if (a[2] != nil and a[2] != 0) 
      word += h[a[2]] + " hundred"
      
      # Add "and" string if the tens or ones 
      # position is occupied with a non-zero value.
      # Note: routine is broken up this way for [my] clarity.
      if (a[1] != nil and a[1] != 0) 
          # catch 10 - 99
          word += " and"
      elsif a[0] != nil and a[0] != 0
          # catch 1 - 9
          word += " and"
      end        
    end
              
    # Tens and ones position
    tens_position_value = 99
    if (a[1] != nil and a[1] != 0)  
      # Calculate the tens position value per the
      # first and second element in array
      # e.g. (8 * 10) + 1 = 81 
      tens_position_value = a[1] * 10 + a[0]
      
      if tens_position_value <= 20
        # If the tens position value is 20 or less
        # there's an entry in the hash. Use it and there's
        # no need to consider the ones position  
        word += " " + h[tens_position_value]    
      else
        # Determine the tens position word by
        # dividing by 10 first. E.g. 8 * 10 = h[80]
        # We will pick up the ones position word later in
        # the next part of the routine        
        word += " " + h[(a[1] * 10)]               
      end
    end
    
    if (a[0] != nil and a[0] != 0 and tens_position_value > 20) 
        # Deal with ones position where tens position is 
        # greater than 20 or we have a single digit number        
        word += " " + h[a[0]]        
    end
    
    # Trim the empty spaces off both ends of the string
    word.strip
  end
  
   def to_word_length     
     self.to_word.gsub(/ /,'').length          
     
     # I original wrote the result as follows:
     #    self.to_word.gsub(' ','').length
     # but from what I've read it seems that providing 
     # a regex as the first argument is more Ruby-like
   end
end

puts (1..1000).inject(0) { |agg, i| agg + i.to_word_length }

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"

Project Euler 16: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 16. I am finding a few of my recent solutions are dangerously similar. Perhaps I should be worried that I am getting locked into a single-minded approach. I’ll have to watch out for this. As always, any feedback is welcome.

# Euler 16
# http://projecteuler.net/index.php?section=problems&id=16
# 2^15 = 32768 and the sum of its digits is 
# 3 + 2 + 7 + 6 + 8 = 26. 
# What is the sum of the digits of the number 2^1000?
timer_start = Time.now

numbers = (2**1000).to_s \
  .split(//) \
  .map { |char| char.to_i }

puts numbers.inject { |agg, n| agg + n }

puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"


Windows Live Sync and the Absolutely Absurd Error Message

Apparently customers wanted to know why Microsoft had two services – Windows Live Sync and Live Mesh beta – with similar features.  In response, Microsoft has announced that Live Mesh will soon be replaced by the new Windows Live Sync which will be built out using the Mesh technology. 

I have been using Windows Live Mesh for a while and even though there are some quirks I am happy with the product.  That said, if Microsoft wants to merge these services together to form one super end-user experience, I’ll be the first in line.  So, with little prompting, I installed the Live Sync Beta bits and abandoned Mesh without a second thought this past weekend.  I was plugged into SkyDrive and reaping additional Sync benefits after spending only a quick 30 minutes on the install and folder re-synchronization. Small price to pay, I guess. 

Everything has been fine since the switch.  That is until yesterday when I did the unthinkable; I shutdown my laptop before leaving the office and then I started it back up when I arrived home!  What the heck was I thinking?  Why did I ever think Windows Live Sync could handle such a drastic and unanticipated user action?  But there was hope – an error message:

Sorry, there was a problem with Windows Live Sync.  Please restart your computer. If the problem persists, please reinstall Sync. 

Seriously?  I get it.  It’s beta software, and stuff breaks, but is this the most absurd message ever?

You may have caught on to the fact that I develop software.  You probably do too.  Well, can you imagine getting away with a message like this?  Even if you were shipping beta software?

So, product-development-manager-person-who-should-hopefully-help-me-make-good-decisions-and-keep-me-from-coding-anything-amazingly-stupid-into-the-product, there’s a possibility that my software will fail when users bring up their systems. If users never start up their systems, there’s no reason for concern, but on the off chance that they do, well, we should be ready.  I know Windows Update prompts me to install updates and restart my own machine every 14 minutes so there’s at least a small chance that someone will reboot sometime, right? 

So, I’ve been brainstorming possible ways to handle the issue, as unlikely as it may be.  Rather than just fixing the problem, I think I am going to display an error message.  That should save me tons of development time…

First, I’ll apologize to the user for the inconvenience.  That’s seems appropriate.  After all, I am sorry that I won’t be fixing the issue before the beta version is released. I was thinking about making the error message fun, but I think I’m going to keep it serious and very vague.  Serious and vague is better, right?  So I’ll start by telling the user that there was “a problem.”  Period.  No explanation – I’ll just state the obvious and really drive that “problem” point home while keeping the user completely in the dark.

And then I’ll suggest the two most drastic and unlikely fixes any developer could dream up. I’m talking about stuff that only incompetent technical support folks can get away with saying.  So my question for you is, can I actually get away with wasting the user’s time with a system reboot or should I just have them reinstall the software which is already known to fail? Right. I should definitely have them reboot first.  That should keep them busy and give them time to cool off before publishing that flaming blog post.  Good thinking.

Okay. I’m done. Thanks for sticking with me.  Hopefully this hasn’t come across as too much of a rant and hopefully there’s a lesson learned in this post somewhere.  I’ll get back to actual coding in my next post.