extra/project-euler/117/117.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.order sequences splitting ;
   4 IN: project-euler.117
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=117
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Using a combination of black square tiles and oblong tiles chosen
  12 ! from: red tiles measuring two units, green tiles measuring three
  13 ! units, and blue tiles measuring four units, it is possible to tile a
  14 ! row measuring five units in length in exactly fifteen different ways.
  15
  16 ! How many ways can a row measuring fifty units in length be tiled?
  17
  18
  19 ! SOLUTION
  20 ! --------
  21
  22 ! This solution uses a simple dynamic programming approach using the
  23 ! following recurence relation
  24
  25 ! ways(i) = 1 | i <= 0
  26 ! ways(i) = ways(i-4) + ways(i-3) + ways(i-2) + ways(i-1)
  27
  28 <PRIVATE
  29
  30 : short ( seq n -- seq n )
  31     over length min ;
  32
  33 : next ( seq -- )
  34     [ 4 short tail* sum ] keep push ;
  35
  36 : (euler117) ( n -- m )
  37     V{ 1 } clone tuck [ next ] curry times peek ;
  38
  39 PRIVATE>
  40
  41 : euler117 ( -- answer )
  42     50 (euler117) ;
  43
  44 ! [ euler117 ] 100 ave-time
  45 ! 0 ms run time - 100 trials
  46
  47 MAIN: euler117