extra/project-euler/092/092.factor

   1 ! Copyright (c) 2008 Aaron Schaefer, Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.ranges project-euler.common sequences ;
   4 IN: project-euler.092
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=92
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! A number chain is created by continuously adding the square of the digits in
  12 ! a number to form a new number until it has been seen before.
  13
  14 ! For example,
  15
  16 !     44 -> 32 -> 13 -> 10 -> 1 -> 1
  17 !     85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89
  18
  19 ! Therefore any chain that arrives at 1 or 89 will become stuck in an endless
  20 ! loop. What is most amazing is that EVERY starting number will eventually
  21 ! arrive at 1 or 89.
  22
  23 ! How many starting numbers below ten million will arrive at 89?
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 <PRIVATE
  30
  31 : next-link ( n -- m )
  32     number>digits [ sq ] sigma ;
  33
  34 : chain-ending ( n -- m )
  35     dup [ 1 = ] [ 89 = ] bi or [ next-link chain-ending ] unless ;
  36
  37 : lower-endings ( -- seq )
  38     567 [1,b] [ chain-ending ] map ;
  39
  40 : fast-chain-ending ( seq n -- m )
  41     dup 567 > [ next-link ] when 1 - swap nth ;
  42
  43 PRIVATE>
  44
  45 : euler092 ( -- answer )
  46     lower-endings 9999999 [1,b] [ fast-chain-ending 89 = ] with count ;
  47
  48 ! [ euler092 ] 10 ave-time
  49 ! 33257 ms ave run time - 624.27 SD (10 trials)
  50
  51 ! TODO: this solution is not very efficient, much better optimizations exist
  52
  53 SOLUTION: euler092