## Problem 33 – Cancelling Fractions

by

49/98 = 4/8 if you cancel the 9s. This happens for few others fractions $n/d$ where $0, and we’ll also ignore $(n'\cdot 10)/(d'\cdot 10)$ for digits $n',d'$. Now take all these fractions that cancel like this, consider their product as a reduced fraction, and find the denominator. This is the challenge of problem 33.

Here’s what I came up with:

def gcd(a,b):
if b == 0:
return a
return gcd(b,a%b)

def solve():
fracs = [ ]
conv = lambda t:int("%s%s" % t)
for bothdig in xrange(1,10): # the digit that cancels
for numdig in xrange(1,10): # digit left in numerator
for dendig in xrange(1,10): # digit left in denom
nums = map(conv, [(numdig,bothdig),(bothdig,numdig)]) # consider bother orderings
dens = map(conv, [(dendig,bothdig),(bothdig,dendig)])
for v in [(n,d) for n in nums for d in dens if n<d]:
if v*dendig == v*numdig: # v/v = numdig/dendig
fracs += [ v ]
p = reduce(lambda l,r:(l*r,l*r),fracs) # multiply together solutions
return p / gcd(*p) # reduce the fraction, return denom


Certainly room for improvement, but it works.

Tags: