ProjectEuler/043_sub-string_divisibility.py at master · MaX-Lo/ProjectEuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
"""
idea:


"""
import time


def main():
    t = time.time()
    pandigitals = get_pandigital_numbers()
    print("time for generating pandigitals", time.time() - t)

    len_pandigitals = len(pandigitals)
    i = 0
    print("num of pandigital nums:", len_pandigitals)

    wanted_nums = []

    for num in pandigitals:
        i += 1
        if i % 10000 == 0:
            print(i/len_pandigitals)

        num_str = str(num)
        if int(num_str[1:4]) % 2 != 0:
            continue
        if int(num_str[2:5]) % 3 != 0:
            continue
        if int(num_str[3:6]) % 5 != 0:
            continue
        if int(num_str[4:7]) % 7 != 0:
            continue
        if int(num_str[5:8]) % 11 != 0:
            continue
        if int(num_str[6:9]) % 13 != 0:
            continue
        if int(num_str[7:10]) % 17 != 0:
            continue

        wanted_nums.append(num)

    print(wanted_nums)
    print(sum(int(num) for num in wanted_nums))


def get_pandigital_numbers():
    digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    # digits = ['0', '1', '2']

    pandigital_numbers = []
    for digit in digits:
        new_num = digit
        new_digits = list(digits)
        new_digits.remove(digit)
        pandigital_numbers.extend(f(new_num, new_digits))
    return pandigital_numbers


def f(num, digits: list):
    if len(digits) == 1:
        return [num+digits[0]]
    else:
        ls = []
        for digit in digits:
            new_digits = list(digits)
            new_digits.remove(digit)
            new_num = num + digit
            ls.extend(f(new_num, new_digits))
        return ls


if __name__ == '__main__':
    start_time = time.time()
    main()
    print("time:", time.time() - start_time)