extra/project-euler/117/117.factor

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