extra/project-euler/043/043.factor

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