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.

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)

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

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
  

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

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.