extra/project-euler/043/043.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators.short-circuit kernel math math.functions math.combinatorics
   4     math.parser math.ranges project-euler.common sequences sets sorting ;
   5 IN: project-euler.043
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=43
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The number, 1406357289, is a 0 to 9 pandigital number because it is made up
  13 ! of each of the digits 0 to 9 in some order, but it also has a rather
  14 ! interesting sub-string divisibility property.
  15
  16 ! Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note
  17 ! the following:
  18
  19 !     * d2d3d4  = 406 is divisible by 2
  20 !     * d3d4d5  = 063 is divisible by 3
  21 !     * d4d5d6  = 635 is divisible by 5
  22 !     * d5d6d7  = 357 is divisible by 7
  23 !     * d6d7d8  = 572 is divisible by 11
  24 !     * d7d8d9  = 728 is divisible by 13
  25 !     * d8d9d10 = 289 is divisible by 17
  26
  27 ! Find the sum of all 0 to 9 pandigital numbers with this property.
  28
  29
  30 ! SOLUTION
  31 ! --------
  32
  33 ! Brute force generating all the pandigitals then checking 3-digit divisiblity
  34 ! properties...this is very slow!
  35
  36 <PRIVATE
  37
  38 : subseq-divisible? ( n index seq -- ? )
  39     [ 1 - dup 3 + ] dip subseq 10 digits>integer swap divisor? ;
  40
  41 : interesting? ( seq -- ? )
  42     {
  43         [ 17 8 rot subseq-divisible? ]
  44         [ 13 7 rot subseq-divisible? ]
  45         [ 11 6 rot subseq-divisible? ]
  46         [ 7  5 rot subseq-divisible? ]
  47         [ 5  4 rot subseq-divisible? ]
  48         [ 3  3 rot subseq-divisible? ]
  49         [ 2  2 rot subseq-divisible? ]
  50     } 1&& ;
  51
  52 PRIVATE>
  53
  54 : euler043 ( -- answer )
  55     1234567890 number>digits 0 [
  56         dup interesting? [
  57             10 digits>integer +
  58         ] [ drop ] if
  59     ] reduce-permutations ;
  60
  61 ! [ euler043 ] time
  62 ! 60280 ms run / 59 ms GC time
  63
  64
  65 ! ALTERNATE SOLUTIONS
  66 ! -------------------
  67
  68 ! Build the number from right to left, generating the next 3-digits according
  69 ! to the divisiblity rules and combining them with the previous digits if they
  70 ! overlap and still have all unique digits. When done with that, add whatever
  71 ! missing digit is needed to make the number pandigital.
  72
  73 <PRIVATE
  74
  75 : candidates ( n -- seq )
  76     1000 over <range> [ number>digits 3 0 pad-head ] map [ all-unique? ] filter ;
  77
  78 : overlap? ( seq -- ? )
  79     [ first 2 tail* ] [ second 2 head ] bi = ;
  80
  81 : clean ( seq -- seq )
  82     [ unclip 1 head prefix concat ] map [ all-unique? ] filter ;
  83
  84 : add-missing-digit ( seq -- seq )
  85     dup natural-sort 10 swap diff prepend ;
  86
  87 : interesting-pandigitals ( -- seq )
  88     17 candidates { 13 11 7 5 3 2 } [
  89         candidates swap cartesian-product [ overlap? ] filter clean
  90     ] each [ add-missing-digit ] map ;
  91
  92 PRIVATE>
  93
  94 : euler043a ( -- answer )
  95     interesting-pandigitals [ 10 digits>integer ] sigma ;
  96
  97 ! [ euler043a ] 100 ave-time
  98 ! 10 ms ave run time - 1.37 SD (100 trials)
  99
 100 SOLUTION: euler043a