Project Euler problem 4 in Ruby

Question

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 ×ばつ 99. Find the largest palindrome made from the product of two 3-digit numbers.

I started out with this solution. It's iterative, and not very efficient. It multiplies all number combinations, adds the products to an array, finds the palindromes, then chooses the max.

def palindrome?(number)
 number.to_s == number.to_s.reverse
end
def largest_palindrome(range = 1..999)
 array = []
 range.each do |x|
 range.each do |y|
 array.push(x * y)
 end
 end
 array.select { |n| palindrome?(n) }.max
end
puts largest_palindrome

I improved with my second iteration, but it still relies on iteration. I narrowed the range down reasoning that the largest palindrome is likely to be the product of two numbers within 901 and 999. This time I multiplied all the numbers, but only saved the palindromes in the array, then selected max, which saved a step. It's noticeably faster, but still not optimal.

def largest_palindrome(range = 1..99)
 palindromes = []
 range.end.downto(range.begin).each do |x|
 range.end.downto(range.begin).each do |y|
 palindromes << x * y if palindrome?(x * y)
 end
 end
 palindromes.max
end
puts largest_palindrome 901..999

My reasoning about narrowing the range feels like cheating. It's intuitive, and arbitrary.

Answer 1

Algorithm

You can increase the efficiency of the algorithm by making use of two facts (particularly the second one):

• Given m and n, m < n, the largest palindrome m*j, m < j <= n, if there are any, is the one for which j is largest. In other words, with m fixed, we can look for palindromes m*j, beginning with j = n and then successively reduce j until either a palindrome is found or we conclude there are no palindromes m*j for m < j <= n. If a palindrome mk is found, then (for fixed m) there is no need to consider values of j for which m < j < k, as we have found the largest palindrome whose smaller factor equals m and whose larger factor is between m+1 and n.

• If a palindrome k*l has been found, where k < l <= n, then in order for i*j > k*l, where i < k, i < j <= n, we see that j > k*l/i (regardless of whether i*j is a palindrome). In other words, there is no need to check to see if i*j is a palindrome for j <= k*l/i, as it cannot be larger than the currently largest known palindrome. Moreover:

  • if i*j, is found to a palindrome, where k*l/i < j <= n, it becomes the currently largest known palindrome; and
  • if k*l/i > n, we are finished, as no product e*f, e <= i, e < f <= n, can be larger than the currently largest known palindrome.

These two observations are implemented in a straightforward way by the code that follows.

Code

def largest_palindrome(low=1,n)
 best = { product: false }
 (n-1).downto(low) do |start1|
 start2 = best[:product] ? (best[:product]/start1.to_f).ceil : start1+1
 break if start2 > n
 found2 = n.downto(start2).find { |j| palindrome?(start1*j) }
 best = { product: start1*found2, v1: start1, v2: found2 } if found2
 end
 best
end 
def palindrome?(n)
 (s = n.to_s) == s.reverse
end

Examples

largest_palindrome(99)
 # {:product=> 9,009, :v1=> 91, :v2=> 99,
 # :smaller_at_term=> 90, :nbr_palins=>1, :soln_time=>"0.00004"}
largest_palindrome(999)
 # {:product=> 906,609, :v1=> 913, :v2=> 993,
 # :smaller_at_term=> 907, :nbr_palins=>2, :soln_time=>"0.00101"}
largest_palindrome(9,999)
 # {:product=> 99,000,099, :v1=> 9901, :v2=> 9999,
 # :smaller_at_term=> 9,900, :nbr_palins=>1, :soln_time=>"0.00178"}
largest_palindrome(99,999)
 # {:product=> 9,966,006,699, :v1=> 99681, :v2=> 99979,
 # :smaller_at_term=> 99661, :nbr_palins=>1, :soln_time=>"0.02040"}
largest_palindrome(999,999)
 # {:product => 999,000,000,999, :v1=> 999,001, :v2=> 999,999,
 # :smaller_at_term=> 999,000, :nbr_palins=>1, :soln_time=>"0.20434"}
largest_palindrome(9,999,999)
 # {:product=>99,956,644,665,999, :v1=>9,997,647, :v2=>9,998,017,
 # :smaller_at_term=> 9,995,665, :nbr_palins=>1, :soln_time=>"2.05677"}

I have formatted the numbers to make them easier to read and also added three statistics I thought might be of interest:

• the value of the smaller of the two factors when the search was terminated;
• the number of palindromes found before the search terminated; and
• the solution time in seconds (on a newish Mac).

To see where each search terminated, divide best[:product] by n, round up and subtract 1. For example, for n = 9999, this would be:

(99000099/9999.0).ceil - 1 #=> 9900

This shows that when determining the largest palindrome for numbers up to 9,999, it was only necessary to consider pairs with values greater than 9,900. Hence, at most (9999-9900)*(9999-9901) => 99*98 => 9,702 pairs were examined, which is 0.0097% of all 9999*9998 => 99,970,002 pairs of numbers up to 9,999.

For n = 999, two palindromes were found before the search terminated. In each of the other four examples, only one palindrome (i.e., the largest) was found before the search terminated.

• Mohamad: I think I need to brush up on my math. Great answer. Thanks. So many good answers, it's hard to choose one. I like this optimisation too (converting to_s once): (s = n.to_s) == s.reverse I didn't know it was possible.
• 200_success: Excellent analysis. But why do you misspell it as palendrome? I see that you are aware of the correct spelling. Is it a deliberate decision to take parameters low and high instead of a range? Also, having a default for the first parameter but not the second is unusual.
• Cary Swoveland: @200_success, I noticed the misspelling when I did the benchmark. At the time I made a mental note to correct the spelling in my answer. Later I remembered I had made a mental note about my answer, but couldn't remember what it was! Thanks! (Fixed.) As to the defaults, I just didn't give much thought to that.

Answer 2

I prepared a benchmark, mainly to emphasize the importance of choosing an efficient algorithm.

module Methods 
 def mohamad(n)
 range = 1..n
 palindromes = []
 range.end.downto(range.begin).each do |x|
 range.end.downto(range.begin).each do |y|
 palindromes << x * y if palindrome?(x * y)
 end
 end
 palindromes.max
 end

 def success(n)
 range = 1..n
 array = []
 range.each do |x|
 x.upto(range.end) do |y|
 array.push(x * y) if palindrome?(x * y)
 end
 end
 array.max
 end

 def caridorc(max)
 min = 1
 palindromes = []
 range = (min...max)
 (min...max).each do |x|
 (min...max).each do |y|
 prod = x*y
 palindromes << prod if palindrome?(prod)
 end
 end
 palindromes.max
 end

 # Helpers are defined below, outside module 
 def tokland(n)
 range = (1..n)
 range.repeated_combination(2).map { |x, y| x * y }.select(&:palindrome?).max
 end

 def britishtea(n)
 range = 1..n
 palindrome = 0
 max = range.end
 range.each do |x|
 max.downto(x) do |y|
 product = x * y
 if product > palindrome && palindrome?(product)
 palindrome = product
 break
 end
 end
 end
 return palindrome
 end

 def cary(low=1,n)
 best = { product: false }
 (n-1).downto(low) do |start1|
 start2 = best[:product] ? (best[:product]/start1.to_f).ceil : start1+1
 break if start2 > n
 found2 = n.downto(start2).find { |j| palindrome?(start1*j) }
 best = { product: start1*found2, v1: start1, v2: found2 } if found2
 end
 best[:product]
 end 

 private
 def palindrome?(n)
 (s = n.to_s) == s.reverse
 end
end

# Tokland's helpers
class Fixnum
 def palindrome?
 to_s == to_s.reverse
 end
end
class Range
 def repeated_combination(n)
 to_a.repeated_combination(n).lazy
 end
end

include Methods
methods = Methods.instance_methods(false)
puts "methods = #{methods}"
 # methods = [:mohamad, :success, :caridorc, :tokland, :britishtea, :cary]
