Thursday, February 17, 2011

Project Euler–Problem 4

Description

From Project Euler:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Solution

There are two parts to the solution to problem 4. The first part is to generate all the multiples of 3-digit numbers. This is relatively trivial. All we need to do multiple all the combinations of numbers from 100 to 999. The only obvious optimization here is to recognize that 100 * 999 is the same as 999 * 100. So we really only have to compute one of the two.
class Problem004
 def multiples(range)
  Enumerator.new do |yielder|
   range.each do |i|
    (range.first..i).each do |j|
     yielder << i * j
    end
   end
  end
 end
end
Here I’ve used an Enumerator. It simply loops through all the numbers in a range and multiplies those values by all the numbers in the range less than that number. Each time, it yields these values.
The second part of the problem is to determine whether a number is a palindrome or not. This too is straight forward. All we need to do is compare whether the number is equal to its reverse. Since numbers do not have a reverse method, we’ll have to convert it to a string first.
class Integer
 def palindrome?
  text = self.to_s
  text == text.reverse
 end
end
With all of this in place, finding the largest palindrome is as easy as:
Problem004.new.multiples(100..999).select { |x| x.palindrome? }.max
The full source and specifications can be seen on github. Next time, finding the smallest number divisible by each of the number 1 through 20.

No comments: