extra/project-euler/032/032.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.combinatorics math.functions math.parser math.ranges
   4     project-euler.common sequences sets ;
   5 IN: project-euler.032
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=32
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing
  13 ! multiplicand, multiplier, and product is 1 through 9 pandigital.
  14
  15 ! Find the sum of all products whose multiplicand/multiplier/product identity
  16 ! can be written as a 1 through 9 pandigital.
  17
  18 ! HINT: Some products can be obtained in more than one way so be sure to only
  19 ! include it once in your sum.
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 ! Generate all pandigital numbers and then check if they fit the identity
  26
  27 <PRIVATE
  28
  29 : source-032 ( -- seq )
  30     9 factorial [ 9 permutation [ 1+ ] map 10 digits>integer ] map ;
  31
  32 : 1and4 ( n -- ? )
  33     number>string 1 cut-slice 4 cut-slice
  34     [ string>number ] tri@ [ * ] dip = ;
  35
  36 : 2and3 ( n -- ? )
  37     number>string 2 cut-slice 3 cut-slice
  38     [ string>number ] tri@ [ * ] dip = ;
  39
  40 : valid? ( n -- ? )
  41     [ 1and4 ] [ 2and3 ] bi or ;
  42
  43 : products ( seq -- m )
  44     [ 10 4 ^ mod ] map ;
  45
  46 PRIVATE>
  47
  48 : euler032 ( -- answer )
  49     source-032 [ valid? ] filter products prune sum ;
  50
  51 ! [ euler032 ] 10 ave-time
  52 ! 16361 ms ave run time - 417.8 SD (10 trials)
  53
  54
  55 ! ALTERNATE SOLUTIONS
  56 ! -------------------
  57
  58 ! Generate all reasonable multiplicand/multiplier pairs, then multiply and see
  59 ! if the equation is pandigital
  60
  61 <PRIVATE
  62
  63 : source-032a ( -- seq )
  64     50 [1,b] 2000 [1,b] cartesian-product ;
  65
  66 ! multiplicand/multiplier/product
  67 : mmp ( pair -- n )
  68     first2 2dup * [ number>string ] tri@ 3append string>number ;
  69
  70 PRIVATE>
  71
  72 : euler032a ( -- answer )
  73     source-032a [ mmp ] map [ pandigital? ] filter products prune sum ;
  74
  75 ! [ euler032a ] 10 ave-time
  76 ! 2624 ms ave run time - 131.91 SD (10 trials)
  77
  78 MAIN: euler032a