1 ! Copyright (c) 2008 Eric Mertens.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math ranges sequences project-euler.common ;
6 ! http://projecteuler.net/index.php?section=problems&id=116
11 ! A row of five black square tiles is to have a number of its tiles replaced
12 ! with colored oblong tiles chosen from red (length two), green (length
13 ! three), or blue (length four).
15 ! If red tiles are chosen there are exactly seven ways this can be done.
16 ! If green tiles are chosen there are three ways.
17 ! And if blue tiles are chosen there are two ways.
19 ! Assuming that colors cannot be mixed there are 7 + 3 + 2 = 12 ways of
20 ! replacing the black tiles in a row measuring five units in length.
22 ! How many different ways can the black tiles in a row measuring fifty units in
23 ! length be replaced if colors cannot be mixed and at least one coloured tile
30 ! This solution uses a simple dynamic programming approach using the
31 ! following recurence relation
33 ! ways(n,_) = 0 | n < 0
35 ! ways(n,i) = ways(n-i,i) + ways(n-1,i)
36 ! solution(n) = ways(n,1) - 1 + ways(n,2) - 1 + ways(n,3) - 1
40 : nth* ( n seq -- elt/0 )
41 [ length swap - 1 - ] keep ?nth 0 or ;
43 : next ( colortile seq -- )
44 [ nth* ] [ last + ] [ push ] tri ;
46 : ways ( length colortile -- permutations )
47 V{ 1 } clone [ [ next ] 2curry times ] keep last 1 - ;
49 : (euler116) ( length -- permutations )
50 3 [1..b] [ ways ] with map-sum ;
54 : euler116 ( -- answer )
57 ! [ euler116 ] 100 ave-time
58 ! 0 ms ave run time - 0.34 SD (100 trials)