1 ! Copyright (c) 2009 Guillaume Nargeot.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors kernel math math.ranges project-euler.common
7 ! http://projecteuler.net/index.php?section=problems&id=85
12 ! By counting carefully it can be seen that a rectangular grid measuring
13 ! 3 by 2 contains eighteen rectangles.
15 ! Although there exists no rectangular grid that contains exactly two million
16 ! rectangles, find the area of the grid with the nearest solution.
22 ! A grid measuring x by y contains x * (x + 1) * y * (x + 1) / 4 rectangles.
27 2000000 - abs ; inline
29 : rectangles-count ( a b -- n )
30 2dup [ 1 + ] bi@ * * * 4 /i ; inline
32 :: each-unique-product ( ... a b quot: ( ... i j -- ... ) -- ... )
39 TUPLE: result { area read-only } { distance read-only } ;
43 : min-by-distance ( seq seq -- seq )
44 [ [ distance>> ] bi@ < ] most ; inline
46 : compute-result ( i j -- pair )
47 [ * ] [ rectangles-count distance ] 2bi <result> ; inline
49 : area-of-nearest ( -- n )
50 T{ result f 0 2000000 } 1 2000
51 [ compute-result min-by-distance ] each-unique-product area>> ;
55 : euler085 ( -- answer )
58 ! [ euler085 ] 100 ave-time
59 ! 791 ms ave run time - 17.15 SD (100 trials)