1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.order sequences splitting ;
6 ! http://projecteuler.net/index.php?section=problems&id=117
11 ! Using a combination of black square tiles and oblong tiles chosen
12 ! from: red tiles measuring two units, green tiles measuring three
13 ! units, and blue tiles measuring four units, it is possible to tile a
14 ! row measuring five units in length in exactly fifteen different ways.
16 ! How many ways can a row measuring fifty units in length be tiled?
22 ! This solution uses a simple dynamic programming approach using the
23 ! following recurence relation
25 ! ways(i) = 1 | i <= 0
26 ! ways(i) = ways(i-4) + ways(i-3) + ways(i-2) + ways(i-1)
30 : short ( seq n -- seq n )
34 [ 4 short tail* sum ] keep push ;
36 : (euler117) ( n -- m )
37 V{ 1 } clone tuck [ next ] curry times peek ;
41 : euler117 ( -- answer )
44 ! [ euler117 ] 100 ave-time
45 ! 0 ms ave run time - 0.29 SD (100 trials)