## 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[0]*dendig == v[1]*numdig: # v[0]/v[1] = numdig/dendig
fracs += [ v ]
p = reduce(lambda l,r:(l[0]*r[0],l[1]*r[1]),fracs) # multiply together solutions
return p[1] / gcd(*p) # reduce the fraction, return denom


Certainly room for improvement, but it works.

Tags: