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

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

• Might wanna look here: codereview.stackexchange.com/q/74881/112041 Commented Jul 27, 2016 at 16:04
• Don't forget to state the problem. Not everyone who reads this site is familiar with PE. Commented Jul 27, 2016 at 16:09

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.

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"


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

• I'd recommend dropping the is_-prefix on that method name too Commented Jul 27, 2016 at 18:59
• I agree in general, but this instance I also wanted an example of snake_case
– Zack
Commented Jul 27, 2016 at 19:29
• 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." Commented Jul 27, 2016 at 19:33

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.

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