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

• Amndeep7: Might wanna look here: codereview.stackexchange.com/q/74881/112041
• Eric Lippert: Don't forget to state the problem. Not everyone who reads this site is familiar with PE.

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.

• Flambino: I'd recommend dropping the is_-prefix on that method name too
• Zack: I agree in general, but this instance I also wanted an example of snake_case
• Flambino: Sure, but why not do both? E.g. "For one, it should be is_palindrome? (since Ruby uses snake_case for methods), but you can also drop the is_ since that's implied by the ?. Ruby eschews such prefixes for that reason."

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