 ! Copyright (c) 2008 Aaron Schaefer, Slava Pestov.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: kernel math math.ranges sequences ;
+USING: kernel math math.ranges project-euler.common sequences ;
 IN: project-euler.092
 
 ! http://projecteuler.net/index.php?section=problems&id=92

<PRIVATE

: next-link ( n -- m )
    0 swap [ dup zero? not ] [ 10 /mod sq -rot [ + ] dip ] [ ] while drop ;

: chain-ending ( n -- m )
    dup [ 1 = ] [ 89 = ] bi or [ next-link chain-ending ] unless ;

: fast-chain-ending ( seq n -- m )
    dup 567 > [ next-link ] when 1- swap nth ;

PRIVATE>

: euler092 ( -- answer )
    lower-endings 9999999 [1,b] [ fast-chain-ending 89 = ] with count ;

! [ euler092 ] 10 ave-time
! 33257 ms ave run time - 624.27 SD (10 trials)

! TODO: this solution is not very efficient, much better optimizations exist

MAIN: euler092
