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