len_longest_name = methods.map(&:size).max 
def compute(n, m) send(m, n) end

Confirm methods return the same value

n = 999
pals = methods.map { |m| compute(n,m) }
if pals.uniq.size == 1
 puts "All return same value #{pals.first}"
else
 methods.zip(pals).each { |m,p|
 puts "#{m.to_s.ljust(len_longest_name)}: #{p}, #{p.class}" }
end
 # All return same value 906609

Benchmark code

require 'benchmark'
[99, 999, 9999, 99999].each do |n|
 puts "n = #{n}\n\n"
 Benchmark.bm(len_longest_name) do |bm|
 methods.each do |m|
 bm.report m.to_s do
 compute(n, m)
 end
 end
 end
end

Results

n = 99
 user system total real
mohamad 0.000000 0.000000 0.000000 ( 0.004248)
success 0.000000 0.000000 0.000000 ( 0.001942)
caridorc 0.010000 0.000000 0.010000 ( 0.003965)
tokland 0.000000 0.000000 0.000000 ( 0.005438)
britishtea 0.000000 0.000000 0.000000 ( 0.000669)
cary 0.000000 0.000000 0.000000 ( 0.000041)
n = 999
 user system total real
mohamad 0.430000 0.000000 0.430000 ( 0.428956)
success 0.220000 0.000000 0.220000 ( 0.217869)
caridorc 0.430000 0.000000 0.430000 ( 0.426822)
tokland 0.570000 0.000000 0.570000 ( 0.579525)
britishtea 0.060000 0.000000 0.060000 ( 0.055914)
cary 0.000000 0.000000 0.000000 ( 0.001627)
n = 9999
 user system total real
mohamad 48.710000 0.070000 48.780000 ( 48.864148)
success 23.740000 0.030000 23.770000 ( 23.789719)
caridorc 49.060000 0.230000 49.290000 ( 49.353672)
tokland 69.870000 0.200000 70.070000 ( 70.460212)
britishtea 4.690000 0.010000 4.700000 ( 4.702356)
cary 0.000000 0.000000 0.000000 ( 0.002379)
n = 99999
 user system total real
britishtea 471.040000 0.830000 471.870000 (472.665509)
cary 0.030000 0.000000 0.030000 ( 0.025619)

• Mohamad: Wow. That's impressive actually. Thanks for taking the time.
• britishtea: Very cool! I'd recommend using benchmark-ips for Ruby benchmarking in the future. It counts iterations per second instead of execution time, especially handy if execution time is very short. Plus it has a handy #compare! :D
• Cary Swoveland: Thanks for the suggestion, @britishtea. The one thing I particularly recommend when benchmarking is to put the methods to be compared in a module to be included. Not only does that provide an easy way to get a list of the methods, for subsequent use with send, but it allows methods to be added, removed or renamed without having to change any of the other code.

Answer 3

There's nothing about Project Euler problems that requires you to find the answer by relying entirely on programming. Narrowing down the possibilities by thinking things through is encouraged, and in later problems, essential. That said, you still need to mentally justify any shortcuts taken, ideally documented in a comment.

In this case, narrowing down the range to 901..999 isn't obviously justified. For example, (900 ×ばつかける 999 =わ 899100)> (901 ×ばつかける 901 =わ 811801). You still need to show that there is no palindromic product involving a number under 900 that is greater than 913 ×ばつ 993. Knowing that a candidate answer involves 993, you just need to check for possible better answers involving 994, 995, 996, 997, 998, and 999.

That said, using 100..999 for the range would be the fastest way to resolve that issue — especially when you take into account the time you spend writing the code.

I'll just review your second solution. There is no advantage to iterating through the range backwards, so you may as well use range#each normally. However, due to symmetry from the commutative property of multiplication, you can cut out half of the work.

def largest_palindrome(range)
 array = []
 range.each do |x|
 x.upto(range.end) do |y|
 array.push(x * y) if palindrome?(x * y)
 end
 end
 array.max
