1 ! Copyright (c) 2008 Eric Mertens
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.ranges sequences sequences.lib ;
7 ! http://projecteuler.net/index.php?section=problems&id=116
12 ! A row of five black square tiles is to have a number of its tiles replaced
13 ! with coloured oblong tiles chosen from red (length two), green (length
14 ! three), or blue (length four).
16 ! If red tiles are chosen there are exactly seven ways this can be done.
17 ! If green tiles are chosen there are three ways.
18 ! And if blue tiles are chosen there are two ways.
20 ! Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of
21 ! replacing the black tiles in a row measuring five units in length.
23 ! How many different ways can the black tiles in a row measuring fifty units in
24 ! length be replaced if colours 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* ] [ peek + ] [ push ] tri ;
46 : ways ( length colortile -- permutations )
47 V{ 1 } clone [ [ next ] 2curry times ] keep peek 1- ;
51 : (euler116) ( length -- permutations )
52 3 [1,b] [ ways ] with sigma ;
54 : euler116 ( -- permutations )