How to make Project Euler 32 in Python faster?

Question

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

I need help on making this code faster. Right now I'm using double nested for-loops; is there a way I can change that?

from timeit import default_timer as timer

start = timer()
products = set()
for a in range(12, 100):
    for b in range(102, 1000): # to get 9-digit: 2-digit * 3-digit
        product = a * b
        digits = list(str(a) + str(b) + str(product))
        digits = [int(x) for x in digits]
        if sorted(digits, key = int) == range(1, 10):
            products.add(product)

for a in range(1, 10):
    for b in range(1023, 10000): # other option is 1-digit * 4-digit
        product = a * b
        digits = list(str(a) + str(b) + str(product))
        digits = [int(x) for x in digits]
        if sorted(digits, key = int) == range(1, 10):
            products.add(product)

ans = sum(list(products))
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

Since you know that all of the non-zero digits must be present in the answer, you can skip most of the numbers in the range. That is, it's pointless to do a test multiplication of 22*3333 because those both repeat digits.

So what is needed is an efficient way to run through all of the permutations of digits quickly, and fortunately, Python's itertools provides exactly that.

import itertools
start = timer()
products = set()
def makeint(n):
    return int(''.join(map(str,n)))

target = range(1,10)
d = itertools.permutations(target, 5)
for a in d:
    product = makeint(a[:2])*makeint(a[2:])
    if sorted(list(a)+map(int,str(product))) == target:
        products.add(product)
    product = makeint(a[:1])*makeint(a[1:])
    if sorted(list(a)+map(int,str(product))) == target:
        products.add(product)

ans = sum(list(products))

The way this works is to pick off permutations 5 digits at a time and then group as 2 and 3 or as 1, 4 as you have done. There are other refinements one can make, such as skipping every number which ends in a 5 (because 5*n will always end in either 0, which is not in the range, or 5 which would be a duplicate digit), but I'll leave such refinements to you.

As it stands, this code runs almost 8x faster than the original.

Answer 2

As far as I know Project Euler problems, a brute force approach just doesn't work. So, we shouldn't code code, but rather an algorithm review.

An immediate thing coming to mind is that you test too many knowingly impossible combinations of a and b. They together must be composed of different digits, which you may test prior to multiplication.

My suggestion would be to create an iterator supplying numbers composed by different digits (from a given set - for b the digit set doesn't include digits used in a), and test the product being composed by what's left.

That may give you a significant speedup. May be, more math insight is required.

PS: once digits for a are selected, you may limit the range in which a product may fall, which in turn limits the possible range for b.