Ruby solution to Project Euler Problem #4: Largest palindrome product

Question

I've solved the Project Euler Problem #4, but I'd like some tips as to how to make this more efficient. I am a beginner to Ruby, so please be nice about the stupid stuffs (but still tell me about it).

Project Euler 4: Largest palindrome product

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. 1

class Euler4
  def isPalindrome(n)
    n == n.to_s.reverse.to_i
  end
end

  puts "Setting Variables"
  x = 999
  y = 999

  highest = 1

  found = false

  while (x > 100 && !found)
    y = 999
    while (y > 100 && !found)
      puts "Working with"
      puts x
      puts " and "
      puts y

      if Euler4.new.isPalindrome(x*y)
        puts "Found Palindrome"
        puts x
        puts y
        puts x*y
        if highest < (x*y)
          highest = x * y
        end
      end
      y = y - 1
    end

    x = x - 1

  end

puts "Highest Found"
puts highest

Answer 1

Let's start with something small:

def isPalindrome(n)
  n == n.to_s.reverse.to_i
end

How do I know if a number is a palindrome?

• Convert it to a string.
• Produce the reverse of that string.
• Convert the reversed string to a number.
• Compare the numbers for equality.

As yourself: why did we need to do the last two steps? We could have said:

• Convert it to a string.
• Produce the reverse of that string.
• Compare the strings for equality.

and skipped the "convert to integer" step entirely.

Next small thing. I've removed every line of your program that does not use variable found:

found = false
while (x > 100 && !found)
  while (y > 100 && !found)

See any problems with that code? Because I don't see anywhere that it is set to true and therefore it will always be false. I'm not sure why a variable that is always false is of use to you.

Next thing: You check all pairs: (999, 999), (999, 998), ... (999, 101) and then start over again with (998, 999). But you already checked (998, 999) when you checked (999, 998)! You don't need to start y at 999. It suffices to start y at x. Then you only check each pair once instead of checking the vast majority of them twice.

Next thing: If you find an (x, y) pair that is a palindrome, you don't need to check (x, y - 1); even if it is a palindrome, it will be smaller. Probably this is what you were trying to do with your "found" variable, but you never wrote the logic correctly.

Next thing: Remove all that print-debugging trace. If you need to debug your program, use a debugger.

Answer 2

Some style comments:

First, you don't need to put isPalindrome() in a class, you can simply declare it and use it directly. Additionally, the ruby preferred style is to use snake_case and if the function is a predicate (a function that takes a value and returns true/false) you should add a question mark to the end:

def is_palindrome?(n)
  # ...
end

# usage
is_palindrome? 6006    # => true
is_palindrome?(1234)   # => false   

Second, you have some code that looks like this:

x = 999
while (x > 100)
  # ...
end

Ruby has constructs for this called Ranges and Enumerators. Ranges are a collection of sequential numbers while enumerators are looping constructs that iterate over a collection, like items in an array or the numbers in a range. While ranges only count up, there is a function for counting down, downto() that returns an enumerator.

# Range Example: Counting Up
(5..9).each { |i| print i }  # .each here makes an enumerator over the range
# => 12345

# Enumerator Example: Counting Down
9.downto(5) do |i|   # downto() creates an enumerator that starts at 9 and ends at 5
  print i
end
# => 98765

Finally, you have code like:

puts "Found Palindrome"
puts x
puts y
puts x*y

Ruby has several ways to conveniently print text. First there is string interpolation. You use double quotes on the string, and use #{ code } inside the string. When ruby parses the string the code is executed and the results replace the code in the string.

puts "Found a palindrome: #{x} x #{y} = #{x*y}"
# => "Found a palindrome: 993 x 913 = 906603"

Ruby also has C-style format strings. Use '%d', %f', '%s', etc in the string and then supply an array at the end of the string with all of the arguments.

puts "Found a palindrome: %d x %d = %d" % [x, y, x*y]
# => "Found a palindrome: 993 x 913 = 906603"

Some Code Comments

Like Eric mentioned, you can speed things up by not doing duplicate work and intelligently managing the values you loop over.

Answer 3

As mentioned, if you've tried 999 * 998 you don't also need to check 998 * 999 since the result is the same. But you can also limit the range by setting the lower bound to the lower of the two factors that produce a palindrome.

E.g. a = 995 and b = 583 produces a palindrome: 580085. We don't know if it's the highest, but we know that for a palindrome to be greater, the smaller of its factors must be equal to or greater than b.

We could keep decrementing b, and we'd find 995 * 517 = 514415 - but why bother?

So for the next loop, we only need to try the range 994..583.

One (quickly written) way to do this could be:

palindromes = []
minimum = 100    # initial lower bound

999.downto(minimum) do |a|
  a.downto(minimum) do |b|
    product = a * b
    if product.to_s.reverse == product.to_s
      minimum = b                    # set new lower bound
      palindromes << [a, b, product] # note the factors and product
      break                          # break out of inner loop
    end
  end
end

# find and print the greatest palindrome
a, b, product = palindromes.max_by(&:last)
puts "#{a} * #{b} = #{product}"

This tries 7227 combinations (curiously, that's a palindrome itself), and finds 5 candidate palindromes.

But it can be improved more. The above only raises the lower bound if it finds a palindrome, but whether or not the product's a palindrome, we can raise the lower bound if that product is smaller than a previously found palindrome. E.g.:

greatest_palindrome = 0
minimum = 100

999.downto(minimum) do |a|
  a.downto(minimum) do |b|
    product = a * b

    # if it's a palindrome, store it
    if product.to_s.reverse == product.to_s
      greatest_palindrome = product
    end

    # if the product is smaller than a known palindrome, we can
    # raise the lower bound
    if product <= greatest_palindrome
      minimum = b
      break
    end
  end
end

puts greatest_palindrome

Now it's down to 6166 tries.

Answer 4

There are already some good answers that address the problems of your code, I have nothing to add on this regard. But I'd like to propose a different approach, declarative and functional:

module MathFunctions
  def self.palindrome?(n)
    n.to_s.reverse.to_i == n
  end
end

module ProjectEuler
  def self.problem4
    products = (100..999).to_a.repeated_combination(2).map { |x, y| x * y }
    products.select { |p| MathFunctions.palindrome?(p) }.max
  end
end