nekedome / project-euler

solutions/problem32.py

"""

A suspicious escape sequence \l was found. Did you maybe forget to add an r prefix?

Project Euler Problem 32: Pandigital Products
=============================================

.. module:: solutions.problem32
   :synopsis: My solution to problem #32.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem32.py>`_.

Problem Statement
#################

We shall say that an :math:`n`-digit number is pandigital if it makes use of all the digits :math:`1` to :math:`n`

This line is too long as per the coding-style (114/100).

exactly once; for example, the :math:`5`-digit number, :math:`15234`, is :math:`1` through :math:`5` pandigital.

This line is too long as per the coding-style (112/100).

The product :math:`7254` is unusual, as the identity, :math:`39 \\times 186 = 7254`, containing multiplicand,

This line is too long as per the coding-style (109/100).

multiplier, and product is :math:`1` through :math:`9` pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a :math:`1` through

This line is too long as per the coding-style (113/100).

:math:`9` pandigital.

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

This line is too long as per the coding-style (108/100).

Solution Discussion
###################

The single example given demonstrates that we need not consider prime factorisations but rather the product of two

This line is too long as per the coding-style (114/100).

positive integers; :math:`a \\times b = c`.

The tuple :math:`(a,b,c)` is defined as :math:`d`-pandigital if the digits :math:`1` through :math:`d` appear precisely

This line is too long as per the coding-style (119/100).

once in the digits comprising the three integers :math:`a,b,c` when represented in decimal. A pruned search will suffice

This line is too long as per the coding-style (120/100).

to find all such :math:`d`-pandigital integers.

First, observe that :math:`c` is completely determined by :math:`a` and :math:`b`, we need only consider :math:`a` and

This line is too long as per the coding-style (118/100).

:math:`b`. A naive search over all :math:`d`-digit integers :math:`a` and :math:`b` involves a search space of size

This line is too long as per the coding-style (115/100).

:math:`10^{2 \\times d}`. However, this can be reduced by utilising some additional constraints imposed by the problem.

This line is too long as per the coding-style (119/100).

Since we are searching for :math:`1` through :math:`9` pandigital numbers, we know there are no :math:`0` digits. Thus,

This line is too long as per the coding-style (119/100).

:math:`a` and :math:`b` are positive integers without leading zeroes and the number of digits in their product is

This line is too long as per the coding-style (113/100).

restricted according to:

.. math::

    &\\mbox{Let } c = a \\times b \\\\
    &\\mbox{Let } |x| \\mbox{ be the number of decimal digits in } x \\\\
    &|a| + |b| - 1 \\le |c| \le |a| + |b|

For :math:`(a,b,c)` to be :math:`d`-pandigital, the total number of digits in all integers must equal :math:`d`:

This line is too long as per the coding-style (112/100).

.. math::

    |a| + |b| + |c| = d

Combining these two facts sets up useful constraints on :math:`b`, given :math:`a` and :math:`d`:

.. math::

    &|a| + |b| - 1 \\le |c| \\le |a| + |b| \\\\
    \\Rightarrow &|a| + |b| + |a| + |b| - 1 \\le |a| + |b| + |c| \\le |a| + |b| + |a| + |b| \\\\
    \\Rightarrow &2|a| + 2|b| - 1 \\le d \\le 2|a| + 2|b| \\\\
    \\Rightarrow &2|b| - 1 \\le d - 2|a| \\le 2|b| \\\\
    \\Rightarrow &d - 2|a| \\le 2|b| \\mbox{ and } 2|b| - 1 \\le d - 2|a| \\\\
    \\Rightarrow &\\frac{d}{2} - |a| \\le |b| \\mbox{ and } |b| \\le \\frac{d + 1}{2} - |a| \\\\
    \\Rightarrow &\\frac{d}{2} - |a| \\le |b| \\le \\frac{d + 1}{2} - |a|

Finally, the search over possible integers :math:`a` is bound by two overall constraints. Firstly, that :math:`(a,b,c)`

This line is too long as per the coding-style (119/100).

must consist of exactly :math:`d` digits and that each integer must be at least one digit. Secondly, that the number of

This line is too long as per the coding-style (119/100).

digits in :math:`c` will be at least equal to the number of digits in :math:`a`.

.. math::

    c = a \\times b \\Rightarrow |c| \\ge |a| \\mbox{ (for positive integers } a,b,c)

This leads to an upper-bound on the number of digits in :math:`a`:

.. math::

    &d = |a| + |b| + |c| \\ge |a| + |b| + |a| = 2|a| + |b| \\\\
    \\Rightarrow &d \\ge 2|a| + |b| \\\\
    &\\mbox{Since } |b| \\ge 1, 2|a| + |b| \\ge 2|a| + 1 \\\\
    \\Rightarrow &d \\ge 2|a| + 1 \\\\
    \\Rightarrow &\\frac{d - 1}{2} \\ge |a| \\\\
    \\Rightarrow &1 \\le |a| \\le \\frac{d - 1}{2} \\mbox{ (since all } a,b,c \\mbox{ must be at least one digit)}

This line is too long as per the coding-style (114/100).

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem32.py
   :language: python
   :lines: 94-
"""

from lib.digital import is_pandigital, num_digits


def solve():
    """ Compute the answer to Project Euler's problem #32 """

    # Problem specific parameters
    base = 10  # use decimal representation
    target = 9  # searching for target-pandigital numbers
    a_max = base ** ((target - 1) // 2)  # upper-bound on a

    # Perform search over a and b looking for target-pandigital numbers
    pandigitals = set()
    for multiplicand in range(1, a_max):  # search over values of a
        a_len = num_digits(multiplicand)
        b_lower_digits = (target + 1) // 2 - 1  # minimum number of digits in b
        b_upper_digits = target // 2 + 1  # maximum number of digits in b
        b_lower = base ** (b_lower_digits - a_len)  # minimum value of b (half-open interval)
        b_upper = base ** (b_upper_digits - a_len)  # maximum value of b (half-open interval)

        for multiplier in range(b_lower, b_upper):  # search over values of b
            product = multiplicand * multiplier  # compute c = a * b

            if is_pandigital([multiplicand, multiplier, product], target, 1, base):
                pandigitals.add(product)  # save any unique target-pandigital numbers 'product'

    # Sum all unique target-pandigital integers
    answer = sum(pandigitals)
    return answer


expected_answer = 45228

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).