5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.