Project Euler problem 4

Here’s the first of my responses to the Euler problems I’m working through in parallel with ex-colleague and fellow code-charmer Greg Bowie.

Each week we’ll tackle one of the problems (in isolation) and post our respective responses each Friday – workloads permitting – at around 3pm. This week Greg chose 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 x 99.

Find the largest palindrome made from the product of two 3-digit numbers

Here’s Greg’s response and rationale, while my Ruby response can be found below.

Initial thought

I began by determining the highest and lowest products achievable from two 3-digit numbers. the target palindrome will exist in this range. This gave me 10,000 at lowest (100 x 100) up to 998,0001 at highest (999 x 999).

As the highest number ended ‘..001′ the palindrome had to begin ’997…’, so I was looking for 997799.

Hunting palindromes

As we’re aiming for the highest palindrome, the while loop counts down from the highest number, decrementing itself as it goes and exiting when the palindrome’s found. With the loop in place I wrote the palindrome hunter method, which:

  • Converts the current high number to a string
  • substrings the first three characters
  • Creates a variable for a character-reversed version of the number
  • Compare the first 3 characters of the two strings – if matched the loop ends and the palindrome is returned

Here’s how it looks in Ruby:

$starthighest = 998001 # 999 * 999
$lowest = 10000 # 100 * 100
def checkPal
  rev = "" #declare string
  $starthighest.to_s.each_char do |i|
  rev.prepend(i)
  end
  if ($starthighest.to_s[1,3] == rev[1,3])  
    puts "The largest palindrome from two 3-digit numbers is #{$starthighest.to_s}"
    $starthighest = $lowest
  else  
    $starthighest = $starthighest -1
  end
end
while $starthighest > $lowest
  checkPal
end

Notes

As the palindrome will be either 5 or 6 characters long, this method of substrings and reversal allows for overlap without ever having to measure the string length.

Sometimes frowned upon, here I’ve used global variables as the highest number is used both as the loop iterator and the string for comparison. This also allowed me a cleaner, parameter-free method definition.

Now I have to go and pick next week’s problem…

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>