Passed
Push — master ( 6c9680...9c2115 )
by Bill
02:28
created

solutions.problem38   A

Complexity

Total Complexity 7

Size/Duplication

Total Lines 137
Duplicated Lines 0 %

Importance

Changes 0
Metric Value
eloc 19
dl 0
loc 137
rs 10
c 0
b 0
f 0
wmc 7

2 Functions

Rating   Name   Duplication   Size   Complexity  
A solve() 0 17 4
A concatenated_product() 0 17 3
1
"""
2
Project Euler Problem 38: Pandigital Multiples
3
==============================================
4
5
.. module:: solutions.problem38
6
   :synopsis: My solution to problem #38.
7
8
The source code for this problem can be
9
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem38.py>`_.
10
11
Problem Statement
12
#################
13
14
Take the number :math:`192` and multiply it by each of :math:`1,2,` and :math:`3`:
15
16
.. math::
17
18
    192 \\times 1 &= 192 \\\\
19
    192 \\times 2 &= 384 \\\\
20
    192 \\times 3 &= 576
21
22
By concatenating each product we get the :math:`1` to :math:`9` pandigital, :math:`192384576`. We will call
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (107/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
23
:math:`192384576` the concatenated product of :math:`192` and :math:`(1,2,3)`.
24
25
The same can be achieved by starting with :math:`9` and multiplying by :math:`1,2,3,4,` and :math:`5`, giving the
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (113/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
26
pandigital, :math:`918273645`, which is the concatenated product of :math:`9` and :math:`(1,2,3,4,5)`.
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (102/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
27
28
What is the largest :math:`1` to :math:`9` pandigital :math:`9`-digit number that can be formed as the concatenated
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (115/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
29
product of an integer with :math:`(1,2,\\dots,n)` where :math:`n \\gt 1`?
30
31
Solution Discussion
32
###################
33
34
We're given that :math:`n \\gt 1`, but can we establish an upper-bound? Yes.
35
36
Observe that if :math:`n = 10`, then the concatenated product must have at least :math:`10` digits. This cannot be
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (114/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
37
:math:`1` though :math:`9` pandigital as it contains too many digits. Therefore, :math:`n \\le 9`.
38
39
Let :math:`x` be a :math:`y`-digit number
40
41
Observe that :math:`1 \\times x` is obviously a :math:`y`-digit number but other, higher, multiples of :math:`x` are
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (116/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
42
either :math:`y` or :math:`y+1` -digit numbers.
43
44
Now, consider the properties of the concatenated products for various values of :math:`n \\in [2, 9]`.
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (102/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
45
46
:math:`n = 2 \\Rightarrow 1x || 2x` which will have digits in the range of :math:`[2y, 2y+1]`
47
48
Recall that we already have a :math:`9`-digital pandigitial number :math:`918273645`, and that we are searching for a
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (117/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
49
higher one as a result of the concatenated product operation. So, we can assume that if a larger pandigital number
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (114/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
50
exists, it too is :math:`9` digits long. We must constrain :math:`y` s.t. there are :math:`9`-digit numbers in the
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (114/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
51
search space.
52
53
:math:`\\therefore n = 2 \\Rightarrow y \\in \\lbrace 4 \\rbrace`
54
55
By similar analysis we can establish the following results for other values of :math:`n`.
56
57
:math:`n = 3 \\Rightarrow 1x || 2x || 3x` which will have digits in the range of
58
:math:`[3y, 3y+2] \\Rightarrow y \\in \\lbrace 3 \\rbrace`
59
60
:math:`n = 4 \\Rightarrow 1x || 2x || 3x || 4x` which will have digits in the range of
61
:math:`[4y, 4y+3] \\Rightarrow y \\in \\lbrace 2 \\rbrace`
62
63
:math:`n = 5 \\Rightarrow 1x || 2x || 3x || 4x || 5x` which will have digits in the range of
64
:math:`[5y, 5y+4] \\Rightarrow y \\in \\lbrace 1 \\rbrace`
65
66
:math:`n = 6 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x` which will have digits in the range of
67
:math:`[6y, 6y+5] \\Rightarrow y \\in \\lbrace 1 \\rbrace`
68
69
:math:`n = 7 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x` which will have digits in the range of
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (104/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
70
:math:`[7y, 7y+6] \\Rightarrow y \\in \\lbrace 1 \\rbrace`
71
72
:math:`n = 8 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x` which will have digits in the range of
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (110/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
73
:math:`[8y, 8y+7] \\Rightarrow y \\in \\lbrace 1 \\rbrace`
74
75
:math:`n = 9 \\Rightarrow 1x || 2x || 3x || 4x || 5x || 6x || 7x || 8x || 9x` which will have digits in the range of
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (116/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
76
:math:`[9y, 9y+8] \\Rightarrow y \\in \\lbrace 1 \\rbrace`
77
78
For any case where :math:`y \\gt 1`, we can further refine the search. Since :math:`x \\times 1` will be included in the
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (120/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
79
concatenated product, :math:`x` itself cannot contain any repeated digits. So, we can search through increasing integers
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (120/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
80
starting from :math:`1, 12, 123, 1234, \\dots` which are the smallest integers of lengths :math:`1, 2, 3, 4, \\dots`
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (116/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
81
without repeated digits.
82
83
Now, we have an algorithm. Search through :math:`n \\in [2, 9]`, and for each :math:`n`, consider :math:`a` in the range
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (120/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
84
specified above corresponding to :math:`n`. For each :math:`(a, n)`, build the concatenated product. The answer is
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (114/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
85
simply the maximal concatenated product.
86
87
Solution Implementation
88
#######################
89
90
.. literalinclude:: ../../solutions/problem38.py
91
   :language: python
92
   :lines: 95-
93
"""
94
95
from lib.digital import num_digits, is_pandigital
96
97
98
def concatenated_product(a: int, n: int) -> int:
0 ignored issues
show
Coding Style Naming introduced by
The name a does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
Coding Style Naming introduced by
The name n does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
99
    """ Build the concatenated product :math:`a` and :math:`(1, 2, \\dots, n)`
100
101
    The concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)` is defined as
102
    :math:`(1 \\times a) || (2 \\times a) || \\dots || (n \\times a)`
103
104
    :param a: the base integer
105
    :param n: the number of products in the concatenated product
106
    :return: the concatenated product of :math:`a` and :math:`(1, 2, \\dots, n)`
107
    """
