extra/project-euler/164/164.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays assocs kernel math math.ranges sequences ;
   4 IN: project-euler.164
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=164
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! How many 20 digit numbers n (without any leading zero) exist such
  12 ! that no three consecutive digits of n have a sum greater than 9?
  13
  14
  15 ! SOLUTION
  16 ! --------
  17
  18 <PRIVATE
  19
  20 : next-keys ( key -- keys )
  21     [ peek ] [ 10 swap sum - ] bi [ 2array ] with map ;
  22
  23 : next-table ( assoc -- assoc )
  24     H{ } clone swap
  25     [ swap next-keys [ pick at+ ] with each ] assoc-each ;
  26
  27 : init-table ( -- assoc )
  28     9 [1,b] [ 1array 1 ] H{ } map>assoc ;
  29
  30 PRIVATE>
  31
  32 : euler164 ( -- answer )
  33     init-table 19 [ next-table ] times values sum ;
  34
  35 ! [ euler164 ] 100 ave-time
  36 ! 7 ms ave run time - 1.23 SD (100 trials)
  37
  38 MAIN: euler164