Closure, coin sums, & number spiral generator

3 files changed, 119 insertions, 0 deletions

diff --git a/number-spiral-diagonals/README.org b/number-spiral-diagonals/README.org
new file mode 100644
index 0000000..b3daba9
--- /dev/null
+++ b/number-spiral-diagonals/README.org
@@ -0,0 +1,34 @@
+* Solver for https://projecteuler.net/problem=28
+
+The above problem displays an interesting looking square of numbers (generated by counting up from one in a spiral pattern) and asks us to sum the diagonal for a very large square.
+
+In some cases to my detriment, I always try to look for a magical formula that will solve every problem.
+
+In this case, that is possible! We need only recognize that the numbers we are asked to sum belong to a sequence:
+
+The sequence: {1, 3, 5, 7, 9, 13, 17, 21, 25, 31, 37, 43, 49, 57...}
+
+We see that all of the numbers are odd. Further, we see that the first four numbers in the sequence are spaced two numbers apart. The next four numbers are all four numbers apart, then six numbers, then eight, etc.
+
+** Solution
+
+My solution is to implement a formula that can generate number /N/ (zero-indexed) in the sequence given the F_N_-1 (in other words, the preceeding number in the sequence. The formula is this:
+
+F_n = F_n_-1 + 2 * (((n-1) // 4) + 1)
+
+Here is an example of calculating the ninth number in the sequence (25):
+
+(zero indexed!)
+F_8 = F_7 + 2 * ((8-1) // 4) + 1)
+F_8 = 21 + 2 * (1 + 1)
+F_8 = 25
+
+And the tenth number:
+
+F_9 = F_8 + 2 * ((9-1) // 4) + 1)
+F_9 = 25 + 2 * (2 + 1)
+F_9 = 25 + 6
+F_9 = 31
+
+
+The scheme itself looks nicer than the formula.
diff --git a/number-spiral-diagonals/nsd-test.scm b/number-spiral-diagonals/nsd-test.scm
new file mode 100644
index 0000000..bcad616
--- /dev/null
+++ b/number-spiral-diagonals/nsd-test.scm
@@ -0,0 +1,58 @@
+;; -*- compile-command: "guile -L . nsd-test.scm"; -*-
+(use-modules (srfi srfi-64)
+             (nsd))
+
+
+(test-begin "harness")
+
+
+(test-equal "calculate-seq-length 1x1"
+  1
+  (calculate-seq-length 1))
+
+(test-equal "calculate-seq-length 3x3"
+  5
+  (calculate-seq-length 3))
+
+(test-equal "calculate-seq-length 5x5"
+  9
+  (calculate-seq-length 5))
+
+(test-equal "nsd-generator size 1"
+  '(1)
+  (nsd-generator 1))
+
+(test-equal "nsd-generator size 2"
+  '(1 3)
+  (nsd-generator 2))
+
+(test-equal "nsd-generator max two inc"
+  '(1 3 5 7 9)
+  (nsd-generator 5))
+
+(test-equal "nsd-generator four inc"
+  '(1 3 5 7 9 13)
+  (nsd-generator 6))
+
+(test-equal "nsd-generator six inc"
+  '(1 3 5 7 9 13 17 21 25 31)
+  (nsd-generator 10))
+
+(test-equal "nsd-generator eight inc"
+  '(1 3 5 7 9 13 17 21 25 31 37 43 49 57)
+  (nsd-generator 14))
+
+(test-equal "nsd add 1x1"
+  1
+  (nsd 1))
+
+(test-equal "nsd add 3x3"
+  25
+  (nsd 3))
+
+(test-equal "nsd add 7x7"
+  261
+  (nsd 7))
+
+
+(test-end "harness")
diff --git a/number-spiral-diagonals/nsd.scm b/number-spiral-diagonals/nsd.scm
new file mode 100644
index 0000000..9d4bfe3
--- /dev/null
+++ b/number-spiral-diagonals/nsd.scm
@@ -0,0 +1,27 @@
+(define-module (nsd)
+  #:export (nsd
+            nsd-generator
+            calculate-seq-length))
+
+
+(define (nsd n)
+  "Given dimension N of a square, calculates and sums
+an appropriately sized sequence."
+  (apply + (nsd-generator (calculate-seq-length n))))
+
+(define (nsd-generator k)
+  "Generates a sequence of numbers corresponding to the
+diagonals in a square. See README for more details on how
+this is used to solve the problem."
+  (let loop ((i 0)
+             (lst '(1)))
+    (if (>= (1+ i) k)
+        (reverse lst)
+        (loop (1+ i)
+              (cons (+ (car lst) (* 2 (1+ (quotient i 4)))) lst)))))
+
+(define (calculate-seq-length n)
+  "Calculates the size of the sequence. This is equal to
+the length of the two diagonals, minus one for the overlapping
+center."
+  (1- (* 2 n)))