Project Euler “is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.”

I've been working through some of the projects on the website to help teach myself Ruby in my space time.

Problem 4 of Project Euler states the following:

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.

Just doing some simple calculations, the smallest number that can be generated by two 3 digits numbers multiplied together is:

100 * 100 = 10,000 which is a five digit number.  
An example of a five digit palindrome is 10101

The largest number is:

999 x 999 = 998,001 which is a six digit numbers.
An example of a six digit palindrome is 101101.

With this information in mind, the solution I came up with in Ruby is below.

class Palendromes
 
  def initialize
    @Solutions = []
  end
 
def FindPalendromes
 
  for x in 100..999
    for y in 100..999
 
      a = x * y
      a = a.to_s
      next if(a.length % 2 != 0)  
 
      b = []
      a.scan(/[0-9]/) do |z|
        b << z
      end
 
     @Solutions << a if(isPalendome?(b)) 
 
    end
  end
 
  @Solutions.sort
 
end
 
def isPalendome?(array)
 
  reversearray = array.reverse
  for x in 0..array.length
    return false if array[x] != reversearray[x]
  end
 
  return true
 
end
 
end
 
a = Palendromes.new
solutions = a.FindPalendromes
puts solutions

Starting at the bottom, a is set equal to a new instance of class Palindromes which is initialized with a call to the new method which in turn calls the initialize method which declares a new array called 'Solutions' where all the possible palindromes will be stored.  To find the palindromes, the 'FindPalindromes' method is deployed.  

FindPalindromes creates two loops from 100 to 999 so that every product of two three digit combination of numbers will be checked.  Entering the double for loop, x and y are multiplied together and stored in 'a'.  'a' is converted to a string so it can be more easily manipulated and it's length is checked.  If a is a five digit number and not a six digit number, a is discarded because it is obviously not the 'largest palindrome.'  

Next, using Regular Expressions,  each individual number is extracted from a (which is one long string) and put in individual elements in an newly created array b.  

For example the following conversion is made if a is equal to the string  '123456.'

b = {1, 2, 3, 4, 5, 6} 

This is done so that array functions can be used to check if the number is actually a palindrome.  

Next, b is sent to the method isPalindrome() which checks if the numbers contained in b are of a palindromic nature.  The isPalindrome() method is simple.  The method reverses b and stores the results in 'reversearray,' then, it loops through the length of the array comparing each element.  If an element doesn't match up, it returns false and nothing happens.  If however, every element matches, the isPalindrome method returns true and a is pushed into the Solutions array.

When the double for loop has exhausted every possible triple digit product combination, the solution array is sorted and returned to be printed to the screen.  

The answer is: 906609

My solution, while yielding the correct answer, is not the most elegant solution I discovered (not to my surprise as I am still learning the intricacies of the Ruby Programming language).  On the Project Euler forum, Olathe posted the following code:

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 }."

This code is sick (in a good way). He creates two for loops, finds the product of two three digit numbers, and converts the answer to a string — which is what I did in my code, but this is where the similarities end. Instead of extracting single digits into an array, he simply compares the product string to a reversed product string. If they match (if the number is a palindrome), he compares the number to the previous maximum number stored in the 'max' variable. If bigger then the previous max, he stores the number in match. If less, he discards it. Yes. Very Nice.

Project Euler "is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."

Lot's of programmers recently have been using Project Euler as a form of 'Code Kata:'  a philosophy that believes that greatness comes through diligent practicing.  Steve Yegge written on the subject as well as Kathy Sierra.  The idea is that you can be insanely great at anything if you practice at it.  Sure, some people are natural geniuses — and you will never be better then them.  But if you want to, you can be in the top 1% of learned people on any particular subject.

I'm not sure if I believe them, but heck, i think that the idea inspires lots of mediocre programmers ( like myself ) to wake up each day and learn new stuff.  And that in itself is worth something, right?  I do believe that if you just set aside one hour per day to learn something new, you can become quite proficient in anything at all in a shorter period of time then you even imagined.  Most people have a hard time with this though.  They have a seeing that just one hour per day can lead to incredible results.  I myself was in this category until I learned the 'Til Death Due Us Part' productivity method.  On my Google homepage, I have the following widget on display:

The 'Countdown' widget shows me the (estimated) number of days I have until I die.  Instead of brimming over with horrible sadness everyday, the huge number of days I have left actually motivates me.  I just think about this simple fomula:

Number of Hours Per Day * Number of Days Til Death = Total Number of Hours

If I started today learning Ruby and practiced Ruby one hour per day, by the end of my life I will have practiced Ruby 17,193 hours.  What are you NOT going to be good at after practicing for that long?  With that in mind, you have no excuses.  It is never too late for you to learn anything… well, provided you are not already 83 years old.  Then I'd stick to shuffle board.

I've been teaching myself Ruby the last couple months and just recently started going through the problems on Project Euler.  Problem 3 posed the following question:

The prime factors of 13195 are 5,7,13, and 29
What is the largest prime factor of the number 600851475143?

From wikipedia, "In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder."

My solution to the problem in Ruby is below:

The first dilemma I faced while solving the problem was generating a list of prime numbers.  I'm going to be honest, I didn't generate squat.  I kind of cheated.  I found a list of 10,000 prime number online.  When the class PrimeFactorFinder is initialized, the list of numbers is opened, the prime numbers are "scanned" in using Regular Expressions and added to the array @PrimeNumbers.  There is an way to actually generate prime numbers in Ruby I discovered.  One can use the mathn standard ruby library as seen below:

require 'mathn'
primes = Prime.new
factor = primes.next

The next hurdle was finding the list of prime factors.  This was found by modulo(ing) the numberToFactor by each prime number. If the former expression yields '0′ then the prime number divides into the numberToFactor exactly and is a 'Prime Factor.'

All in all a pretty simple exercise, yet it required me to use Ruby's Arrays, File IO, and Regular Expressions. Code Kata indeed.