108
109
    vals = [i * a for i in range(1, n + 1)]
110
    z = 0
0 ignored issues
show
Coding Style Naming introduced by
The name z does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
111
    for val in vals:
112
        z = z * (10 ** num_digits(val)) + val
0 ignored issues
show
Coding Style Naming introduced by
The name z does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
113
114
    return z
115
116
117
def solve():
118
    """ Compute the answer to Project Euler's problem #38 """
119
120
    answer = 918273645  # we are searching for a greater answer, this will do as a starting value to maximise
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (109/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
121
122
    # The range of the search space on a for each possible value of n
123
    bounds = {2: (1234, 10 ** 4), 3: (123, 10 ** 3), 4: (12, 10 ** 2), 5: (1, 10 ** 1), 6: (1, 10 ** 1),
0 ignored issues
show
Coding Style introduced by
This line is too long as per the coding-style (104/100).

This check looks for lines that are too long. You can specify the maximum line length.

Loading history...
124
              7: (1, 10 ** 1), 8: (1, 10 ** 1), 9: (1, 10 ** 1)}
125
126
    # Perform the search
127
    for n in range(2, 10):
0 ignored issues
show
Coding Style Naming introduced by
The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
128
        for a in range(*bounds[n]):
0 ignored issues
show
Coding Style Naming introduced by
The name a does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
129
            concat_prod = concatenated_product(a, n)
130
            if is_pandigital(concat_prod, 9):
131
                answer = max(answer, concat_prod)
132
133
    return answer
134
135
136
expected_answer = 932718654
0 ignored issues
show
Coding Style Naming introduced by
The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).

This check looks for invalid names for a range of different identifiers.

You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements.

If your project includes a Pylint configuration file, the settings contained in that file take precedence.

To find out more about Pylint, please refer to their site.

Loading history...
137