-! Copyright (c) 2008 Eric Mertens
+! Copyright (c) 2008 Eric Mertens.
! See http://factorcode.org/license.txt for BSD license.
-USING: kernel math math.ranges sequences sequences.lib ;
-
+USING: kernel math ranges sequences project-euler.common ;
IN: project-euler.116
! http://projecteuler.net/index.php?section=problems&id=116
! -----------
! A row of five black square tiles is to have a number of its tiles replaced
-! with coloured oblong tiles chosen from red (length two), green (length
+! with colored oblong tiles chosen from red (length two), green (length
! three), or blue (length four).
! If red tiles are chosen there are exactly seven ways this can be done.
! If green tiles are chosen there are three ways.
! And if blue tiles are chosen there are two ways.
-! Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of
+! Assuming that colors cannot be mixed there are 7 + 3 + 2 = 12 ways of
! replacing the black tiles in a row measuring five units in length.
! How many different ways can the black tiles in a row measuring fifty units in
-! length be replaced if colours cannot be mixed and at least one coloured tile
+! length be replaced if colors cannot be mixed and at least one colored tile
! must be used?
+
! SOLUTION
! --------
<PRIVATE
: nth* ( n seq -- elt/0 )
- [ length swap - 1- ] keep ?nth 0 or ;
+ [ length swap - 1 - ] keep ?nth 0 or ;
: next ( colortile seq -- )
- [ nth* ] [ peek + ] [ push ] tri ;
+ [ nth* ] [ last + ] [ push ] tri ;
: ways ( length colortile -- permutations )
- V{ 1 } clone [ [ next ] 2curry times ] keep peek 1- ;
-
-PRIVATE>
+ V{ 1 } clone [ [ next ] 2curry times ] keep last 1 - ;
: (euler116) ( length -- permutations )
- 3 [1,b] [ ways ] with sigma ;
+ 3 [1..b] [ ways ] with map-sum ;
-: euler116 ( -- permutations )
+PRIVATE>
+
+: euler116 ( -- answer )
50 (euler116) ;
+
+! [ euler116 ] 100 ave-time
+! 0 ms ave run time - 0.34 SD (100 trials)
+
+SOLUTION: euler116