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"

Comments

  1. Here’s a more concise solution:


    digit = [ 4, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 8, 7, 9, 8, 8 ]
    decade = [4, 3, 6, 6, 5, 5, 5, 7, 6, 6]

    puts (1..1000).inject(0) { |sum, n|
    sum, n = sum + 11, n % 1000 if n > 999
    sum, n = sum + digit[n / 100] + (n % 100 > 0 ? 10 : 7), n % 100 if n > 99
    sum, n = sum + decade[n / 10], n % 10 if n > 19
    sum += digit[n] if n > 0
    sum
    }

  2. That’s looks great, Ruby Monk. I completely dig how you eliminated the need to store the actual number word and just dealt with their respective lengths. Good call.

    I know my solution is really bloated and it sure doesn’t speak to the conciseness that Ruby offers. That said, I like the fact that I can actually generate all the words for 1..1000 if I want to — and I did when I was testing/eyeballing my solution.

    Thank you for the comment. Your solution is top notch and I’d love to hear your thoughts on some of my other Euler solutions.

  3. Oops, fifteen contains 7 letters, not 8. And in US spelling the word ‘and’ is not used. To make it up to you, here’s a program that spells words up to 10 ^ 100, which should be enough to count pretty much everything in the universe.

    $digits = %w(_ one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen)
    $decades = %w(_ _ twenty thirty forty fifty sixty seventy eighty ninety)
    $powers = [""] + %w(thousand million billion trillion quadrillion quintillion sextillion septillion octillion nonillion decillion undecillion duodecillion tredecillion quattuordecillion quindecillion sexdecillion septendecillion octodecillion novemdecillion vigindecillion unvigintillion dovigintillion trevigintillion quattuorvigintillion quinvigintillion sexvigintillion septenvigintillion octovigintillion novemvigintillion trigintillion untrigintillion dotrigintillion)

    # Pre-condition: 0 < n && n 99
       w, n = w + $decades[n / 10] + (n % 10 > 0 ? "-" : ""), n % 10 if n > 19
       w, n = w + $digits[n], 0 if n > 0
       w
    end

    # Uses US spelling.
    # Pre-condition: 0 < n 0
       w.gsub(/\s+/, " ").strip
    end

    if ARGV.empty?
       puts "As a price for inventing chess, he asked for #{in_words (2 ** 64 - 1)} grains of wheat."
    else
       n = ARGV[0].to_i
       puts n = 10 ** 102 ? "Out of range." : in_words(n)
    end

  4. Aarg, the HTML filter ate some of the code. Let’s try again:

    # Uses US spelling.
    # Pre-condition: 0 < n && n 0
       w.gsub(/\s+/, " ").strip
    end

  5. Third attempt, this time using only one angle bracket per line.

    # Uses US spelling.
    # Pre-condition: n 0
       w.gsub(/\s+/, " ").strip
    end

  6. Fourth attempt…

    def in_words n
      return "googol" if n == 10 ** 100
       w, i = "", 0
       w, n, i = in_words_1000(n % 1000) + " " + $powers[i] + " " + w, n / 1000, i + 1 while n > 0
       w.gsub(/\s+/, " ").strip
    end

  7. The other function was also mangled.

    def in_words_1000 n
       w = ""
       w, n = w + $digits[n / 100] + " hundred ", n % 100 if n > 99
       w, n = w + $decades[n / 10] + (n % 10 > 0 ? "-" : ""), n % 10 if n > 19
       w, n = w + $digits[n], 0 if n > 0
       w
    end

closed