end
puts largest_palindrome 100..999

• Mohamad: Nice. Thanks. Great stuff here: x.upto(range.end).

Answer 4

Various small improvements:

• Instead of requiring a range as the input for your function, it is clearer to require the max number, this simplifies your function to:

  def largest_palindrome(min = 1, max = 999)
   palindromes = []
   (min...max).each do |x|
   (min...max).each do |y|
   palindromes << x*y if palindrome?(x*y)
   end
   end
   palindromes.max
  end
  

• You calculate the product of x and y twice, you can save many multiplications if you save that in a variable:

  def largest_palindrome(min = 1,max = 999)
   palindromes = []
   (min...max).each do |x|
   (min...max).each do |y|
   prod = x*y
   palindromes << prod if palindrome?(prod)
   end
   end
   palindromes.max
  end
  

• Another optimization that also makes the code simpler is calculating range at the start, instead that in all loops.

   def largest_palindrome(min = 1,max = 999)
   palindromes = []
   range = (min...max)
   range.each do |x|
   range.each do |y|
   prod = x*y
   palindromes << prod if palindrome?(prod)
   end
   end
   palindromes.max
  end
  

• Mohamad: Good stuff. Not sure I agree about the last one. I also think the multiplication is trivial, but I see your point.
• britishtea: You're creating the Range, but then aren't doing anything with it.
• Caridorc: @britishtea Excellent point, it should be better to use range.each

Answer 5

If this were an isolated problem, then sure, go along with custom code and explicit loops. But on Project Euler you are going to re-use a lot of these functions, so you better take a more modular/functional/declarative approach. You are taking elements from a set with repetition but order is not important, that's Array#repeated_combination(n). Now, let's start with the roof: wouldn't it be great to write this?

def largest_palindrome(range)
 range.repeated_combination(2).map { |x, y| x * y }.select(&:palindrome?).max
end

Now just fill the gaps (add this code to the common module):

class Fixnum
 def palindrome?
 to_s == to_s.reverse
 end
end
class Range
 def repeated_combination(n)
 to_a.repeated_combination(n).lazy
 end
end

• Mohamad: That's great. It looks a lot cleaner. Do you mind explaining the approach a little bit? In particular the combination method? I'm not sure I understand the logic very well.
• tokland: I've updated the answer, the combination is a repeated_combination.
• Mohamad: Thanks. This is definitely the cleanest solution of the lot, although not as performant as Cary's.
• tokland: Yeah, lazy objects in Ruby are pretty slow. Try removing the .lazy to test, it should be faster.

Answer 6

Your solution calculates much more products than it needs to. The product 100*101, for example, is calculated when x = 100, y = 101 and when x = 101, y = 100. You can throw out roughly half the calculations by starting the inner loop from x instead of range.begin. The products have already been calculated.

By making the inner loop count down, we can skip some additional calculations. If we find a palindrome where y = 89, all products we'll calculate after will always be lower. So we can skip the rest of the inner loop.

It's unnecessary to store all possible palindromes and find the largest later. We can store only the largest and keep our memory usage down.

You want to do as little work as possible in the inner loop. It saves some unnecessary method calls. The biggest win is in avoiding to check whether a given product is a palindrome. If the product isn't larger than the largest palindrome we've found yet, we needn't bother checking if it's a palindrome at all!

Doing less work in the inner loop is also why range.end is cached in a local variable. It avoids range.end method lookups.

def b(range = 10..99)
 palindrome = 0 # Only keep a maximum value, not a whole array.
 max = range.end # Cache the value, to avoid unnecessary method calls.
 range.each do |x|
 max.downto(x) do |y|
 product = x * y
 if product > palindrome && palindrome?(product)
 palindrome = product
 break # y is counting down, so any product is guarenteed to be smaller
 end
 end
 end
 return palindrome
end

I've benchmarked the two algorithms. With these optimisations it is about 5.9 times faster.