extra/project-euler/028/028.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math ranges sequences project-euler.common ;
   4 IN: project-euler.028
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=28
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Starting with the number 1 and moving to the right in a clockwise direction a
  12 ! 5 by 5 spiral is formed as follows:
  13
  14 !     21 22 23 24 25
  15 !     20  7  8  9 10
  16 !     19  6  1  2 11
  17 !     18  5  4  3 12
  18 !     17 16 15 14 13
  19
  20 ! It can be verified that the sum of both diagonals is 101.
  21
  22 ! What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?
  23
  24
  25 ! SOLUTION
  26 ! --------
  27
  28 ! For a square sized n by n, the sum of corners is 4n² - 6n + 6
  29
  30 <PRIVATE
  31
  32 : sum-corners ( n -- sum )
  33     dup 1 = [ [ sq 4 * ] [ 6 * ] bi - 6 + ] unless ;
  34
  35 : sum-diags ( n -- sum )
  36     1 swap 2 <range> [ sum-corners ] map-sum ;
  37
  38 PRIVATE>
  39
  40 : euler028 ( -- answer )
  41     1001 sum-diags ;
  42
  43 ! [ euler028 ] 100 ave-time
  44 ! 0 ms ave run time - 0.39 SD (100 trials)
  45
  46 SOLUTION: euler028