21 Jan 09 Project Euler: Problem 4 in Ruby

This one was my favorite, probably because it's been the least mathy so far. I was also tickled pink by the idea of numbers being palindromes. I saw some other solutions on-line but I was really happy with how mine turned out.

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.

My Solution:

def get_highest_palindrome high, low
  highest = 0
  high.downto low do |i|
    high.downto low do |j|
      sum = i * j
      if sum <= highest
        break
      end
      if is_palindrome(sum.to_s)
        highest = [highest, sum].max
      end
    end
  end
  highest
end
 
def is_palindrome str
  return str == str.reverse
end
 
puts get_highest_palindrome 999, 100

In this particular (and probably only) case I liked my solution better than Olathe's. I found that by counting down from 999 and breaking after any number less than my current max, I was able to save a lot of iterations.

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

However, just before I smugged off to bed I saw a post by Begoner in Python. His explanation:

The palindrome can be written as:

abccba

Which then simpifies to:

100000a + 10000b + 1000c + 100c + 10b + a

And then:

100001a + 10010b + 1100c

Factoring out 11, you get:

11(9091a + 910b + 100c)

So the palindrome must be divisible by 11. Seeing as 11 is prime, at least one of the numbers must be divisible by 11. So brute force in Python, only with less numbers to be checked:

def c():
	max = maxI = maxJ = 0
	i = 999
	j = 990
	while (i > 100):
		j = 990
		while (j > 100):
			product = i * j
			if (product > max):
				productString = str(product)
				if (productString == productString[::-1]):
					max = product
					maxI = i
					maxJ = j
			j -= 11
		i -= 1
	return max, maxI, maxJ