Project Euler 33

Problem 33 of project euler is a problem that concerns it's self with odd ways of canceling fractions. The example they give is 49/98. If you 'cancel' the 9s you will still get the same number: 4/8 = 49/98. So basically we want to see, first if there is a digit that appears in both the numerator and the denominator. I decided to do this in python like so:

#a, the numerator, b the denominator.
def curious(a,b):
    try:
        c = float(a)/b
        if a/10 == b/10: #(4)9 & (9)8
            if float(a%10)/(b%10) == c:
                return 1
        if a/10 == b%10: #(4)9 & 9(8)
            if float(a%10)/(b/10) == c:
                return 1
        if a%10 == b/10: #4(9) & (9)8
            if float(a/10)/(b%10) == c:
                return 1
        if a%10 == b%10: #4(9) & 9(8)
            if float(a/10)/(b/10) == c:
                return 1
    except: #handles cases where b%10 results in 0
        return 0
    return 0

So hopefully either you know the modular arithmetic or it is clear from context, but basically taking any number %10 will knock off everything but the single digit (11%10 -> 1, 72%10 -> 2, 89%10 -> 9, etc). The second potentially confusing part of the 'curious' function is integer division. Basically this is division where you simply never keep track of anything below a whole number (21/10 -> 2, 53/10 -> 5, etc). This way given any pair of two digits numbers I try every combination where they could have two of the same digits. Then I check to see if the other two digits, the ones that would be remaining if the co-occurring digits were removed equal the original fraction. For example I take in 49 and 98 The third if statement would be triggered and 4/8 would be checked against 49/98. They would have the same result and the function would return 1. So now all we need to do is filter out all of the times that the numbers are both multiple of tens and find all of the fractions that are 'curious'.

list = []            
for a in range(10,99):
    for b in range(a + 1,99):
        if curious(a,b):
            if a%10 and b%10:
                 list.append(reduce_fract(a,b))

This code works because for any number like 30 (a multiple of 10) is a or b then 30%10 will equal 0. 0 is always evaluated to mean False so the if statement is never triggered when either of the numbers are divisable by ten. This removes all of the numbers that are not needed by the problem. Now all we have to do is complete the final piece of the puzzle. They want the product of the four fractions that are 'curious' in their lowest common terms. So we will need to write a function that reduces fractions to their lowest common terms. We can do that by iterating over every number from 2 to the numerator and whenever both of the numbers are divisible by that number we simply divide them both and them keep on checking every digit. This function is as follows:

def reduce_fract(a,b):
    for i in range(2,a + 1):
        if a%i == 0 and b%i == 0:
            a /= i
            b /= i
            return reduce_fract(a,b)
    return (a,b)

So putting it all together we get a run time of just 0.019 seconds, no need to even attempt to optimize this code anymore so here is my first attempt at solving this problem.

def curious(a,b):
    try:
        c = float(a)/b
        if a/10 == b/10:
            if float(a%10)/(b%10) == c:
                return 1
        if a/10 == b%10:
            if float(a%10)/(b/10) == c:
                return 1
        if a%10 == b/10:
            if float(a/10)/(b%10) == c:
                return 1
        if a%10 == b%10:
            if float(a/10)/(b/10) == c:
                return 1
    except:
        return 0
    return 0

def reduce_fract(a,b):
    for i in range(2,a + 1):
        if a%i == 0 and b%i == 0:
            a /= i
            b /= i
            return reduce_fract(a,b)
    return (a,b)

list = []            
for a in range(10,99):
    for b in range(a + 1,99):
        if curious(a,b):
            if a%10 and b%10:
                 list.append(reduce_fract(a,b))

print list
print reduce_fract(reduce(lambda x,y: x*y,map(lambda x: x[0], list)),reduce(lambda x,y: x*y,map(lambda x: x[1], list)))

The last line of this map be a little confusing. Each of the reduce statements's functions are simply multiplying the numerators and denominators together using both lambda calculus and reduce. If you do not understand how these work don't worry too much about them for now. I will be describing them more in depth in a future blog post.