nekedome / project-euler

solutions/problem33.py

"""
Project Euler Problem 33: Digit Cancelling Fractions
====================================================

.. module:: solutions.problem33
   :synopsis: My solution to problem #33.

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

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

The fraction :math:`\\frac{49}{98}` is a curious fraction, as an inexperienced mathematician in attempting to simplify

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

it may incorrectly believe that :math:`\\frac{49}{98} = \\frac{4}{8}`, which is correct, is obtained by cancelling the

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

:math:`9\\mbox{s}`.

We shall consider fractions like, :math:`\\frac{30}{50} = \\frac{3}{5}`, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits

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

in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

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

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

Nothing special here, just implement the faulty cancelling logic and see when it just so happens to agree with the

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

correct arithmetic results. Accumulate these so-called curious fractions.

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

.. literalinclude:: ../../solutions/problem33.py
   :language: python
   :lines: 39-
"""

from fractions import Fraction
from typing import Tuple

from lib.digital import digits_of, digits_to_num


def simplify_bad(a: int, b: int) -> Tuple[int, int]:

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

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

    """ Simplify the fraction :math:`\\frac{a}{b}` using the incorrect logic specified for this problem

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

    In particular, individual decimal digits are directly cancelled with each other rather than considering common

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

    divisors of :math:`a` and :math:`b`.

    :param a: fraction numerator
    :param b: fraction denominator
    :return: the simplified fraction :math:`\\frac{a}{b}` using the incorrect logic

    >>> simplify_bad(49, 98)
    (4, 8)
    """

    # Get the decimal digits of the numerator and denominator
    a_digits = digits_of(a, base=10)
    b_digits = digits_of(b, base=10)

    # Build copies of the digits and start cancel them out if possible
    aa = a_digits.copy()

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

    bb = b_digits.copy()

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

    for a_i in a_digits:
        if a_i in bb and a_i != 0:
            aa.remove(a_i)
            bb.remove(a_i)

    return digits_to_num(aa), digits_to_num(bb)  # convert the remaining digits back to integers


def is_curious_fraction(x: int, y: int, x_bad: int, y_bad: int) -> bool:

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

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

    """ Test to see if :math:`\\frac{x}{y}` is a "curious fraction"

    :param x: the numerator of the fraction
    :param y: the denominator of the fraction
    :param x_bad: the numerator of the (incorrectly) cancelled fraction
    :param y_bad: the denominator of the (incorrectly) cancelled fraction
    :return: whether :math:`\\frac{x}{y}` is a "curious fraction" or not
    """

    if x_bad == x:

Unnecessary "else" after "return"

        return False  # no cancellation occurred, cannot be "curious"
    elif y_bad == 0:
        return False  # cancellation resulted in invalid fraction
    else:
        return x_bad / y_bad == x / y


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

    n_digits = 2  # number of digits in each numerator/denominator
    curious_product = Fraction(1, 1)  # will accumulate the product of curious fractions

    for numerator in range(10 ** (n_digits - 1), 10 ** n_digits):
        for denominator in range(numerator + 1, 10 ** n_digits):
            numerator_cancelled, denominator_cancelled = simplify_bad(numerator, denominator)
            if is_curious_fraction(numerator, denominator, numerator_cancelled, denominator_cancelled):

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

                curious_product *= Fraction(numerator_cancelled, denominator_cancelled)

    answer = curious_product.denominator  # extract the denominator from the simplified fraction
    return answer


expected_answer = 100

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