Problem #33 is yet another question that can be killed with basic brute force. The question reads:
Project Euler Problem 33: Digit cancelling 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 fractions, 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.
You can probably guess what my solution to this problem will be if you have been reading the last few blog entries.
Solution #1: Brute Force Approach
We simply iterate through all pairs of two-digit integers. There are at most 90*90 = 8100 pairs to worry about, so this iteration is very simple. The complicated part is finding each case for equal digits to appear in the numerator and the denominator. Once all of the fractions are found, it is a simple matter of multiplying all of the numerators and multiplying all of the denominators and dividing the denominator product . by the greatest common divisor of the numerator and the denominator. This greatest common divisor can be determined by using the Euclidean Algorithm. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #33
'''
import time
def gcd(a,b):
if(b>a):
return gcd(b,a)
while(min(a,b)>0):
temp = a%b
a = b
b = temp
return max(a,b)
def projectEulerProblemThirtyThree(n):
fractions = []
for a in range(10,n+1):
for b in range(10,n+1):
c = a/10
d = a%10
e = b/10
f = b%10
if(d == e and a!=b):
if(f*a==c*b):
fractions.append([a,b])
numerator = 1
denominator = 1
for x in fractions:
numerator*=x[0]
denominator*=x[1]
return denominator/(gcd(numerator,denominator))
start = time.time()
print projectEulerProblemThirtyThree(99)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
100
--- 0.00145101547241 seconds ---
for input of n = 99
'''
As shown above, for small inputs brute force can generally get the job done fairly efficiently. I may return to this question eventually to find a more efficient general solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 