Project Euler Problem 33 Solution

Question

The fraction \frac{49}{98} is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that \frac{49}{98} = \frac{4}{8}, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, \frac{30}{50} = \frac{3}{5}, 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.

Haskell

import Data.Ratio (denominator)

fraction :: Int -> Int -> Rational
fraction n d = fromIntegral n / fromIntegral d

curious :: Int -> Int -> Bool
curious n d | f > 1 = False
            | d1 == 0 || d2 == 0 = False
            | n == d = False
            | n2 /= d1 = False
            | otherwise = fraction n1 d2 == f
            where f = fraction n d
                  (n1, n2) = quotRem n 10
                  (d1, d2) = quotRem d 10

main :: IO ()
main = print $ denominator $ product [fraction n d | n <- [10..99], d <- [10..99], curious n d]

$ ghc -O2 -o curious-fractions curious-fractions.hs
$ time ./curious-fractions
real   0m0.003s
user   0m0.000s
sys    0m0.003s

Python

#!/usr/bin/env python
from fractions import *
from itertools import *
from functools import reduce

def is_curious(n, d):
    f = Fraction(n, d)
    if f >= 1:
        return False
    n_digits = [int(digit) for digit in str(n)]
    d_digits = [int(digit) for digit in str(d)]

    if n_digits[1] == d_digits[0]:
        try:
            if Fraction(n_digits[0], d_digits[1]) == f:
                return True
        except:
            pass
    return False
def main():
    fractions = product(list(range(10, 100)), list(range(10, 100)))
    print(reduce(lambda a, b: a * b, (Fraction(*f) for f in fractions if is_curious(*f))).denominator)

if __name__ == "__main__":
    main()

$ time python3 curious-fractions.py
real   0m0.073s
user   0m0.073s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
puts ('10'..'99').to_a.product(('10'..'99').to_a).select { |num, den|
  (num[0].to_f / den[1].to_f) == (num.to_f / den.to_f) && num[1] == den[0] && num[1] != den[1]
}.uniq.map { |num, den| [num.to_i, den.to_i] }.reduce([1, 1]) { |p, v|
  f = [p[0] * v[0], p[1] * v[1]]
  [f[0] / f[0].gcd(f[1]), f[1] / f[0].gcd(f[1])]
}[1]

$ time ruby curious-fractions.rb
real   0m0.045s
user   0m0.044s
sys    0m0.000s