Project Euler 33

Question: 

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, 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.

문제:

⁴⁹/₉₈은 재밌는 분수이다. 약분을 모르는 사람이 분자와 분모의 9를 지워서 약분을 이상하게 해서 ⁴⁹/₉₈ = ⁴/₈ 로 만들어도 정답이 된다.

다소 '당연한' 다음과 같은 분수도 생각할 수 있다. ³⁰/₅₀ = ³/₅

그 값이 1보다 작으면서, 분자와 분모 모두 두 자리 수로 구성된 이러한 '당연하지 않은' 분수는 총 4개 존재한다.

그 4개의 분수들을 곱한 뒤 약분한 결과의 분모를 구하여라.

Solution:

import time
from math import gcd
n = list()
d = list()
start = time.time()
for denom in range(11,100): #분모의 범위는 11 부터 99
    for nom in range(10,denom): #분자의 범위는 10부터 분모보다 작아야 한다.
        denom_list = list(str(denom)) # 분모를 str으로 변환
        nom_list = list(str(nom)) # 분자를 str으로 변환
        overlap = [x for x in denom_list if x in nom_list] # 중복되는 숫자

        if len(overlap) == 1: #하나의 숫자만이 반복됨
            if overlap[0] != '0': #sort out trivials
                denom_list.pop(denom_list.index(overlap[0])) # 분자에서 그 수를 지운다.
                nom_list.pop(nom_list.index(overlap[0])) # 분모에서 그 수를 지운다.
                if int(denom_list[0]) == 0: #분모가 0일 때는 건너뛰자.
                    pass
                elif int(nom_list[0]) / int(denom_list[0]) == nom / denom:
                    # 멍청한 약분의 결과가 맞는지 판별
                    n.append(nom)
                    d.append(denom)
nom = 1
denom = 1

for i in range(len(d)):
    nom *= n[i]
    denom *= d[i]

               
print("""Fractions: {0}/{4}, {1}/{5}, {2}/{6}, {3}/{7}
Found in ... {8:.5f}s
""".format(n[0],n[1],n[2],n[3],d[0],d[1],d[2],d[3],time.time() - start))
print("""Answer: {0}/{1} --> simplified {2:.0f}/{3:.0f}
""".format(nom,denom,nom / gcd(nom,denom),denom / gcd(nom,denom)))

Output:

Fractions: 16/64, 26/65, 19/95, 49/98

Found in ... 0.00856s

Answer: 387296/38729600 --> simplified 1/100

100