Inleiding programmeren, palindromen

palindrome.py

# Author: Evert Heylen
# Date: 09.10.2014

# call the program with 'color' as an argument to have red input like in
# the Assignment file!

# call the program with 'exp' to use the experimental faster function

# The previous assignment had example output in Dutch, this one has the example output in English, so
# I've edited my helper fucntions accordingly.

import sys
import math

usecolor = False

# ANSI color codes. Thanks wikipedia.
red = '\033[31m'
endc = '\033[0m'  # Resets all ANSI attributes


def ip_input(question, req_format):
    """ Will ask again for as long as the answer isn't in the required format.
    req_format will be of type 'type', which means it is a type on itself.
    As such, we can call it as a function to do the conversion, and it will
    raise an error if the conversion failed. 
    """

    a = 0
    while True:
        try:
            print(question, end='')

            if usecolor:
                a = req_format(input(red))
                print(endc, end='')
            else:
                a = req_format(input())
            break
        except ValueError:
            print(endc + 'Wrong type! Try again.')
    return a


def find_largest_palindrome(n):
    """ Finds the largest palindrome consisting of two numbers x and y, both
    consisting of n numbers (in decimal format).
    n = number of numbers
    """
    if n < 1:
        print('n should be at least 1')
        return

    maxsingle = 10 ** n - 1  # example for n=3: 999
    minsingle = 10 ** (n - 1)  # 100

    largestpalindrome = 0
    largestx = 0
    largesty = 0

    for x in range(maxsingle, minsingle, -1):
        for y in range(x, minsingle, -1):
            p = x * y
            if is_palindrome(p) and p > largestpalindrome:
                largestpalindrome = p
                largestx = x
                largesty = y

    return largestpalindrome, largestx, largesty

# end func find_largest_palindrome


def exp_find_largest_palindrome(n):
    """ Experimental method
    Finds the largest palindrome consisting of two numbers x and y, both
    consisting of n numbers (in decimal format).
    n = number of numbers
    """
    if n < 1:
        print('n should be at least 1')
        return

    # The algorithm I use will try all possible combinations, but it will do
    # it in a  specific order so that it will (most of the time) find the
    # biggest palindrome first. It has been tested to work at least up to n=11
    # (9999994020000204999999 = 99999996349 * 99999943851)
    # It seems to be way faster than the other algorithm above, taking only
    # 30.49s (on my machine, i7 3770K) to find all the palingdromes fitting
    # the requirements from n=1 to n=8.
    # The 'normal' version takes 32.10s to do the same from n=1 to n=4.

    maxsingle = 10 ** n - 1  # example for n=3: 999
    maxtotal = 2 * maxsingle  # 1998

    minsingle = 10 ** (n - 1)  # 100
    mintotal = 2 * minsingle  # 200

    total = maxtotal

    while total >= mintotal:
        xstart = math.ceil(total / 2)

        for x in range(xstart, maxsingle + 1):
            y = total - x
            if y < minsingle:
                break

            p = x * y
            if is_palindrome(p):
                return p, x, y

            previousp = p
        total -= 1

    # end while loop

# end func exp_find_largest_palindrome


def is_palindrome(x):
    strx = str(x)
    return strx == strx[::-1]
    # a lot faster than reversed()


def main():
    if 'color' in sys.argv:
        # Sets the global variable usecolor to True
        global usecolor
        usecolor = True

    n = ip_input('How many digits in each factor?', int)

    if 'exp' in sys.argv:
        print("You're using the experimental version.")
        l, x, y = exp_find_largest_palindrome(n)
    else:
        l, x, y = find_largest_palindrome(n)

    print('Largest palindrome found! {0} x {1} = {2}'.format(x, y, l))


def main2():
    for i in range(1, 5):
        print('n=', i, end=' -->')
        find_largest_palindrome(i)

main()