Project Euler # 43 Sub-string divisibility in Python

Question

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let \$d_1\$ be the 1st digit, \$d_2\$ be the 2nd digit, and so on. In this way, we note the following:

\$d_2d_3d_4=406\$ is divisible by 2

\$d_3d_4d_5=063\$ is divisible by 3

\$d_4d_5d_6=635\$ is divisible by 5

\$d_5d_6d_7=357\$ is divisible by 7

\$d_6d_7d_8=572\$ is divisible by 11

\$d_7d_8d_9=728\$ is divisible by 13

\$d_8d_9d_{10}=289\$ is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Awaiting feedback.

from itertools import permutations
from time import time


def check_divisibility(number):
    """returns True if pandigital number obeys to the divisibility rules."""
    primes = [2, 3, 5, 7, 11, 13, 17]
    to_str = str(number)
    for index in range(1, 8):
        partition = to_str[index: index + 3]
        if int(partition) % primes[index - 1]:
            return False
    return True


def check_zero_nine_pandigits():
    """generates all 10 pandigital numbers that obey the divisibility rules."""
    return (int(''.join(perm)) for perm in permutations('1406357289') if perm[0] != '0' and
            check_divisibility(int(''.join(perm))))


if __name__ == '__main__':
    start_time = time()
    print(sum(check_zero_nine_pandigits()))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

There are probably more subtle ways to solve this problem like using a constructive solution starting from the end. Anyway, let's try to improve your bruteforce implementation.

Already defined values

permutations('1406357289') could be written permutations(string.digits)

Conversions in all directions

From a permutation (iterable), you build a string (with join) then an int which is then converted to a string (in check_divisibility) to get the chunks of 3 digits which are converted to int.

Also, some of these operations are performed twice...

From a permutation perm, you can directly compute the value of the chunk at index i with int(''.join(p[i:i + 3])) (which involves many conversions but it is hard to do less).

Avoid range(1, 8)

The hardcoded range can be hard to understand and easy to get wrong when other parts of the code get updated because of the magic numbers.

In general, it is best to avoid using range when what you want is to iterate over an iterable - see also Ned Batchelder's excellent talk: "Loop like a native".

Here, you could write something like (not tested):

def check_divisibility(number):
    """returns True if pandigital number obeys to the divisibility rules."""
    divisors = [2, 3, 5, 7, 11, 13, 17]
    to_str = str(number)
    for idx, div in enumerate(divisors):
        if int(to_str[idx + 1: idx + 3 + 1]) % div:
            return False
    return True

Builtins

This looks like the typical situation where you can use the builtins all/any.

def check_divisibility(number):
    """returns True if pandigital number obeys to the divisibility rules."""
    divisors = [2, 3, 5, 7, 11, 13, 17]
    to_str = str(number)
    return all(int(to_str[idx + 1: idx + 3 + 1]) % div == 0
               for idx, div in enumerate(divisors))

Now that we remember that we could provide number as a string directly to the function, we'd have something like:

def check_divisibility(number):
    """returns True if pandigital number obeys to the divisibility rules."""
    divisors = [2, 3, 5, 7, 11, 13, 17]
    return all(int(number[idx + 1: idx + 3 + 1]) % div == 0
               for idx, div in enumerate(divisors))


def check_zero_nine_pandigits():
    """generates all 10 pandigital numbers that obey the divisibility rules."""
    return (int(''.join(perm)) for perm in permutations(string.digits) if perm[0] != '0' and check_divisibility(''.join(perm)))

And then, we could ask ourselves if we really need that extra function:

def check_zero_nine_pandigits():
    """generates all 10 pandigital numbers that obey the divisibility rules."""
    divisors = [2, 3, 5, 7, 11, 13, 17]
    return (int(''.join(perm)) for perm in permutations(string.digits)
            if perm[0] != '0' and
            all(int(''.join(perm)[idx + 1: idx + 3 + 1]) % div == 0 for idx, div in enumerate(divisors)))

Small optimisation

The divisibility criteria with 17 is more restrictive than the one with 2. We could start with that one. For instance:

def check_zero_nine_pandigits():
    """generates all 10 pandigital numbers that obey the divisibility rules."""
    divisors = [(17, 7), (13, 6), (11, 5), (7, 4), (5, 3), (3, 2), (2, 1)]
    return (int(''.join(perm)) for perm in permutations(string.digits)
            if perm[0] != '0' and
            all(int(''.join(perm)[idx: idx + 3]) % div == 0 for div, idx in divisors))

Joining less elements

''.join(perm)[idx: idx + 3] can be written ''.join(perm[idx: idx + 3])

Final code:

def check_zero_nine_pandigits():
    """generates all 10 pandigital numbers that obey the divisibility rules."""
    divisors = [(17, 7), (13, 6), (11, 5), (7, 4), (5, 3), (3, 2), (2, 1)]
    return (int(''.join(perm)) for perm in permutations(string.digits)
            if perm[0] != '0' and
            all(int(''.join(perm[idx: idx + 3])) % div == 0 for div, idx in divisors))

Answer 2

Obviously, there are a billion possible permutations to check. To be able to find the number in a reasonable time, you need to prune off parts of the search space that can't possibly include the answer.

For example, given the property d₄d₅d₆ is divisible by 5, we know that d₆ can only be 0 or 5. Similarly, we know that d₄ must be an even digit, and d₁ can't be 0. Using that information, you can reduce the search space to "only" 90 million permutations (still a lot).

Alternatively, you could try to construct a number by starting with a 3-digit number that satisfies one of the criteria. And then try adding digits in such a way that with each new digit, the number satisfies another criteria.