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 math.ranges sequences sequences.lib ;
   4
   5 IN: project-euler.116
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=116
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  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).
  15
  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.
  19
  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.
  22
  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
  25 ! must be used?
  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* ] [ peek + ] [ push ] tri ;
  45
  46 : ways ( length colortile -- permutations )
  47     V{ 1 } clone [ [ next ] 2curry times ] keep peek 1- ;
  48
  49 PRIVATE>
  50
  51 : (euler116) ( length -- permutations )
  52     3 [1,b] [ ways ] with sigma ;
  53
  54 : euler116 ( -- permutations )
  55     50 (euler116) ;