Created
October 20, 2014 17:44
-
-
Save evertheylen/7307d6b8d7965dda83d5 to your computer and use it in GitHub Desktop.
Inleiding programmeren, palindromen
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment