Project Euler Solution 33: Digit cancelling fractions

In today's part of the Project Euler series we have Problem 33: Digit cancelling fractions, which is about unconventional cancellation in fractions.

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 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 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 can be solved pretty directly. One needs to enumerate all the fractions where the denominator is larger than the numerator to fulfil the “less than one in value” property. Then make sure that they have two digits only. Once we have these, determine the digits that are in common. It must be only one common digit, otherwise it would completely cancel the fraction. If there are two common digits, like in 23/32, we could cancel either one, but the result would not be correct. And 0 isn't an interesting common digit.

For the result we need to cancel the fraction, we can use the Euclidean algorithm to determine the greatest common denominator and cancel the fraction.

def greatest_common_denominator(a: int, b: int) -> int:
    while b != 0:
        b, a = a % b, b
    return a


def solution() -> int:
    result_numerator = 1
    result_denominator = 1
    for numerator in range(10, 100):
        for denominator in range(numerator + 1, 100):
            common_digits = set(str(numerator)) & set(str(denominator))
            if "0" in common_digits:
                common_digits.remove("0")
            if len(common_digits) == 1:
                common_digit = list(common_digits)[0]
                new_numerator = str(numerator).replace(str(common_digit), "")
                new_denominator = str(denominator).replace(str(common_digit), "")
                if not new_numerator or not new_denominator:
                    continue
                if numerator * int(new_denominator) == denominator * int(new_numerator):
                    result_numerator *= numerator
                    result_denominator *= denominator
    gcd = greatest_common_denominator(result_numerator, result_denominator)
    return result_denominator // gcd

This runs through in 3.0 ms, so it is fast enough to solve this problem.