extra/project-euler/052/052.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators.short-circuit kernel math
   4     project-euler.common sequences sorting
   5     grouping ;
   6 IN: project-euler.052
   7
   8 ! http://projecteuler.net/index.php?section=problems&id=52
   9
  10 ! DESCRIPTION
  11 ! -----------
  12
  13 ! It can be seen that the number, 125874, and its double, 251748, contain
  14 ! exactly the same digits, but in a different order.
  15
  16 ! Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,
  17 ! contain the same digits.
  18
  19
  20 ! SOLUTION
  21 ! --------
  22
  23 ! Analysis shows the number must be odd, divisible by 3, and larger than 123456
  24
  25 <PRIVATE
  26
  27 : map-nx ( n x -- seq )
  28     [ 1+ * ] with map ; inline
  29
  30 : all-same-digits? ( seq -- ? )
  31     [ number>digits natural-sort ] map all-equal? ;
  32
  33 : candidate? ( n -- ? )
  34     { [ odd? ] [ 3 mod 0 = ] } 1&& ;
  35
  36 : next-all-same ( x n -- n )
  37     dup candidate? [
  38         2dup swap map-nx all-same-digits?
  39         [ nip ] [ 1+ next-all-same ] if
  40     ] [
  41         1+ next-all-same
  42     ] if ;
  43
  44 PRIVATE>
  45
  46 : euler052 ( -- answer )
  47     6 123456 next-all-same ;
  48
  49 ! [ euler052 ] 100 ave-time
  50 ! 92 ms ave run time - 6.29 SD (100 trials)
  51
  52 MAIN: euler052