# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1488477848 0
# Node ID 1138be746556c10189001059b2e9022240d25e0d
# Parent  6936c3316864e562500408ed4401827ef8968b36
Problem 58

diff -r 6936c3316864 -r 1138be746556 src/euler.lisp
--- a/src/euler.lisp	Thu Mar 02 16:50:43 2017 +0000
+++ b/src/euler.lisp	Thu Mar 02 18:04:08 2017 +0000
@@ -151,34 +151,24 @@
            (finding i :such-that (= 1 (mod v modulus)))))
 
 
-(defun number-spiral (size)
-  ;; See problem 28
-  (assert (oddp size) (size))
-  (flet ((turn (dx dy)
-           (cond
-             ((and (= dx  1) (= dy  0)) (values  0  1))
-             ((and (= dx -1) (= dy  0)) (values  0 -1))
-             ((and (= dx  0) (= dy  1)) (values -1  0))
-             ((and (= dx  0) (= dy -1)) (values  1  0)))))
-    (iterate
-      (with array = (make-array (list size size)))
-      (with i = 1)
-      (with x = (floor (/ size 2)))
-      (with y = (floor (/ size 2)))
-      (with dx = 1)
-      (with dy = 0)
-      (initially (setf (aref array y x) i))
-      (for counter :from 1 :by 1/2)
-      (for run-length = (truncate counter))
-      (iterate (repeat run-length)
-               (incf i)
-               (incf x dx)
-               (incf y dy)
-               (if (and (in-range-p 0 x size)
-                        (in-range-p 0 y size))
-                 (setf (aref array y x) i)
-                 (return-from number-spiral array)))
-      (setf (values dx dy) (turn dx dy)))))
+(defun number-spiral-corners (size)
+  "Return a list of the corner values of a 'number spiral' of size `size`.
+
+  `size` must be odd.  The order of the corners in the resulting list is
+  unspecified.
+
+  Note that the \"spiral\" of size one has just a single \"corner\": `1`.
+
+  "
+  (assert (oddp size))
+  (if (= 1 size)
+    (list 1)
+    (let ((leg (1- size))
+          (final (square size)))
+      (list (- final (* 0 leg))
+            (- final (* 1 leg))
+            (- final (* 2 leg))
+            (- final (* 3 leg))))))
 
 
 (defun truncate-number-left (n amount &optional (radix 10))
@@ -1000,16 +990,8 @@
   ;;
   ;; What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
   ;; formed in the same way?
-  (let* ((size 1001)
-         (spiral (number-spiral size)))
-    (+ (iterate (for x :from 0 :below size) ; \
-                (for y :from 0 :below size)
-                (summing (aref spiral y x)))
-       (iterate (for x :from (1- size) :downto 0) ; /
-                (for y :from 0 :below size)
-                (summing (aref spiral y x)))
-       ;; don't double-count the center...
-       (- (aref spiral (truncate size 2) (truncate size 2))))))
+  (iterate (for size :from 1 :to 1001 :by 2)
+           (summing (apply #'+ (number-spiral-corners size)))))
 
 (defun problem-29 ()
   ;; Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
@@ -1730,6 +1712,40 @@
     (counting (> (digits-length (numerator expansion))
                  (digits-length (denominator expansion))))))
 
+(defun problem-58 ()
+  ;; Starting with 1 and spiralling anticlockwise in the following way, a square
+  ;; spiral 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 spiral above, a square
+  ;; spiral with side length 9 will be formed. If this process is continued,
+  ;; what is the side length of the square spiral for which the ratio of primes
+  ;; along both diagonals first falls below 10%?
+  (labels ((score (value)
+             (if (primep value) 1 0))
+           (primes-in-layer (size)
+             (sum (number-spiral-corners size) :key #'score)))
+    (iterate
+      (for size :from 3 :by 2)
+      (for count :from 5 :by 4)
+      (sum (primes-in-layer size) :into primes)
+      (for ratio = (/ primes count))
+      (finding size :such-that (< ratio 1/10)))))
+
+
+
+
 
 (defun problem-74 ()
   ;; The number 145 is well known for the property that the sum of the factorial
@@ -1857,9 +1873,10 @@
 (test p55 (is (= 249 (problem-55))))
 (test p56 (is (= 972 (problem-56))))
 (test p57 (is (= 153 (problem-57))))
+(test p58 (is (= 26241 (problem-58))))
 
 (test p74 (is (= 402 (problem-74))))
 (test p145 (is (= 608720 (problem-145))))
 
 
-;; (run! :euler)
+(run! :euler)