Solution to Project Euler problem 58

diff --git a/extra/project-euler/058/058-tests.factor b/extra/project-euler/058/058-tests.factor
new file mode 100644 (file)
index 0000000..13a2aaf
--- /dev/null
+++ b/extra/project-euler/058/058-tests.factor
@@ -0,0 +1,3 @@
+USING: project-euler.058 tools.test ;
+
+{ 26241 } [ euler058 ] unit-test

diff --git a/extra/project-euler/058/058.factor b/extra/project-euler/058/058.factor
new file mode 100644 (file)
index 0000000..133175f
--- /dev/null
+++ b/extra/project-euler/058/058.factor
@@ -0,0 +1,68 @@
+! Copyright (c) 2009 Aaron Schaefer.
+! See http://factorcode.org/license.txt for BSD license.
+USING: fry kernel math math.primes math.ranges project-euler.common sequences ;
+IN: project-euler.058
+
+! http://projecteuler.net/index.php?section=problems&id=58
+
+! DESCRIPTION
+! -----------
+
+! Starting with 1 and solveling anticlockwise in the following way, a square
+! solve with side length 7 is formed.
+
+!     37 36 35 34 33 32 31
+!     38 17 16 15 14 13 30
+!     39 18  5  4  3 12 29
+!     40 19  6  1  2 11 28
+!     41 20  7  8  9 10 27
+!     42 21 22 23 24 25 26
+!     43 44 45 46 47 48 49
+
+! It is interesting to note that the odd squares lie along the bottom right
+! diagonal, but what is more interesting is that 8 out of the 13 numbers lying
+! along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
+
+! If one complete new layer is wrapped around the solve above, a square solve
+! with side length 9 will be formed. If this process is continued, what is the
+! side length of the square solve for which the ratio of primes along both
+! diagonals first falls below 10%?
+
+
+! SOLUTION
+! --------
+
+<PRIVATE
+
+CONSTANT: PERCENT_PRIME 0.1
+
+! The corners of a square of side length n are:
+!    (n-2)² + 1(n-1)
+!    (n-2)² + 2(n-1)
+!    (n-2)² + 3(n-1)
+!    (n-2)² + 4(n-1) = odd squares, no need to calculate
+
+: prime-corners ( n -- m )
+    3 [1,b] swap '[ _ [ 1- * ] keep 2 - sq + prime? ] count ;
+
+: total-corners ( n -- m )
+    1- 2 * ; foldable
+
+: ratio-below? ( count length -- ? )
+    total-corners 1+ / PERCENT_PRIME < ;
+
+: next-layer ( count length -- count' length' )
+    2 + [ prime-corners + ] keep ;
+
+: solve ( count length -- length )
+    2dup ratio-below? [ nip ] [ next-layer solve ] if ;
+
+PRIVATE>
+
+: euler058 ( -- answer )
+    8 7 solve ;
+
+! [ euler058 ] 10 ave-time
+! 12974 ms ave run time - 284.46 SD (10 trials)
+
+SOLUTION: euler058

diff --git a/extra/project-euler/project-euler.factor b/extra/project-euler/project-euler.factor
index 62f6a56c652cd93269a96b148a8c6ae5465740dc..d60ae60126010467c6effee7618afa7993949e67 100644 (file)
--- a/extra/project-euler/project-euler.factor
+++ b/extra/project-euler/project-euler.factor
@@ -15,13 +15,14 @@ USING: definitions io io.files io.pathnames kernel math math.parser
     project-euler.041 project-euler.042 project-euler.043 project-euler.044
     project-euler.045 project-euler.046 project-euler.047 project-euler.048
     project-euler.049 project-euler.052 project-euler.053 project-euler.054
-    project-euler.055 project-euler.056 project-euler.057 project-euler.059
-    project-euler.067 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.055 project-euler.056 project-euler.057 project-euler.058
+    project-euler.059 project-euler.067 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 ;
 IN: project-euler
 
 <PRIVATE