extra/project-euler/009/009.factor

   1 ! Copyright (c) 2007 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions namespaces sequences sorting ;
   4 IN: project-euler.009
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=9
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
  12 !     a² + b² = c²
  13
  14 ! For example, 3² + 4² = 9 + 16 = 25 = 5².
  15
  16 ! There exists exactly one Pythagorean triplet for which a + b + c = 1000.
  17 ! Find the product abc.
  18
  19
  20 ! SOLUTION
  21 ! --------
  22
  23 ! Algorithm adapted from http://www.friesian.com/pythag.com
  24
  25 <PRIVATE
  26
  27 : next-pq ( p1 q1 -- p2 q2 )
  28     ! p > q and both are odd integers
  29     dup 1 = [ drop 2 + dup ] when 2 - ;
  30
  31 : abc ( p q -- triplet )
  32     [
  33         2dup * ,                    ! a = p * q
  34         [ sq ] bi@ 2dup - 2 / ,  ! b = (p² - q²) / 2
  35         + 2 / ,                     ! c = (p² + q²) / 2
  36     ] { } make natural-sort ;
  37
  38 : (ptriplet) ( target p q triplet -- target p q )
  39     roll [ swap sum = ] keep -roll
  40     [ next-pq 2dup abc (ptriplet) ] unless ;
  41
  42 : ptriplet ( target -- triplet )
  43    3 1 { 3 4 5 } (ptriplet) abc nip ;
  44
  45 PRIVATE>
  46
  47 : euler009 ( -- answer )
  48     1000 ptriplet product ;
  49
  50 ! [ euler009 ] 100 ave-time
  51 ! 1 ms run / 0 ms GC ave time - 100 trials
  52
  53 MAIN: euler009