|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 33: Digit Cancelling Fractions |
|
3
|
|
|
==================================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem33 |
|
6
|
|
|
:synopsis: My solution to problem #33. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem33.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
The fraction :math:`\\frac{49}{98}` is a curious fraction, as an inexperienced mathematician in attempting to simplify |
|
|
|
|
|
|
15
|
|
|
it may incorrectly believe that :math:`\\frac{49}{98} = \\frac{4}{8}`, which is correct, is obtained by cancelling the |
|
|
|
|
|
|
16
|
|
|
:math:`9\\mbox{s}`. |
|
17
|
|
|
|
|
18
|
|
|
We shall consider fractions like, :math:`\\frac{30}{50} = \\frac{3}{5}`, to be trivial examples. |
|
19
|
|
|
|
|
20
|
|
|
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits |
|
|
|
|
|
|
21
|
|
|
in the numerator and denominator. |
|
22
|
|
|
|
|
23
|
|
|
If the product of these four fractions is given in its lowest common terms, find the value of the denominator. |
|
|
|
|
|
|
24
|
|
|
|
|
25
|
|
|
Solution Discussion |
|
26
|
|
|
################### |
|
27
|
|
|
|
|
28
|
|
|
Nothing special here, just implement the faulty cancelling logic and see when it just so happens to agree with the |
|
|
|
|
|
|
29
|
|
|
correct arithmetic results. Accumulate these so-called curious fractions. |
|
30
|
|
|
|
|
31
|
|
|
Solution Implementation |
|
32
|
|
|
####################### |
|
33
|
|
|
|
|
34
|
|
|
.. literalinclude:: ../../solutions/problem33.py |
|
35
|
|
|
:language: python |
|
36
|
|
|
:lines: 39- |
|
37
|
|
|
""" |
|
38
|
|
|
|
|
39
|
|
|
from fractions import Fraction |
|
40
|
|
|
from typing import Tuple |
|
41
|
|
|
|
|
42
|
|
|
from lib.digital import digits_of, digits_to_num |
|
43
|
|
|
|
|
44
|
|
|
|
|
45
|
|
|
def simplify_bad(a: int, b: int) -> Tuple[int, int]: |
|
|
|
|
|
|
46
|
|
|
""" Simplify the fraction :math:`\\frac{a}{b}` using the incorrect logic specified for this problem |
|
|
|
|
|
|
47
|
|
|
|
|
48
|
|
|
In particular, individual decimal digits are directly cancelled with each other rather than considering common |
|
|
|
|
|
|
49
|
|
|
divisors of :math:`a` and :math:`b`. |
|
50
|
|
|
|
|
51
|
|
|
:param a: fraction numerator |
|
52
|
|
|
:param b: fraction denominator |
|
53
|
|
|
:return: the simplified fraction :math:`\\frac{a}{b}` using the incorrect logic |
|
54
|
|
|
|
|
55
|
|
|
>>> simplify_bad(49, 98) |
|
56
|
|
|
(4, 8) |
|
57
|
|
|
""" |
|
58
|
|
|
|
|
59
|
|
|
# Get the decimal digits of the numerator and denominator |
|
60
|
|
|
a_digits = digits_of(a, base=10) |
|
61
|
|
|
b_digits = digits_of(b, base=10) |
|
62
|
|
|
|
|
63
|
|
|
# Build copies of the digits and start cancel them out if possible |
|
64
|
|
|
aa = a_digits.copy() |
|
|
|
|
|
|
65
|
|
|
bb = b_digits.copy() |
|
|
|
|
|
|
66
|
|
|
for a_i in a_digits: |
|
67
|
|
|
if a_i in bb and a_i != 0: |
|
68
|
|
|
aa.remove(a_i) |
|
69
|
|
|
bb.remove(a_i) |
|
70
|
|
|
|
|
71
|
|
|
return digits_to_num(aa), digits_to_num(bb) # convert the remaining digits back to integers |
|
72
|
|
|
|
|
73
|
|
|
|
|
74
|
|
|
def is_curious_fraction(x: int, y: int, x_bad: int, y_bad: int) -> bool: |
|
|
|
|
|
|
75
|
|
|
""" Test to see if :math:`\\frac{x}{y}` is a "curious fraction" |
|
76
|
|
|
|
|
77
|
|
|
:param x: the numerator of the fraction |
|
78
|
|
|
:param y: the denominator of the fraction |
|
79
|
|
|
:param x_bad: the numerator of the (incorrectly) cancelled fraction |
|
80
|
|
|
:param y_bad: the denominator of the (incorrectly) cancelled fraction |
|
81
|
|
|
:return: whether :math:`\\frac{x}{y}` is a "curious fraction" or not |
|
82
|
|
|
""" |
|
83
|
|
|
|
|
84
|
|
|
if x_bad == x: |
|
|
|
|
|
|
85
|
|
|
return False # no cancellation occurred, cannot be "curious" |
|
86
|
|
|
elif y_bad == 0: |
|
87
|
|
|
return False # cancellation resulted in invalid fraction |
|
88
|
|
|
else: |
|
89
|
|
|
return x_bad / y_bad == x / y |
|
90
|
|
|
|
|
91
|
|
|
|
|
92
|
|
|
def solve(): |
|
93
|
|
|
""" Compute the answer to Project Euler's problem #33 """ |
|
94
|
|
|
|
|
95
|
|
|
n_digits = 2 # number of digits in each numerator/denominator |
|
96
|
|
|
curious_product = Fraction(1, 1) # will accumulate the product of curious fractions |
|
97
|
|
|
|
|
98
|
|
|
for numerator in range(10 ** (n_digits - 1), 10 ** n_digits): |
|
99
|
|
|
for denominator in range(numerator + 1, 10 ** n_digits): |
|
100
|
|
|
numerator_cancelled, denominator_cancelled = simplify_bad(numerator, denominator) |
|
101
|
|
|
if is_curious_fraction(numerator, denominator, numerator_cancelled, denominator_cancelled): |
|
|
|
|
|
|
102
|
|
|
curious_product *= Fraction(numerator_cancelled, denominator_cancelled) |
|
103
|
|
|
|
|
104
|
|
|
answer = curious_product.denominator # extract the denominator from the simplified fraction |
|
105
|
|
|
return answer |
|
106
|
|
|
|
|
107
|
|
|
|
|
108
|
|
|
expected_answer = 100 |
|
|
|
|
|
|
109
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.