extra/project-euler/173/173.factor

   1 ! Copyright (c) 2007 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions ranges sequences project-euler.common ;
   4 IN: project-euler.173
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=173
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! We shall define a square lamina to be a square outline with a square "hole"
  12 ! so that the shape possesses vertical and horizontal symmetry. For example,
  13 ! using exactly thirty-two square tiles we can form two different square
  14 ! laminae: [see URL for figure]
  15
  16 ! With one-hundred tiles, and not necessarily using all of the tiles at one
  17 ! time, it is possible to form forty-one different square laminae.
  18
  19 ! Using up to one million tiles how many different square laminae can be formed?
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 <PRIVATE
  26
  27 : laminae ( upper -- n )
  28     4 / dup sqrt [1..b] 0 rot [ over /i - - ] curry reduce ;
  29
  30 PRIVATE>
  31
  32 : euler173 ( -- answer )
  33     1000000 laminae ;
  34
  35 ! [ euler173 ] 100 ave-time
  36 ! 0 ms ave run time - 0.35 SD (100 trials)
  37
  38 SOLUTION: euler173