extra/project-euler/116/116.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math ranges sequences project-euler.common ;
   4 IN: project-euler.116
   5
   6 ! https://projecteuler.net/problem=116
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! A row of five black square tiles is to have a number of its
  12 ! tiles replaced with colored oblong tiles chosen from red
  13 ! (length two), green (length three), or blue (length four).
  14
  15 ! If red tiles are chosen there are exactly seven ways this can
  16 ! be done. If green tiles are chosen there are three ways. And
  17 ! if blue tiles are chosen there are two ways.
  18
  19 ! Assuming that colors cannot be mixed there are 7 + 3 + 2 = 12
  20 ! ways of replacing the black tiles in a row measuring five
  21 ! units in length.
  22
  23 ! How many different ways can the black tiles in a row measuring
  24 ! fifty units in length be replaced if colors cannot be mixed
  25 ! and at least one colored tile must be used?
  26
  27
  28 ! SOLUTION
  29 ! --------
  30
  31 ! This solution uses a simple dynamic programming approach using
  32 ! the following recurence relation
  33
  34 ! ways(n,_) = 0   | n < 0
  35 ! ways(0,_) = 1
  36 ! ways(n,i) = ways(n-i,i) + ways(n-1,i)
  37 ! solution(n) = ways(n,1) - 1 + ways(n,2) - 1 + ways(n,3) - 1
  38
  39 <PRIVATE
  40
  41 : nth* ( n seq -- elt/0 )
  42     [ length swap - 1 - ] keep ?nth 0 or ;
  43
  44 : next ( colortile seq -- )
  45     [ nth* ] [ last + ] [ push ] tri ;
  46
  47 : ways ( length colortile -- permutations )
  48     V{ 1 } clone [ [ next ] 2curry times ] keep last 1 - ;
  49
  50 : (euler116) ( length -- permutations )
  51     3 [1..b] [ ways ] with map-sum ;
  52
  53 PRIVATE>
  54
  55 : euler116 ( -- answer )
  56     50 (euler116) ;
  57
  58 ! [ euler116 ] 100 ave-time
  59 ! 0 ms ave run time - 0.34 SD (100 trials)
  60
  61 SOLUTION: euler116