Solution to Project Euler problem 85

diff --git a/extra/project-euler/085/085-tests.factor b/extra/project-euler/085/085-tests.factor
new file mode 100644 (file)
index 0000000..2dadf6a
--- /dev/null
+++ b/extra/project-euler/085/085-tests.factor
@@ -0,0 +1,4 @@
+USING: project-euler.085 tools.test ;
+IN: project-euler.085.tests
+
+[ 2772 ] [ euler085 ] unit-test

diff --git a/extra/project-euler/085/085.factor b/extra/project-euler/085/085.factor
new file mode 100644 (file)
index 0000000..bd09203
--- /dev/null
+++ b/extra/project-euler/085/085.factor
@@ -0,0 +1,57 @@
+! Copyright (c) 2009 Guillaume Nargeot.
+! See http://factorcode.org/license.txt for BSD license.
+USING: arrays kernel math math.ranges project-euler.common sequences ;
+IN: project-euler.085
+
+! http://projecteuler.net/index.php?section=problems&id=85
+
+! DESCRIPTION
+! -----------
+
+! By counting carefully it can be seen that a rectangular grid measuring
+! 3 by 2 contains eighteen rectangles.
+
+! Although there exists no rectangular grid that contains exactly two million
+! rectangles, find the area of the grid with the nearest solution.
+
+
+! SOLUTION
+! --------
+
+! A grid measuring x by y contains x * (x + 1) * y * (x + 1) rectangles.
+
+<PRIVATE
+
+: distance ( m -- n )
+    2000000 - abs ;
+
+: rectangles-count ( a b -- n )
+    2dup [ 1 + ] bi@ * * * 4 / ;
+
+: unique-products ( a b -- seq )
+    tuck [a,b] [
+        over dupd [a,b] [ 2array ] with map
+    ] map concat nip ;
+
+: max-by-last ( seq seq -- seq )
+    [ [ last ] bi@ < ] most ;
+
+: array2 ( seq -- a b )
+    [ first ] [ last ] bi ;
+
+: convert ( seq -- seq )
+    array2 [ * ] [ rectangles-count distance ] 2bi 2array ;
+
+: area-of-nearest ( -- n )
+    1 2000 unique-products
+    [ convert ] [ max-by-last ] map-reduce first ;
+
+PRIVATE>
+
+: euler085 ( -- answer )
+    area-of-nearest ;
+
+! [ euler085 ] 100 ave-time
+! 2285 ms ave run time - 4.8 SD (100 trials)
+
+SOLUTION: euler085

diff --git a/extra/project-euler/authors.txt b/extra/project-euler/authors.txt
index d280bffce6277dc99b9063797c919f64017cb8c2..50d93f655232258a231aa7caaac4ea323ebc0f9b 100644 (file)
--- a/extra/project-euler/authors.txt
+++ b/extra/project-euler/authors.txt
@@ -1,2 +1,3 @@
 Aaron Schaefer
 Eric Mertens
+Guillaume Nargeot

diff --git a/extra/project-euler/project-euler.factor b/extra/project-euler/project-euler.factor
index 95d364421500c6c50c315db2c6180d2256040e10..d925e2253de0c811c4b2f10dd8130e3d0c6df296 100644 (file)
--- a/extra/project-euler/project-euler.factor
+++ b/extra/project-euler/project-euler.factor
@@ -18,11 +18,11 @@ USING: definitions io io.files io.pathnames kernel math math.parser
     project-euler.055 project-euler.056 project-euler.057 project-euler.058
     project-euler.059 project-euler.063 project-euler.067 project-euler.069
     project-euler.071 project-euler.073 project-euler.075 project-euler.076
-    project-euler.079 project-euler.092 project-euler.097 project-euler.099
-    project-euler.100 project-euler.116 project-euler.117 project-euler.134
-    project-euler.148 project-euler.150 project-euler.151 project-euler.164
-    project-euler.169 project-euler.173 project-euler.175 project-euler.186
-    project-euler.190 project-euler.203 project-euler.215 ;
+    project-euler.079 project-euler.085 project-euler.092 project-euler.097
+    project-euler.099 project-euler.100 project-euler.116 project-euler.117
+    project-euler.134 project-euler.148 project-euler.150 project-euler.151
+    project-euler.164 project-euler.169 project-euler.173 project-euler.175
+    project-euler.186 project-euler.190 project-euler.203 project-euler.215 ;
 IN: project-euler
 
 <PRIVATE