Project Euler 33

Earlier this morning I was reading through SICP and somewhere in chapter 2 there was a section about data abstraction involving rational numbers, which reminded me of Problem 33 on project euler.

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 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.

One of the hardest things—for me, at least—about problem solving is actually understanding the problem. Left this one off for a while because I wasn't sure what was meant by trivial. Of course then I decided to apply my brain properly and realized that a nontrivial example would look like this: ab/ca or ba/ac, if a, b and c are digits.

Wrote a function to check if a fraction is nontrivial and soon discovered a problem: if b & c were equal (ie, the numerator and denominator were palindromes), I would end up cancelling out a total of 4 digits and wouldn't have any number left at all!

So, I concluded, for the numerator n and denominator d of the fraction f, these conditions need to be true:

• n & d cannot be palindromes
• n < d so that f < 1
• f must be simplifiable
• likewise, f must have an unorthodox simplification
• the unorthodox simplification & the correct simplification of f must be equivalent
  • this was not as simple as saying unorthodoxSimplification f == correctSimplification f, because my unorthodox simplification of a fraction was not reduced. eg, unorthodoxSimplification (49/98) = 4/8, but correctSimplification (49/98) = 1/2. because I represented rational fractions as tuples this is what was happening: (4, 8) /= (1, 2)
• f must be nontrivial

And, happily, these conditions found me exactly four rational fractions. The rest was easy as pie: just folded over a list of the four fractions with a function that multiplies rational numbers, simplified the result, and extracted the denominator. Happy day :]