extra/project-euler/033/033.factor

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