extra/project-euler/173/173.factor

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