Friday, August 17, 2012

Problem 4 - Palindromes

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.


#!/usr/bin/env python

def ispal(num):  #Check if the number is a palindrome
    val = str(num)  #Python just does the right thing here.  Nice.
    for each in range(0,int((len(val)+1)/2)): #Any mismatch return false
        if val[len(val)-1-each]!=val[0+each]: return False
    return True  #otherwise return true

def calc():  #brute force looking for palindromes
    temp = 0
    largest = 0
    for each in range(999,100,-1):
        for other in range(999,100,-1):
            temp = each * other
            if ispal(temp):
                largest = max(largest,temp)
    return largest

if __name__ == '__main__' :
    print (calc())

The answer is 906609.


This was one of the problems which took almost no time to code.  The seamless casting in Python made this one trivial.  You just work from both ends and look for mismatches.

Converting to a string worked exactly like it should have and python made it trivial to code.  Using some sort of built-in to reverse the string and see if it matches the original sting would probably be faster than a char by char comparison.


The benchmarks fell out pretty much like the others.  Boring example, Sorry!

Problem #4 Benchmarks
time python

real 0m0.746s
user 0m0.744s
sys 0m0.000s
time python -O

real 0m0.764s
user 0m0.756s
sys 0m0.004s
time python3

real 0m0.839s
user 0m0.828s
sys 0m0.008s
time python3 -O

real 0m0.875s
user 0m0.868s
sys 0m0.004s
time pypy

real 0m0.090s
user 0m0.080s
sys 0m0.008s
time pypy -O

real 0m0.087s
user 0m0.072s
sys 0m0.012s
time jython

real 0m2.835s
user 0m5.852s
sys 0m0.176s


Python just worked here.  This problem took no time at all to code and worked on the first try.  The benchmarks agree with everything else we've seen.  The answer is 906609.