"""
 palindrome.py

 In class exercise looking at Project Euler problem 4
 i.e. https://projecteuler.net/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.

 Jim Mahoney | March 2018
"""

def string_reverse(a_string):
    """ Returned string reversed 
        >>> string_reverse('cat')
        'tac'
    """
    # from https://www.geeksforgeeks.org/reverse-string-python-5-different-ways/
    result = ""
    for letter in a_string:
        result = letter + result
    return result

def is_palindrome(i):
    """ return True if the number i is a palindrome 
        >>> is_palindrome(12)
        False
        >>> is_palindrome(9009)
        True
    """
    as_string = str(i)
    return as_string == string_reverse(as_string)

def search(n):
    """ return pair pair of n-digit numbers with biggest product 
        >>> search(2)
        (91, 99)
    """
    # (a,b) will be the numbers
    # For n=2, loop a from 10 (smallest) to 99 (biggest) inclusive.
    # second number can loop from a+1 to 99, 
    # since we can have the smaller number be a.
    (best_product, best_b, best_a) = (0, 0, 0)
    smallest = 10**(n-1)
    biggest = 10**n - 1
    #print "n is ", n
    #print " smallest ", smallest
    #print " biggest ", biggest
    for a in range(smallest, biggest+1):
        for b in range(a+1, biggest+1):
            #print a, b
            product = a * b
            if is_palindrome(product) and product > best_product:
                (best_product, best_b, best_a) = (product, b, a)
    return (best_a, best_b)

def main():
    n = 3
    (a, b) = search(n)
    print "biggest {}-digit palindrome: {} * {} = {}".format(n, a, b, a*b)

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()