In Programming, Just Getting The Right Answer Is Not The Answer

9 Dec

I decided for sure that Ruby is what I’m going to learn next. So to learn, I am going through the Programming Ruby 1.9 (3rd edition) book. Unfortunately, the book does not contain any practice quizes.

So to get some practice, I’ve started completing the problems on Project Euler. I am able to get the correct answers to these problems pretty quickly, but looking through the forums afterwards makes me realize that I still have a ton to learn, especially about efficiency. My programs, although they get the correct answer, take a really long time to run and tend to be way more lines of code than they need to be!

Here is an example from Problem 4, which has the following instructions:

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.

Here is my code, which took the computer about 30 seconds or so to run:

# Problem 4
# ----
#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.
# ----

#checks to see if the number is a palindrome
def isPalindrome(num)
  isPalindrome = true

  #converts the number into a string and then into an array
  numarray = num.to_s.split(//)

  #this array holds the first half of the number
  array1 = numarray[0, numarray.length/2]

  #this array holds the second half of the number
  array2 = numarray[numarray.length/2, numarray.length]

  #check to see if the numbers stored in array1 are equial
  #to the numbers in stored in array2 in reverse order
  for i in 0...numarray.length/2

    #sets isPalindrome to false if there are any unequal numbers
    #between the 2 arrays
    if array1[i] != array2[-1 * (i+1)]
      isPalindrome = false
    end

  end

  #returns true if the number is a Palindrome
  return isPalindrome
end

#stores the largest palindrome
largestPalindrome = 0

for i in 100..999
  for j in 100..999
    #multiply all the three digit numbers
    product = i * j

    #if the product is a palindrome and larger than the largestPalindrome,
    #it becomes stored as the largestPalindrome
    if isPalindrome(product) == true and product > largestPalindrome
      largestPalindrome = product
    end

  end

#prints out the largest Palindrome
puts largestPalindrome
end

Upon getting the answer, I came across this solution in the thread section by someone with the user name of Olathe:

max = 0
100.upto(999) { |a|
  a.upto(999) { |b|
    prod = a * b
    max = [max, prod].max if prod.to_s == prod.to_s.reverse
  }
}
puts "Maximum palindrome is #{ max }."

Olathe’s code is extremely elegant, and runs in about 3 seconds!

So, from now on, I will not only strive to just get the solution, but also get the solution in the most efficient way possible.

Advertisements

2 Responses to “In Programming, Just Getting The Right Answer Is Not The Answer”

  1. DM December 16, 2011 at 11:54 am #

    Awesome find, thanks.
    Gonna have to do some of those problems 😉

Trackbacks/Pingbacks

  1. Brain food: Project Euler | Got-fu? - December 16, 2011

    […] This project has been around for years, but I only just stumbled on it via another post. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s