extra/project-euler/015/015.factor

   1 ! Copyright (c) 2007 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.combinatorics ;
   4 IN: project-euler.015
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=15
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Starting in the top left corner of a 2x2 grid, there are 6 routes (without
  12 ! backtracking) to the bottom right corner.
  13
  14 ! How many routes are there through a 20x20 grid?
  15
  16
  17 ! SOLUTION
  18 ! --------
  19
  20 <PRIVATE
  21
  22 : grid-paths ( n -- n )
  23     dup 2 * swap nCk ;
  24
  25 PRIVATE>
  26
  27 : euler015 ( -- answer )
  28     20 grid-paths ;
  29
  30 ! [ euler015 ] 100 ave-time
  31 ! 0 ms ave run time - 0.2 SD (100 trials)
  32
  33 MAIN: euler015