extra/project-euler/164/164.factor

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