81710e614e21
Problem 28
author | Steve Losh <steve@stevelosh.com> |
---|---|
date | Wed, 22 Feb 2017 18:01:30 +0000 |
parents | 404d59f863aa |
children | d2de8990952f |
branches/tags | (none) |
files | src/euler.lisp |
Changes
--- a/src/euler.lisp Wed Feb 22 17:26:37 2017 +0000 +++ b/src/euler.lisp Wed Feb 22 18:01:30 2017 +0000 @@ -140,6 +140,36 @@ (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))))) + + ;;;; Problems ----------------------------------------------------------------- (defun problem-1 () ;; If we list all the natural numbers below 10 that are multiples of 3 or 5, @@ -770,6 +800,31 @@ (b :from -1000 :to 1000))) (finding (* a b) :maximizing (primes-produced a b))))) +(defun problem-28 () + ;; Starting with the number 1 and moving to the right in a clockwise direction + ;; a 5 by 5 spiral is formed as follows: + ;; + ;; 21 22 23 24 25 + ;; 20 7 8 9 10 + ;; 19 6 1 2 11 + ;; 18 5 4 3 12 + ;; 17 16 15 14 13 + ;; + ;; It can be verified that the sum of the numbers on the diagonals is 101. + ;; + ;; 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)))))) + ;;;; Tests -------------------------------------------------------------------- (def-suite :euler) @@ -801,6 +856,8 @@ (test p24 (is (= 2783915460 (problem-24)))) (test p25 (is (= 4782 (problem-25)))) (test p26 (is (= 983 (problem-26)))) +(test p27 (is (= -59231 (problem-27)))) +(test p28 (is (= 669171001 (problem-28)))) ;; (run! :euler)