bitvector wrote:I did this one a while ago when I was working some of the Euler problems. Rather than loop over all pairs of multiples as you did (which grows rather fast), I basically generated all palindromic numbers of the right length in descending order and factored them, stopping with the first match. In Python, the six digit case takes about 90 seconds.
Okay, so to walk through the code -- as I say here, I generate palindromes in decreasing order and then factor them, stopping with the first that fits the criteria (that has a pair of factors with n digits).
Here, I define find_pal_pairs as the outer function and it takes in the desired number of digits in the factors (e.g. if n=3 you want two 3 digit numbers that multiply to a 6 digit palindrome). Next, I just define a small function that tests whether a number has the correct number of digits. You could do this many ways, including converting to a string and testing the length, but I just do it by seeing if the number is <= 10 taken to the (n-1)th power and < 10 to the nth power.
def find_pal_pairs(n):
ql, qh = 10**(n-1), 10**n
def ndigits(t):
return t >= ql and t < qh
Next I generate all of the palindromic numbers of length 2*n in descending order as a list and loop over that list in order. In the body of the loop, s is current number (as a string).
for s in genpalinrev(2*n):
In the body of the loop, I convert the current palindrome number to a number (int(s)) and then call getfacpairs on that number. That helper function returns pairs of factors of the number stopping at about the square root of the number (since above that point you'll get duplicate entries which are just (y, x) where (x, y) is already in the list). So if you passed it 15, it should return a list with [(1, 15), (3, 5)]. Now here's a part that might seem weird -- the list that getfacpairs returns is passed to filter. Filter takes a function which is used to filter out entries in the list. Basically you give filter a list and you give it a function and it calls the function for every element in the list. When it's done, it returns a list that contains only the elements where the function returned "true." So, if you passed filter a list of words and a function that tested if a string started with a capital letter, you'd get back a list of only the capitalized words. In this case, the function passed to filter tests whether the first and second elements of the pair (e.g. both x and y in (x, y)) have the right number of digits (remember, that's all the ndigits function does).
fp = filter(lambda t: ndigits(t[0]) and ndigits(t[1]),
getfacpairs(int(s)))
Now, after we call filter, what are we left with? Well we are left with a list of factor pairs (x, y) of the current palindrome where both x and y are the right number of digits. So if the list is non-empty, if it contains any pairs, that means we have found a match: x*y multiply to a palindrome. So in Python "if x" is used to test if a list or collection is non-empty. If the list is non-empty, we've found our result and we print it and stop the loop. Most of the time, when filter is done, the list will be empty because none of the pairs meet the criteria.
So now all we have left is the helper functions.
First, the function to generate palandromic numbers of a certain length recursively and in descending order. I did this by simple recursive decomposition: if we need to generate all palindromes of length 0 or 1, it is trivial, and those are our base cases. The list of palindromes with zero digits just contains the empty string. The list of palindromes with one digit is easy too -- just the numbers 0-9 in descending order. The xrange thing says generate all numbers in the range [9, -1) (non-inclusive with -1 and decrement by 1). A more intuitive way of writing this is "reversed(xrange(0, 10))" (e.g. the range [0, 10) reversed).
def genpalinrev(n):
if n == 0:
return ['']
elif n == 1:
return [str(d) for d in xrange(9, -1, -1)]
Now the recursive case: if we need to generate palindromes of length N, we can do it by generating all palindromes of length N-2 and then appending two matching characters on each end. So if we have the list ['99', '88', ...] we can make a list of palindromes of length 4 by simply adding matching pairs of digits to each one: ['9999', '9889', ... '8998', ...]. So we loop over all digits 9 to 0 for
each entry in the list of palindromes of N-2. So we append 9 to each end of '99', '88', all the way to '00' and then append 8 to each end of '99', '88', etc. gathering the list of all of them.
else:
l = genpalinrev(n-2)
return [str(d) + o + str(d) for d in xrange(9, -1, -1) for o in l]
Finally, this is the helper function to generate pairs of factors of our number "num". We just loop over all numbers 1 to about the ceiling of the square root of num. For each number i in our loop, we test "if not num % i", which means that i divides into num evenly (the remainder is 0). If the test is true, the pair (i, num / i) is added to the list. So this gives us all of the pairs of factors of num.
from math import sqrt, ceil
def getfacpairs(num):
return [(i, num / i) for i in xrange(1, int(ceil(sqrt(num)+1))) if not num % i]
just brew it! wrote:bitvector wrote:The one potentially "tricky" part for people only familiar with mainstream procedural and OO languages is the use of list comprehensions.
Well... that, and the explicit use of indentation for control flow. But that one's pretty easy to get used to, since it merely forces the programmer to indent the code the way it should've been in the first place.
Just writing up the explanation of this, I realized there are some other less than obvious Pythonic things here -- decreasing xrange, the use of "if x" to test for empty collections (or "if not x" to test if something is 0), as well as filter and lambda functions (more FP than Python, but still...). It's quite dense, and if you're only used to
Blub languages, it could be confounding.