extra/project-euler/116/116.factor

   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 ;
   4 IN: project-euler.116
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=116
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  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).
  14
  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.
  18
  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.
  21
  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
  24 ! must be used?
  25
  26
  27 ! SOLUTION
  28 ! --------
  29
  30 ! This solution uses a simple dynamic programming approach using the
  31 ! following recurence relation
  32
  33 ! ways(n,_) = 0   | n < 0
  34 ! ways(0,_) = 1
  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
  37
  38 <PRIVATE
  39
  40 : nth* ( n seq -- elt/0 )
  41     [ length swap - 1 - ] keep ?nth 0 or ;
  42
  43 : next ( colortile seq -- )
  44      [ nth* ] [ last + ] [ push ] tri ;
  45
  46 : ways ( length colortile -- permutations )
  47     V{ 1 } clone [ [ next ] 2curry times ] keep last 1 - ;
  48
  49 : (euler116) ( length -- permutations )
  50     3 [1..b] [ ways ] with map-sum ;
  51
  52 PRIVATE>
  53
  54 : euler116 ( -- answer )
  55     50 (euler116) ;
  56
  57 ! [ euler116 ] 100 ave-time
  58 ! 0 ms ave run time - 0.34 SD (100 trials)
  59
  60 SOLUTION: euler116