nekedome / project-euler

solutions/problem31.py

"""
Project Euler Problem 31: Coin Sums
===================================

.. module:: solutions.problem31
   :synopsis: My solution to problem #31.

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

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

In England the currency is made up of pound, :raw-html:`&pound;`, and pence, p, and there are eight coins in general

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

circulation:

    :math:`1p, 2p, 5p, 10p, 20p, 50p,` :raw-html:`£1` :math:`(100p)` and :raw-html:`£2` :math:`(200p)`.

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

It is possible to make :raw-html:`£2` in the following way:

    :math:`1 \\times` :raw-html:`£1` :math:`+ 1 \\times 50p + 2 \\times 20p + 1 \\times 5p + 1 \\times 2p +`

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

    :math:`3 \\times 1p`

How many different ways can :raw-html:`£2` be made using any number of coins?

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

This solution is inspired by a `meet-in-the-middle approach <https://en.wikipedia.org/wiki/Meet-in-the-middle_attack>`_.

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

We will separate the denominations into three mutually exclusive subsets. Two subsets representing similarly sized

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

subspaces and a final subset consisting of the one pence coin. More specifically:

* :math:`\\lbrace 2p, 20p, 50p \\rbrace`
* :math:`\\lbrace 5p, 10p, 100p, 200p \\rbrace`
* :math:`\\lbrace 1p \\rbrace`

Consider the possible range of coins of a given denomination :math:`x` s.t. the sum-total doesn't exceed

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

:raw-html:`£2`.

.. math::

    0 \\le \\# \\mbox{ coins of denomination } x \\le \\left \\lfloor \\frac{200}{x} \\right \\rfloor

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

These bounds give the size of each search space associated with the denomination :math:`x`.

The size of the search space associated with each subset is the size of the cross product of the respective

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

denominations. That is:

* :math:`|| \\lbrace 1p \\rbrace || = (200+1) = 201`
* :math:`|| \\lbrace 2p, 20p, 50p \\rbrace || =`
  :math:`(100 + 1) \\times (10 + 1) \\times (4 + 1) = 101 \\times 11 \\times 5 = 5555`
* :math:`|| \\lbrace 5p, 10p, 100p, 200p \\rbrace || =`
  :math:`(40 + 1) \\times (20 + 1) \\times (2 + 1) \\times (1 + 1) = 41 \\times 21 \\times 3 \\times 2 = 5166`

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

.. note:: the one pence coin is considered separately for a very specific reason. As long as the total of all other

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

          denominations is no greater than two pounds then a solution is possible by adding the required number of one

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

          pence coins until two pounds is achieved.

Now, the algorithm is simple. Find all combinations of coins from each of the two non-trivial subsets that do not

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

exceed two pounds. Search through the cross product of these two spaces and every total combination not exceeding

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

two pounds is a valid answer. The difference can simply be padded with one pence coins until two pounds is reached.

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

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

.. literalinclude:: ../../solutions/problem31.py
   :language: python
   :lines: 72-
"""

from itertools import product
from typing import Dict, List


def partial_solutions(bounds: Dict[int, int], threshold: int) -> List[int]:
    """ Produce the set of combinations of coins that doesn't exceed `threshold` pence

    The coins that may be used are specified in `bounds` which is a dictionary mapping denominations to the upper bound

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

    in the search space for that denomination.

    :param bounds: dictionary mapping denominations to search space upper bounds
    :param threshold: the sum-total threshold
    :return: the list of totals given by combinations of coins not exceeding `threshold`
    """

    rv = []

The name rv does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for x in product(*(range(bounds[y] + 1) for y in bounds.keys())):

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        subtotal = sum([ai * bi for ai, bi in zip(x, bounds.keys())])
        if subtotal <= threshold:
            rv.append(subtotal)
    rv.sort()
    return rv


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

    target = 200  # in pence
    subset1, subset2 = [2, 20, 50], [5, 10, 100, 200]  # 1p is not included
    bounds1 = {pence: target // pence for pence in subset1}
    bounds2 = {pence: target // pence for pence in subset2}

    # Independently compute partial solutions based on each non-trivial subset
    partial_solutions1 = partial_solutions(bounds1, target)
    partial_solutions2 = partial_solutions(bounds2, target)

    # Consider the cross-product of partial solutions and identify any combination not exceeding two points

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

    answer = 0
    for ps1 in partial_solutions1:
        for ps2 in partial_solutions2:
            if ps1 + ps2 <= target:
                answer += 1  # 1p coins can increase this to target as required
            else:
                break  # ps1 + ps2 for all further ps2 will now exceed target due to sorting
    return answer


expected_answer = 73682

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