Project Euler Problem 33 - digit canceling fractions

Question

Problem:

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

We shall consider fractions like, \$(\dfrac{30}{50}) = (\dfrac{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 is some rough code -- this one was a lot harder than I expected it to be. Please help me optimize.

from timeit import default_timer as timer

start = timer()
fractions_that_work = []

def a_common_element(list_a, list_b):
    count = 0
    common = 0
    for m in list_a:
        for n in list_b:
            if m == n:
                count += 1
                common = m
    if count == 1:
        return common
    return False

for numerator in range(10, 100):
    for denominator in range(numerator + 1, 100): # denom must be > num
        n_digits = sorted([int(x) for x in str(numerator)])
        d_digits = sorted([int(x) for x in str(denominator)])
        common = a_common_element(n_digits, d_digits)
        if common:
            n_digits.remove(common)
            d_digits.remove(common)
            n_rem = n_digits[0]
            d_rem = d_digits[0]
            if 0 not in n_digits and 0 not in d_digits:
                if float(numerator) / denominator == float(n_rem) / d_rem:
                    fractions_that_work.append([numerator, denominator])        
product_of_fractions = [1, 1]
for frac in fractions_that_work:
    product_of_fractions[0] *= frac[0]
    product_of_fractions[1] *= frac[1]

start = timer()
ans = product_of_fractions[1] / product_of_fractions[0]
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

Firstly, you set start at the top of the script (which is OK). However, you reset start right before your final calulation:

# This will only time the execution of one statement!
start = timer()
ans = product_of_fractions[1] / product_of_fractions[0]
elapsed_time = (timer() - start) * 1000 # s --> ms

Remove the above start = timer() to get a more accurate timing. Also, I would recommend moving the first start declaration to just before the nested for loops. That was the start time is more spatially related to what you are actually timing.

---

Secondly, your a_common_element function's name is a little misleading. Currently, it insinuates it will return positively if the two lists have any number of common elements. Changing the function name to something like has_single_common_element gives a better description of what the function actually does.

Also, a_common_element can be simplified a tad. By using list comprehension we can combine the nested for loops into one comprehension:

def a_common_element(list_a, list_b):
    common_list = [value for value in list_a if value in list_b]

    if len(common_list) == 1:
        return common_list[0]
    return False

---

Your next section is actually quite interesting: you used a neat way to separate the digits. However, the downfall (I believe) to your method is the back-and-forth casting that it requires. I would, instead, recommend doing to calculations to get your digits:

for numerator in range(10, 100):
    for denomerator in range(numerator+1, 100):
        # Division will strip off the first digit
        # Modulus will strip off the 0th digit
        n_digits = sorted([int(numerator/10), numerator % 10])           
        d_digits = sorted([int(denomerator/10), denomerator % 10])

NOTE: This recommendation is based on the project description you provided, that is all numbers will have exactly 2 digits. If you wanted to extend this to greater sets of numbers (3-digits, 4-digits, etc) I would keep your current implementation.

---

This next recommendation, like the previous, is based off of 2-digit numbers only.

Once you remove the common digit from the lists, you assign the remaining digits to variables; which is good. However, you then go check if the lists contain 0 instead of comparing the variables:

# I imagine this is what Python does in the backgroud when you say:
#    if 0 not in list
if n_rem != 0 and d_rem != 0:

---

Your next section is nice. Its simple and intuitive. If you wanted to make the code more Pythonic, you could instead do it this way:

product_of_fractions = [1, 1]
for frac in fractions_that_work:
    product_of_fractions = [i*j for i, j in zip(product_of_fractions, frac)]

If you wanted to go a bit more towards functional programming you could use this single line of code:

from functools import reduce   # Needed for Python 3, works in Python 2.6+
import operator

product_of_fractions = [reduce(operator.mul, value) for value in zip(*fractions_that_work)]

Even though it may be more complex (and thus slightly less readable), I prefer this last way because of its brevity.