extra/project-euler/033/033.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math ranges project-euler.common sequences ;
   4 IN: project-euler.033
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=33
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! The fraction 49/98 is a curious fraction, as an inexperienced mathematician
  12 ! in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which
  13 ! is correct, is obtained by cancelling the 9s.
  14
  15 ! We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
  16
  17 ! There are exactly four non-trivial examples of this type of fraction, less
  18 ! than one in value, and containing two digits in the numerator and
  19 ! denominator.
  20
  21 ! If the product of these four fractions is given in its lowest common terms,
  22 ! find the value of the denominator.
  23
  24
  25 ! SOLUTION
  26 ! --------
  27
  28 ! Through analysis, you only need to check fractions fitting the pattern ax/xb
  29
  30 <PRIVATE
  31
  32 : source-033 ( -- seq )
  33     10 99 [a..b] dup cartesian-product concat [ first2 < ] filter ;
  34
  35 : safe? ( ax xb -- ? )
  36     [ 10 /mod ] bi@ [ = ] dip zero? not and nip ;
  37
  38 : ax/xb ( ax xb -- z/f )
  39     2dup safe? [ [ 10 /mod ] bi@ 2nip / ] [ 2drop f ] if ;
  40
  41 : curious? ( m n -- ? )
  42     2dup / [ ax/xb ] dip = ;
  43
  44 : curious-fractions ( seq -- seq )
  45     [ first2 curious? ] filter [ first2 / ] map ;
  46
  47 PRIVATE>
  48
  49 : euler033 ( -- answer )
  50     source-033 curious-fractions product denominator ;
  51
  52 ! [ euler033 ] 100 ave-time
  53 ! 7 ms ave run time - 1.31 SD (100 trials)
  54
  55 SOLUTION: euler033