# Commits

committed 2f269be

Added a bunch of problem descriptions and a few solutions and improvements

# probs.clj

`     (count (take-while #(= f %) seq))))`
` `
` (defn run-length-encode [seq]`
`-  (if (nil? seq)`
`+  (if (or (nil? seq)`
`+          (nil? (first seq)))`
`     seq`
`     (let [f (first seq)`
`           cnt (count-uniq seq)]`
` `
` ;; This could be simpler`
` (defn is-square? [n]`
`-  (let [x (int (Math/sqrt n))]`
`-    (= (* x x) n)))`
`+  (and (let [d (rem n 4)]`
`+         (or (zero? d)`
`+             (= 1 d)))`
`+       (let [x (Math/round (Math/sqrt n))]`
`+         (= (* x x) n))))`
` `
` (defn prime-plus-2-square? [n]`
`   (filter is-square?`
` ;; Exactly four continued fractions, for N  13, have an odd period.`
` `
` ;; How many continued fractions for N  10000 have an odd period?`
`+(defn sqrt-period [n]`
`+  (if (is-square? n)`
`+    0))`
`+`
` `
` `
` ;}}}`
` ;; 272`
` `
` ;}}}`
`+`
`+`
`+;{{{ pipeline`
`+`
`+;; (defmacro pipeline`
`+;;   "Meant to facilitate long map filter reduce pipelines, especially`
`+;; indentation and unncessary nesting.  Each keyword is changed into a`
`+;; call to the function of the same name with the two arguments, 1 next`
`+;; item in the macro body and the result of pipeline applied recursively`
`+;; to the rest of the body."`
`+;;   [& body]`
`+;;   (let [one (and body (first body))`
`+;;         two (and body (rest body) (frest body))`
`+;;         three (and body (rest body) (rrest body))]`
`+;;     (if (keyword? one)`
`+;;       (if (nil? two)                    ;Or maybe I could check to see if two is keyword?`
`+;;           (list (symbol (name one))`
`+;;                 `(pipeline ~@three))`
`+;;         (list (symbol (name one))`
`+;;               two`
`+;;               `(pipeline ~@three)))`
`+;;       `(do ~@body))))`
`+`
`+`
`+(defmacro pipeline`
`+  "Meant to facilitate long map filter reduce pipelines, especially`
`+indentation and unncessary nesting.  Each keyword is changed into a`
`+call to the function of the same name with the two arguments, 1 next`
`+item in the macro body and the result of pipeline applied recursively`
`+to the rest of the body."`
`+  [& body]`
`+  (if (keyword? (and body (first body)))`
`+    (let [pieces (split-with (complement keyword?) (rest body))]`
`+      (if (zero? (count (pieces 1)))`
`+          `(~(symbol (name (first body))) ~@(pieces 0))`
`+        `(~(symbol (name (first body))) ~@(pieces 0) (pipeline ~@(pieces 1)))))`
`+    `(do ~@body)))`
`+;}}}`
`+`
`+`
` ;{{{ problem 66 -- Diaphontine equations *`
` `
` ;; Consider quadratic Diophantine equations of the form:`
` `
` ;; x^2 - Dy^2 = 1`
` `
`-;; For example, when D=13, the minimal solution in x is 6492 - 131802 = 1.`
`+;; For example, when D=13, the minimal solution in x is 649^2 - 13*180^2 = 1.`
` `
` ;; It can be assumed that there are no solutions in positive integers`
` ;; when D is square.`
` ;; Find the value of D <= 1000 in minimal solutions of x for which the`
` ;; largest value of x is obtained.`
` `
`+(defn first-intersection [seq1 seq2]`
`+  (cond (< (first seq1) (first seq2))`
`+          (recur (rest seq1) seq2)`
`+        (> (first seq1) (first seq2))`
`+          (recur seq1 (rest seq2))`
`+        :else ;; they must be equal`
`+          (first seq1)))`
`+`
`+(defn minimum-x-with-solution-2 [D]`
`+  (list`
`+   (first-intersection (map #(* % %) (iterate inc 1))`
`+                       (map #(+ 1 (* D % %))`
`+                            (iterate inc 1)))`
`+   D))`
`+`
`+`
`+;; (/ (- (* x x) 1) D)                     ;; must be square so`
`+`
`+`
`+(defn no-solution-for [y]`
`+  (fn [D]`
`+    (not (is-square? (+ 1 (* D y y))))))`
`+`
`+(defn minimum-D`
`+  ([n] (minimum-D 1`
`+                  (filter (complement is-square?)`
`+                          (range 2 (inc n)))))`
`+  ([y seq]`
`+     (if (= 1 (count seq))`
`+    (first seq)`
`+    (recur (inc y)`
`+           (filter (no-solution-for y) seq)))))`
`+`
`+;; (time (minimum-D 1000))`
`+;;`
`+`
`+(defn minimum-x-with-solution [D]`
`+  (list`
`+   (pipeline`
`+     :first`
`+     :filter is-square?`
`+     :map #(+ 1 (* D % %))`
`+     (iterate inc 1))`
`+   D))`
`+`
`+(defn minimal-diaphontine-x [n]`
`+  (pipeline`
`+    :frest`
`+    :reduce max-first`
`+    :map minimum-x-with-solution`
`+    :filter (complement is-square?)`
`+    (range (inc n))))`
`+`
`+;; (time (minimal-diaphontine-x 100))`
`+;; "Elapsed time: 256626.027 msecs"`
`+;; 61`
`+`
`+`
`+`
`+`
`+(defn largest-factor [D]`
`+  (reduce max 1`
`+          (pipeline`
`+            :map #(big-integer-pow (first %) (frest %))`
`+            :filter #(and (not (nil? (first %)))`
`+                          (not= 2 (first %)))`
`+            (run-length-encode (factors D)))))`
`+`
`+`
`+(defn minimum-x-with-solution [D]`
`+  (let [incrementer (largest-factor D)]`
`+    (list`
`+     (take 2`
`+`
`+           (for [xx (take-while #(< % 100) (iterate #(+ incrementer %) 1))]`
`+             (do ;(prn D incrementer xx (/ (* xx (+ xx 2)) D) (/ (* xx (- xx 2)) D))`
`+;;                (prn xx (/ (* xx (+ xx 2)) D) (/ (* xx (- xx 2)) D))`
`+               (cond (is-square? (/ (* xx (+ xx 2)) D))`
`+                       (list (inc xx) D)`
`+                     (is-square? (/ (* xx (- xx 2)) D))`
`+                       (list (dec xx) D)`
`+                     :else`
`+                     nil))))`
`+     D)))`
`+`
`+`
`+`
`+(defn minimum-x-with-solution [D]`
`+  (let [incrementer (largest-factor D)]`
`+    (pipeline :first`
`+              :filter (complement nil?)`
`+              :map #(cond (is-square? (/ (* % (+ % 2)) D))`
`+                            (list (inc %) D)`
`+                          (is-square? (/ (* % (- % 2)) D))`
`+                            (list (dec %) D)`
`+                          :else`
`+                            nil)`
`+              (iterate #(+ incrementer %) incrementer))))`
`+`
`+`
`+;; (map largest-factor )`
`+(defn minimal-diaphontine-x [n]`
`+  (pipeline`
`+`
`+;;     :frest nil`
`+;;     :reduce max-first`
`+`
`+;;     :reverse nil`
`+;;     :sort-by first`
`+`
`+    :map minimum-x-with-solution`
`+    :filter (complement is-square?)`
`+    (range (inc n))))`
`+`
`+;; (time (minimal-diaphontine-x 100))`
`+;; "Elapsed time: 256626.027 msecs"`
`+;; "Elapsed time:  45649.972 msecs"`
`+;; 61`
`+`
`+`
` ;}}}`
` ;{{{ problem 67 -- more triangle path maximizing`
` `
` ;; It is possible to complete the ring with four different totals: 9`
` ;; 10, 11, and 12. There are eight solutions in total.`
` `
`-;; Total	Solution Set`
`-;; 9	4,2,3; 5,3,1; 6,1,2`
`-;; 9	4,3,2; 6,2,1; 5,1,3`
`-;; 10	2,3,5; 4,5,1; 6,1,3`
`-;; 10	2,5,3; 6,3,1; 4,1,5`
`-;; 11	1,4,6; 3,6,2; 5,2,4`
`-;; 11	1,6,4; 5,4,2; 3,2,6`
`-;; 12	1,5,6; 2,6,4; 3,4,5`
`-;; 12	1,6,5; 3,5,4; 2,4,6`
`+;; Total Solution Set`
`+;; 9    4,2,3; 5,3,1; 6,1,2`
`+;; 9    4,3,2; 6,2,1; 5,1,3`
`+;; 10   2,3,5; 4,5,1; 6,1,3`
`+;; 10   2,5,3; 6,3,1; 4,1,5`
`+;; 11   1,4,6; 3,6,2; 5,2,4`
`+;; 11   1,6,4; 5,4,2; 3,2,6`
`+;; 12   1,5,6; 2,6,4; 3,4,5`
`+;; 12   1,6,5; 3,5,4; 2,4,6`
` `
` ;; By concatenating each group it is possible to form 9-digit strings;`
` ;; the maximum string for a 3-gon ring is 432621513.`
` `
` ;}}}`
` `
`-(defmacro pipeline`
`-  "Meant to facilitate long map filter reduce pipelines, especially`
`-indentation and unncessary nesting.  Each keyword is changed into a`
`-call to the function of the same name with the two arguments, 1 next`
`-item in the macro body and the result of pipeline applied recursively`
`-to the rest of the body."`
`-  [& body]`
`-  (let [one (and body (first body))`
`-        two (and body (rest body) (frest body))`
`-        three (and body (rest body) (rrest body))]`
`-    (if (keyword? one)`
`-      (if (nil? two)                    ;Or maybe I could check to see if two is keyword?`
`-          (list (symbol (name one))`
`-                `(pipeline ~@three))`
`-        (list (symbol (name one))`
`-              two`
`-              `(pipeline ~@three)))`
`-      `(do ~@body))))`
`-`
`-`
`+;{{{ problem 71 -- ordering fractions`
`+`
`+;; Consider the fraction, n/d, where n and d are positive integers. If`
`+;; nd and HCF(n,d)=1, it is called a reduced proper fraction.`
`+`
`+;; If we list the set of reduced proper fractions for d <= 8 in ascending`
`+;; order of size, we get:`
`+`
`+;; 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5`
`+;; 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8`
`+`
`+;; It can be seen that 2/5 is the fraction immediately to the left of 3/7.`
`+`
`+;; By listing the set of reduced proper fractions for d <= 1,000,000`
`+;; in ascending order of size, find the numerator of the fraction`
`+;; immediately to the left of 3/7.`
`+`
`+(defn next-smallest-fraction [a b d]`
`+  (- (/ a b)`
`+     (/ (inc (rem (dec (* a d)) b))`
`+        (* b d))))`
`+`
`+(defn next-smallest-fraction-in-range [frac n]`
`+  (let [a (. frac numerator)`
`+        b (. frac denominator)]`
`+    (pipeline`
`+      :reduce max`
`+      :map #(next-smallest-fraction a b %)`
`+      (range 2 (inc n)))))`
`+`
`+;; (next-smallest-fraction-in-range 3/7 1000000)`
`+;; 428570/999997`
`+`
`+;}}}`
`+;{{{ problem 72 -- number of reduced fractions`
`+`
`+;; Consider the fraction, n/d, where n and d are positive integers. If`
`+;; nd and HCF(n,d)=1, it is called a reduced proper fraction.`
`+`
`+;; If we list the set of reduced proper fractions for d <= 8 in ascending`
`+;; order of size, we get:`
`+`
`+;; 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5`
`+;; 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8`
`+`
`+;; It can be seen that there are 21 elements in this set.`
`+`
`+;; How many elements would be contained in the set of reduced proper`
`+;; fractions for d <= 1,000,000?`
`+`
`+(defn num-fractions [n]`
`+  (pipeline`
`+  :reduce +`
`+  :map totient`
`+  (range 2 (inc n))))`
`+`
`+;; (num-fractions 1000000)`
`+;; 303963552391`
`+`
`+;}}}`
`+;{{{ problem 73 -- number of reduced fractions`
`+`
`+;; Consider the fraction, n/d, where n and d are positive integers. If`
`+;; n/d and HCF(n,d)=1, it is called a reduced proper fraction.`
`+`
`+;; If we list the set of reduced proper fractions for d <= 8 in ascending`
`+;; order of size, we get:`
`+`
`+;; 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, **1/3, 3/8, 2/5, 3/7, 1/2**, 4/7, 3/5`
`+;; 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8`
`+`
`+;; It can be seen that there are 3 fractions between 1/3 and 1/2.`
`+`
`+;; How many fractions lie between 1/3 and 1/2 in the sorted set of`
`+;; reduced proper fractions for d <= 10,000?`
`+`
`+(defn next-smallest-numerator [a b d]`
`+  (let [x (dec (* a d))]`
`+    (/ (- x (rem x b)) b)))`
`+`
`+(defn next-largest-numerator [a b d]`
`+  (let [x (* a d)]`
`+    (inc (/ (- x (rem x b)) b))))`
`+`
`+(defn reduced-fractions-between [d]`
`+  (pipeline`
`+    :count`
`+    :filter #(= 1 (gcd d %))`
`+    (range (next-largest-numerator 1 3 d)`
`+           (inc (next-smallest-numerator 1 2 d)))))`
`+`
`+(defn fractions-between [d]`
`+  (pipeline`
`+    :reduce +`
`+    :map reduced-fractions-between`
`+    (range 2 (inc d))))`
`+`
`+;; (time (fractions-between 10000))`
`+;; "Elapsed time: 5036.473 msecs"`
`+;; 5066251`
`+`
`+;}}}`
`+;{{{ problem 74 -- sum of factorials of digits`
`+`
`+;; The number 145 is well known for the property that the sum of the`
`+;; factorial of its digits is equal to 145:`
`+`
`+;; 1! + 4! + 5! = 1 + 24 + 120 = 145`
`+`
`+;; Perhaps less well known is 169, in that it produces the longest`
`+;; chain of numbers that link back to 169; it turns out that there are`
`+;; only three such loops that exist:`
`+`
`+;; 169  363601  1454  169`
`+;; 871  45361  871`
`+;; 872  45362  872`
`+`
`+;; It is not difficult to prove that EVERY starting number will`
`+;; eventually get stuck in a loop. For example`
`+`
`+;; 69  363600  1454  169  363601 ( 1454)`
`+;; 78  45360  871  45361 ( 871)`
`+;; 540  145 ( 145)`
`+`
`+;; Starting with 69 produces a chain of five non-repeating terms, but`
`+;; the longest non-repeating chain with a starting number below one`
`+;; million is sixty terms.`
`+`
`+;; How many chains, with a starting number below one million, contain`
`+;; exactly sixty non-repeating terms?`
`+`
`+(defn sum-of-factorials-of-digits [n]`
`+  (reduce + (map factorial (to-digits n))))`
`+`
`+(defn member? [elt seq]`
`+  (contains? (zipmap seq seq) elt))`
`+`
`+(defn chain [item fn-or-map]`
`+  ((fn this [item accum]`
`+     (let [next (fn-or-map item)]`
`+       (if (member? next accum)`
`+           accum`
`+         (recur next (cons next accum)))))`
`+   item (list item)))`
`+`
`+(defn chain-length [item fn-or-map]`
`+  (count (chain item fn-or-map)))`
`+`
`+(defn find-chains-of-length-less-than [x n]`
`+  (pipeline`
`+    :count`
`+    :filter #(= x %)`
`+    :map #(chain-length % sum-of-factorials-of-digits)`
`+    (range n)))`
`+`
`+;; (time (find-chains-of-length-less-than 60 1000000))`
`+;; "Elapsed time: 545063.311 msecs"`
`+;; 402`
`+`
`+;}}}`
`+`
`+;{{{ problem 75 -- wire right triangles`
`+`
`+;; It turns out that 12 cm is the smallest length of wire that can be`
`+;; bent to form an integer sided right angle triangle in exactly one`
`+;; way, but there are many more examples.`
`+`
`+;; 12 cm: (3,4,5)`
`+;; 24 cm: (6,8,10)`
`+;; 30 cm: (5,12,13)`
`+;; 36 cm: (9,12,15)`
`+;; 40 cm: (8,15,17)`
`+;; 48 cm: (12,16,20)`
`+`
`+;; In contrast, some lengths of wire, like 20 cm, cannot be bent to`
`+;; form an integer sided right angle triangle, and other lengths allow`
`+;; more than one solution to be found; for example, using 120 cm it is`
`+;; possible to form exactly three different integer sided right angle`
`+;; triangles.`
`+`
`+;; 120 cm: (30,40,50), (20,48,52), (24,45,51)`
`+`
`+;; Given that L is the length of the wire, for how many values of L <=`
`+;; 2,000,000 can exactly one integer sided right angle triangle be`
`+;; formed?`
`+`
`+`
`+;; TOO SLOW!`
`+;; (defn pythagorean-triples [n]`
`+;;   ;; (count-uniq seq)`
`+;;   (count`
`+;;    (filter #(= 1 (frest %))`
`+;;            (run-length-encode`
`+;;             (sort (filter #(<= % n)`
`+;;                           (for [x (iterate inc 1) :while (< x n)`
`+;;                                 y (iterate inc 1) :while (and (<= y x)`
`+;;                                                               (<= (+ x y) n))`
`+;;                                                   :when (is-square? (+ (* x x) (* y y)))]`
`+;;                             (+ x y (Math/round (Math/sqrt (+ (* x x) (* y y))))))))))))`
`+`
`+;; I cheated on this one: http://en.wikipedia.org/wiki/Pythagorean_triple`
`+(defn primitive-pythagorean-triples-below [max]`
`+  (sort (for [m (range 1 max) ;; this could be improved...`
`+              n (range 1 m)`
`+              :while (<= (* 2 m (+ m n)) max)`
`+              :when (and (= 1 (gcd m n))`
`+                         (= 1 (+ (rem m 2)`
`+                                 (rem n 2))))`
`+              ]`
`+          ;;     (+ (* 2 m n) (* 2 m m))`
`+          (* 2 m (+ m n)))))`
`+`
`+(defn multiples-below [n max]`
`+  (take-while #(<= % max)`
`+              (iterate #(+ % n) n)))`
`+`
`+(defn run-length-encode-no-recur [seq]`
`+  ((fn [seq accum]`
`+    (if (or (nil? seq)`
`+            (nil? (first seq)))`
`+      (reverse accum)`
`+      (let [f (first seq)`
`+            cnt (count-uniq seq)]`
`+        (recur (nthrest seq cnt) (list* (list f cnt) accum)))))`
`+   seq (list)))`
`+`
`+(defn pythagorean-triples [n]`
`+  ;; (count-uniq seq)`
`+  (pipeline`
`+    :count`
`+    :filter #(= 1 (frest %))`
`+    :run-length-encode-no-recur`
`+    :sort`
`+    (mapcat #(multiples-below % n)`
`+            (primitive-pythagorean-triples-below n))))`
`+`
`+;; (time (pythagorean-triples 2000000))`
`+;; "Elapsed time: 7997.541 msecs"`
`+;; 214954`
`+`
`+;}}}`
`+;{{{ problem 76 -- partitions`
`+`
`+;; It is possible to write five as a sum in exactly six different`
`+;; ways:`
`+`
`+;; 4 + 1`
`+;; 3 + 2`
`+;; 3 + 1 + 1`
`+;; 2 + 2 + 1`
`+;; 2 + 1 + 1 + 1`
`+;; 1 + 1 + 1 + 1 + 1`
`+`
`+;; How many different ways can one hundred be written as a sum of at`
`+;; least two positive integers?`
`+`
`+(defn partitions [n]`
`+  ((fn this[n max]`
`+     (cond (zero? n)`
`+             (list (list))`
`+           (< n 0)`
`+             nil`
`+           (= n 1)`
`+             (list (list n))`
`+           (= max 1)`
`+             (list (replicate max 1))`
`+           :else`
`+             (reduce concat (for [x (range 1 (inc max))]`
`+                             (map #(cons x %)`
`+                                  (this (- n x) x))))))`
`+   n n))`
`+`
`+;; (defn num-partitions [n]`
`+;;   (count (partitions n)))`
`+`
`+(def num-partitions-helper`
`+  (memoize`
`+   (fn [n max]`
`+     (cond (< n 0)`
`+           0`
`+           (or (zero? n)`
`+               (= n 1)`
`+               (= max 1))`
`+           1`
`+           :else`
`+           (reduce + (for [x (range 1 (inc max))]`
`+                       (num-partitions-helper (- n x) x)))))))`
`+`
`+(defn num-partitions [n]`
`+  (num-partitions-helper n n))`
`+`
`+;; (defn num-partitions [n]`
`+;;   ((fn this[n max]`
`+;;      (cond (< n 0)`
`+;;            0`
`+;;            (or (zero? n)`
`+;;                (= n 1)`
`+;;                (= max 1))`
`+;;            1`
`+;;            :else`
`+;;            (reduce + (for [x (range 1 (inc max))]`
`+;;                        (this (- n x) x)))))`
`+;;    n n))`
`+`
`+;; (time (dec (num-partitions 100)))`
`+;; "Elapsed time: 152553.962 msecs"`
`+;; 190569291`
`+`
`+;}}}`
`+;{{{ problem 77 -- prime partitions`
`+`
`+;; It is possible to write ten as the sum of primes in exactly five`
`+;; different ways:`
`+`
`+;; 7 + 3`
`+;; 5 + 5`
`+;; 5 + 3 + 2`
`+;; 3 + 3 + 2 + 2`
`+;; 2 + 2 + 2 + 2 + 2`
`+`
`+;; What is the first value which can be written as the sum of primes`
`+;; in over five thousand different ways?`
`+`
`+(defn prime-partitions [n]`
`+  ((fn this[n max]`
`+     (cond (zero? n)`
`+             (list (list))`
`+           (and (= n 2) (= n 3))`
`+             (list (list n))`
`+           (or (= n 1) (< n 0))         ;the second should never happen`
`+             nil`
`+           :else`
`+             (apply concat (for [x (primes-below (inc max))]`
`+               (map #(cons x %)`
`+                    (this (- n x) x))))))`
`+   n n))`
`+`
`+(defn find-prime-partitions [n]`
`+  (pipeline`
`+    :first`
`+    :filter #(>= (first %) n)`
`+    :map #(list (count (prime-partitions %)) %)`
`+    (iterate inc 1)))`
`+`
`+;; (time (find-prime-partitions 5000))`
`+;; "Elapsed time: 1272.905 msecs"`
`+;; (5007 71)`
`+`
`+;}}}`
`+;{{{ problem 78 -- number of partitions divisible by 1,000,000`
`+`
`+;; Let p(n) represent the number of different ways in which n coins`
`+;; can be separated into piles. For example, five coins can separated`
`+;; into piles in exactly seven different ways, so p(5)=7.`
`+`
`+;; OOOOO`
`+;; OOOO   O`
`+;; OOO   OO`
`+;; OOO   O   O`
`+;; OO   OO   O`
`+;; OO   O   O   O`
`+;; O   O   O   O   O`
`+`
`+;; Find the least value of n for which p(n) is divisible by one million.`
`+`
`+;; Cheated on this one: http://home.att.net/~numericana/answer/numbers.htm#partitions`
`+;; linked to from http://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function`
`+(def partition-number`
`+  (memoize`
`+   (fn [i]`
`+     (if (<= i 1)`
`+       1`
`+       ;;     :else`
`+       (let [signs (iterate #(- %) 1)`
`+             t1 (reduce +`
`+                        (map * signs`
`+                             (map partition-number`
`+                                  (take-while #(>= % 0)`
`+                                              (map #(- i (/ (+ (* 3 % %) %) 2)) (iterate inc 1)))))`
`+                        )`
`+             t2 (reduce +`
`+                        (map * signs`
`+                             (map partition-number`
`+                                  (take-while #(>= % 0)`
`+                                              (map #(- i (/ (- (* 3 % %) %) 2)) (iterate inc 1)))))`
`+                        )`
`+             ]`
`+         (+ t1 t2))))))`
`+`
`+;; (defn find-big-partitions [n]`
`+;;   (pipeline`
`+;;     :first`
`+;;     :filter #(zero? (rem (frest %) n))`
`+;;     :map #(list % (partition-number %))`
`+;;     (iterate inc 1)))`
`+`
`+(defn find-big-partitions [n]`
`+  (first (for [x (iterate inc 1) :when (zero? (rem (partition-number x) n))]`
`+           x)))`
`+`
`+;; (time (find-big-partitions 2000000))`
`+;; "Elapsed time: 44583.063 msecs"`
`+;; 55374`
`+`
`+;}}}`
`+;{{{ problem 79 -- shortest possible password *`
`+`
`+;; A common security method used for online banking is to ask the user`
`+;; for three random characters from a passcode. For example, if the`
`+;; passcode was 531278, they may asked for the 2nd, 3rd, and 5th`
`+;; characters; the expected reply would be: 317.`
`+`
`+;; The text file, keylog.txt, contains fifty successful login attempts.`
`+`
`+;; Given that the three characters are always asked for in order`
`+;; analyse the file so as to determine the shortest possible secret`
`+;; passcode of unknown length.`
`+`
`+`
`+;}}}`
`+;{{{ problem 80 -- square root sums *`
`+`
`+;; It is well known that if the square root of a natural number is not`
`+;; an integer, then it is irrational. The decimal expansion of such`
`+;; square roots is infinite without any repeating pattern at all.`
`+`
`+;; The square root of two is 1.41421356237309504880..., and the`
`+;; digital sum of the first one hundred decimal digits is 475.`
`+`
`+;; For the first one hundred natural numbers, find the total of the`
`+;; digital sums of the first one hundred decimal digits for all the`
`+;; irrational square roots.`
`+`
`+(defn square-root-sum [n digits]`
`+  )`
`+`
`+`
`+(defn bob [n]`
`+  (pipeline`
`+    :map #(square-root-sum % 100)`
`+    :filter (complement is-square?)`
`+    (range 1 (inc n))))`
`+`
`+;}}}`
`+`
`+;{{{ problem 81 -- minimal path -- down, right *`
`+`
`+;; In the 5 by 5 matrix below, the minimal path sum from the top left`
`+;; to the bottom right, by only moving to the right and down, is`
`+;; indicated in red and is equal to 2427.`
`+`
`+;; 131 673 234 103 18`
`+;; 201 96  342 965 150`
`+;; 630 803 746 422 111`
`+;; 537 699 497 121 956`
`+;; 805 732 524 37  331`
`+`
`+;; Find the minimal path sum, in matrix.txt (right click and 'Save`
`+;; Link/Target As...'), a 31K text file containing a 80 by 80 matrix`
`+;; from the top left to the bottom right by only moving right and`
`+;; down.`
`+`
`+(defn read-matrix [file]`
`+  (map #(re-seq #"[0-9]+" %)`
`+       (re-seq #".+" (slurp file))))`
`+`
`+(def matrix (read-matrix "matrix.txt"))`
`+`
`+(def small-matrix`
`+     (131 673 234 103 18)`
`+     (201 96  342 965 150)`
`+     (630 803 746 422 111)`
`+     (537 699 497 121 956)`
`+     (805 732 524 37  331)`
`+)`
`+`
`+(defn get-row [matrix n]`
`+  (nth matrix n))`
`+`
`+(defn get-column [matrix n]`
`+  (map #(nth % n) matrix))`
`+`
`+`
`+`
`+;}}}`
`+;{{{ problem 82 -- minimal path -- up, down, right *`
`+`
`+;; NOTE: This problem is a more challenging version of Problem 81.`
`+`
`+;; The minimal path sum in the 5 by 5 matrix below, by starting in any`
`+;; cell in the left column and finishing in any cell in the right`
`+;; column, and only moving up, down, and right, is indicated in red;`
`+;; the sum is equal to 994.`
`+`
`+;; 131  673 234 103 18`
`+;; 201  96  342 965 150`
`+;; 630  803 746 422 111`
`+;; 537  699 497 121 956`
`+;; 805  732 524 37  331`
`+`
`+;; Find the minimal path sum, in matrix.txt (right click and 'Save`
`+;; Link/Target As...'), a 31K text file containing a 80 by 80 matrix`
`+;; from the left column to the right column.`
`+`
`+;}}}`
`+;{{{ problem 83 -- minimal path -- up, down, left, right *`
`+`
`+;; NOTE: This problem is a significantly more challenging version of`
`+;; Problem 81.`
`+`
`+;; In the 5 by 5 matrix below, the minimal path sum from the top left`
`+;; to the bottom right, by moving left, right, up, and down, is`
`+;; indicated in red and is equal to 2297.`
`+`
`+;; 131  673 234 103 18`
`+;; 201  96  342 965 150`
`+;; 630  803 746 422 111`
`+;; 537  699 497 121 956`
`+;; 805  732 524 37  331`
`+`
`+;; Find the minimal path sum, in matrix.txt (right click and 'Save`
`+;; Link/Target As...'), a 31K text file containing a 80 by 80 matrix`
`+;; from the top left to the bottom right by moving left, right, up`
`+;; and down.`
`+`
`+;}}}`
`+;{{{ problem 84 -- monopoly probabilities *`
`+`
`+;; In the game, Monopoly, the standard board is set up in the following way:`
`+`
`+;; GO  A1  CC1  A2  T1  R1  B1  CH1  B2  B3  JAIL`
`+;; H2                                        C1`
`+;; T2                                        U1`
`+;; H1                                        C2`
`+;; CH3                                       C3`
`+;; R4                                        R2`
`+;; G3                                        D1`
`+;; CC3                                       CC2`
`+;; G2                                        D2`
`+;; G1                                        D3`
`+;; G2J  F3  U2  F2  F1  R3  E3  E2  CH2  E1  FP`
`+`
`+;; A player starts on the GO square and adds the scores on two 6-sided`
`+;; dice to determine the number of squares they advance in a clockwise`
`+;; direction. Without any further rules we would expect to visit each`
`+;; square with equal probability: 2.5%. However, landing on G2J (Go To`
`+;; Jail), CC (community chest), and CH (chance) changes this`
`+;; distribution.`
`+`
`+;; In addition to G2J, and one card from each of CC and CH, that`
`+;; orders the player to go to directly jail, if a player rolls three`
`+;; consecutive doubles, they do not advance the result of their 3rd`
`+;; roll. Instead they proceed directly to jail.`
`+`
`+;; At the beginning of the game, the CC and CH cards are`
`+;; shuffled. When a player lands on CC or CH they take a card from the`
`+;; top of the respective pile and, after following the instructions`
`+;; it is returned to the bottom of the pile. There are sixteen cards`
`+;; in each pile, but for the purpose of this problem we are only`
`+;; concerned with cards that order a movement; any instruction not`
`+;; concerned with movement will be ignored and the player will remain`
`+;; on the CC/CH square.`
`+`
`+;; Community Chest (2/16 cards):`
`+;; Advance to GO`
`+;; Go to JAIL`
`+;; Chance (10/16 cards):`
`+;; Advance to GO`
`+;; Go to JAIL`
`+;; Go to C1`
`+;; Go to E3`
`+;; Go to H2`
`+;; Go to R1`
`+;; Go to next R (railway company)`
`+;; Go to next R`
`+;; Go to next U (utility company)`
`+;; Go back 3 squares.`
`+`
`+;; The heart of this problem concerns the likelihood of visiting a`
`+;; particular square. That is, the probability of finishing at that`
`+;; square after a roll. For this reason it should be clear that, with`
`+;; the exception of G2J for which the probability of finishing on it`
`+;; is zero, the CH squares will have the lowest probabilities, as 5/8`
`+;; request a movement to another square, and it is the final square`
`+;; that the player finishes at on each roll that we are interested`
`+;; in. We shall make no distinction between "Just Visiting" and being`
`+;; sent to JAIL, and we shall also ignore the rule about requiring a`
`+;; double to "get out of jail", assuming that they pay to get out on`
`+;; their next turn.`
`+`
`+;; By starting at GO and numbering the squares sequentially from 00 to`
`+;; 39 we can concatenate these two-digit numbers to produce strings`
`+;; that correspond with sets of squares.`
`+`
`+;; Statistically it can be shown that the three most popular squares`
`+;; in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and`
`+;; GO (3.09%) = Square 00. So these three most popular squares can be`
`+;; listed with the six-digit modal string: 102400.`
`+`
`+;; If, instead of using two 6-sided dice, two 4-sided dice are used`
`+;; find the six-digit modal string.`
`+`
`+;}}}`
`+;{{{ problem 85 -- number of rectangles **`
`+`
`+;; 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.`
`+`
`+(defn num-rectangles [a b]`
`+  (reduce + (for [x (range 1 (inc a))`
`+                  y (range 1 (inc b))]`
`+              (* x y))))`
`+`
`+(defn find-big-retangles [n num]`
`+  (pipeline`
`+;;     :frest`
`+    :reduce min-first`
`+    :take num`
`+    (for [a (iterate inc 1)`
`+          b (range 1 (inc a))]`
`+      (list (abs (- n (num-rectangles a b))) (* a b)))))`
`+`
`+;; (time (find-big-retangles 2000000 3000))`
`+;; "Elapsed time: 25365.739 msecs"`
`+;; (2 2772)`
`+`
`+;}}}`
`+`
`+;{{{ problem 86 -- cuboid path *`
`+`
`+;; A spider, S, sits in one corner of a cuboid room, measuring 6 by 5`
`+;; by 3, and a fly, F, sits in the opposite corner. By travelling on`
`+;; the surfaces of the room the shortest "straight line" distance from`
`+;; S to F is 10 and the path is shown on the diagram.`
`+`
`+;; However, there are up to three "shortest" path candidates for any`
`+;; given cuboid and the shortest route is not always integer.`
`+`
`+;; By considering all cuboid rooms up to a maximum size of M by M by`
`+;; M, there are exactly 2060 cuboids for which the shortest distance`
`+;; is integer when M=100, and this is the least value of M for which`
`+;; the number of solutions first exceeds two thousand; the number of`
`+;; solutions is 1975 when M=99.`
`+`
`+;; Find the least value of M such that the number of solutions first`
`+;; exceeds one million.`
`+`
`+`
`+`
`+;}}}`
`+;{{{ problem 87 -- prime square, cube and fourth power *`
`+`
`+;; The smallest number expressible as the sum of a prime square, prime`
`+;; cube, and prime fourth power is 28. In fact, there are exactly four`
`+;; numbers below fifty that can be expressed in such a way:`
`+`
`+;; 28 = 2^2 + 2^3 + 2^4`
`+;; 33 = 3^2 + 2^3 + 2^4`
`+;; 49 = 5^2 + 2^3 + 2^4`
`+;; 47 = 2^2 + 3^3 + 2^4`
`+;; How many numbers below fifty million can be expressed as the sum of`
`+;; a prime square, prime cube, and prime fourth power?`
`+`
`+;}}}`
`+;{{{ problem 88 -- minimal product sum *`
`+`
`+;; A natural number, N, that can be written as the sum and product of`
`+;; a given set of at least two natural numbers, {a1, a2, ... , ak} is`
`+;; called a product-sum number: N = a1 + a2 + ... + ak = a1 a2 ... ak.`
`+`
`+;; For example, 6 = 1 + 2 + 3 = 1  2  3.`
`+`
`+;; For a given set of size, k, we shall call the smallest N with this`
`+;; property a minimal product-sum number. The minimal product-sum`
`+;; numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.`
`+`
`+;; k=2: 4 = 2  2 = 2 + 2`
`+;; k=3: 6 = 1  2  3 = 1 + 2 + 3`
`+;; k=4: 8 = 1  1  2  4 = 1 + 1 + 2 + 4`
`+;; k=5: 8 = 1  1  2  2  2 = 1 + 1 + 2 + 2 + 2`
`+;; k=6: 12 = 1  1  1  1  2  6 = 1 + 1 + 1 + 1 + 2 + 6`
`+`
`+;; Hence for 2 <= k <= 6, the sum of all the minimal product-sum`
`+;; numbers is 4+6+8+12 = 30; note that 8 is only counted once in the`
`+;; sum.`
`+`
`+;; In fact, as the complete set of minimal product-sum numbers for`
`+;; 2 <= k <= 12 is {4, 6, 8, 12, 15, 16}, the sum is 61.`
`+`
`+;; What is the sum of all the minimal product-sum numbers for 2 <= k <= 12000?`
`+`
`+;}}}`
`+;{{{ problem 89 -- roman numerals in minimal form **`
`+`
`+;; The rules for writing Roman numerals allow for many ways of writing`
`+;; each number (see FAQ: Roman Numerals). However, there is always a`
`+;; "best" way of writing a particular number.`
`+`
`+;; For example, the following represent all of the legitimate ways of`
`+;; writing the number sixteen:`
`+`
`+;; IIIIIIIIIIIIIIII`
`+;; VIIIIIIIIIII`
`+;; VVIIIIII`
`+;; XIIIIII`
`+;; VVVI`
`+;; XVI`
`+`
`+;; The last example being considered the most efficient, as it uses`
`+;; the least number of numerals.`
`+`
`+;; The 11K text file, roman.txt (right click and 'Save Link/Target`
`+;; As...'), contains one thousand numbers written in valid, but not`
`+;; necessarily minimal, Roman numerals; that is, they are arranged in`
`+ ;; descending units and obey the subtractive pair rule (see FAQ for`
`+;; the definitive rules for this problem).`
`+`
`+;; Find the number of characters saved by writing each of these in`
`+;; their minimal form.`
`+`
`+;; Note: You can assume that all the Roman numerals in the file`
`+;; contain no more than four consecutive identical units.`
`+`
`+;; {{{ FAQ:`
`+`
`+;; Traditional Roman numerals are made up of the following denominations:`
`+`
`+;; I = 1`
`+;; V = 5`
`+;; X = 10`
`+;; L = 50`
`+;; C = 100`
`+;; D = 500`
`+;; M = 1000`
`+`
`+;; You will read about many different rules concerning Roman numerals`
`+;; but the truth is that the Romans only had one simple rule:`
`+`
`+;; Numerals must be arranged in descending order of size.`
`+`
`+;; For example, three ways that sixteen could be written are XVI`
`+;; XIIIIII, VVVI; the first being the preferred form as it uses the`
`+;; least number of numerals.`
`+`
`+;; The "descending size" rule was introduced to allow the use of`
`+;; subtractive combinations. For example, four can be written IV`
`+;; because it is one before five. As the rule requires that the`
`+;; numerals be arranged in order of size it should be clear to a`
`+;; reader that the presence of a smaller numeral out of place, so to`
`+;; speak, was unambiguously to be subtracted from the following`
`+;; numeral. For example, nineteen could be written XIX = X + IX`
`+;; (9). Note also how the rule requires X (ten) be placed before IX`
`+;; (nine), and IXX would not be an acceptable configuration.`
`+`
`+;; Generally the Romans tried to use as few numerals as possible when`
`+;; displaying numbers. For this reason, XIX would be the preferred`
`+;; form of nineteen over other valid combinations, like XVIIII or`
`+;; XVIV. However, this was NOT a rule and there still remain in Rome`
`+;; many examples where economy of numerals has not been employed. For`
`+;; example, in the famous Colesseum the the numerals above the`
`+;; forty-ninth entrance is written XXXXVIIII and not IL nor XLIX (see`
`+;; rules below).`
`+`
`+;; Despite this, over time we have continued to introduce new`
`+;; restrictive rules. By mediaeval times it had become standard`
`+;; practice to avoid more than three consecutive identical`
`+;; numerals. That is, IV would be written instead of IIII, IX would be`
`+;; used instead of VIIII, and so on. In addition, the subtractive`
`+;; combinations had the following rules superimposed:`
`+`
`+;; * Only I, X, and C can be used as the leading numeral in part of a subtractive pair.`
`+;; * I can only be placed before V and X.`
`+;; * X can only be placed before L and C.`
`+;; * C can only be placed before D and M.`
`+`
`+;; These last four rules are considered to be law, and generally it is`
`+;; preferred, but not necessary, to display numbers using the minimum`
`+;; number of numerals. Which means that IL is considered an invalid`
`+;; way of writing forty-nine, and whereas XXXXVIIII, XXXXIX, XLVIIII`
`+;; and XLIX are all quite legitimate, the latter is the preferred`
`+;; (minimal) form.`
`+`
`+;; It is also expected that higher denominations should be used`
`+;; whenever possible; for example, L should be used in place of XXXXX`
`+;; or C should be used in place of LL. However, even this "rule" has`
`+;; been flaunted: in the church of Sant'Agnese fuori le Mura (St`
`+;; Agnes' outside the walls), found in Rome, the date, MCCCCCCVI`
`+;; (1606), is written on the gilded and coffered wooden ceiling; I am`
`+;; sure that many would argue that it should have been written MDCVI.`
`+`
`+;; However, if we believe the adage, "when in Rome do as the Romans`
`+;; do," and we see how the Romans write numerals, then it clearly`
`+;; gives us much more freedom than many would care to admit.`
`+`
`+;; }}}`
`+`
`+(defn roman2num [roman]`
`+  ((fn [accum x r]`
`+     (cond (nil? r)`
`+             (+ accum x)`
`+           (and (not= 0 x)`
`+                (< x (first r)))`
`+             (recur (- accum x) (first r) (rest r))`
`+           :else`
`+             (recur (+ accum x) (first r) (rest r))))`
`+   0 0`
`+   (for [letter roman]`
`+     (condp = letter`
`+              \I 1`
`+              \V 5`
`+              \X 10`
`+              \L 50`
`+              \C 100`
`+              \D 500`
`+              \M 1000`
`+              ;; default`
`+              0))))`
`+`
`+(defn romanize-ten [num one five ten]`
`+  (let [r (rem num 5)]`
`+    (if (= r 4)`
`+      (list one (if (> num 5) ten five))`
`+      (concat (if (>= num 5) (list five)) (take r (repeat one))))))`
`+`
`+(defn num2roman [num]`
`+  (concat`
`+   (take (int (quot num 1000)) (repeat \M))`
`+   (romanize-ten (rem (quot num 100) 10) \C \D \M)`
`+   (romanize-ten (rem (quot num 10)  10) \X \L \C)`
`+   (romanize-ten (rem       num      10) \I \V \X)))`
`+`
`+(defn roman-shrink [roman]`
`+;;   (prn roman)`
`+;;   (prn (num2roman (roman2num roman)))`
`+  (- (count roman)`
`+     (count (num2roman (roman2num roman)))))`
`+`
`+(defn roman-savings [file]`
`+  (pipeline`
`+    :reduce +`
`+    :map roman-shrink`
`+    (re-seq #"\w+" (slurp file))))`
`+`
`+;; (time (roman-savings "roman.txt"))`
`+;; "Elapsed time: 98.535 msecs"`
`+;; 743`
`+`
`+;}}}`
`+;{{{ problem 90 -- two cubes to make a square ***`
`+`
`+;; Each of the six faces on a cube has a different digit (0 to 9)`
`+;; written on it; the same is done to a second cube. By placing the`
`+;; two cubes side-by-side in different positions we can form a variety`
`+;; of 2-digit numbers.`
`+`
`+;; For example, the square number 64 could be formed:`
`+`
`+`
`+;; In fact, by carefully choosing the digits on both cubes it is`
`+;; possible to display all of the square numbers below one-hundred:`
`+;; 01, 04, 09, 16, 25, 36, 49, 64, and 81.`
`+`
`+;; For example, one way this can be achieved is by placing {0, 5, 6`
`+;; 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.`
`+`
`+;; However, for this problem we shall allow the 6 or 9 to be turned`
`+;; upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1`
`+;; 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed;`
`+;; otherwise it would be impossible to obtain 09.`
`+`
`+;; In determining a distinct arrangement we are interested in the`
`+;; digits on each cube, not the order.`
`+`
`+;; {1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}`
`+;; {1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}`
`+`
`+;; But because we are allowing 6 and 9 to be reversed, the two`
`+;; distinct sets in the last example both represent the extended set`
`+;; {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.`
`+`
`+;; How many distinct arrangements of the two cubes allow for all of`
`+;; the square numbers to be displayed?`
`+`
`+(def must-create '((0 1) (0 4) (0 6)`
`+                   (1 6) (2 5) (3 6)`
`+                   (4 6) (6 4) (8 1)))`
`+`
`+(defn generate-cubes [seq die1 die2]`
`+;;   (prn seq die1 die2)`
`+  (if seq`
`+    (concat (generate-cubes (rest seq)`
`+                       (map #(cons (ffirst seq) %) die1)`
`+                       (map #(cons (first (rfirst seq)) %) die2))`
`+            (generate-cubes (rest seq)`
`+                       (map #(cons (ffirst seq) %) die2)`
`+                       (map #(cons (first (rfirst seq)) %) die1)))`
`+    (list (list die1 die2))))`
`+`
`+(defn expound-cube [cube]`
`+  (cond (> (count cube) 6)`
`+        nil`
`+        (= (count cube) 6) ; Here I need to check for a six, and if so add one with a nine`
`+        (if (cube 6)`
`+          (list cube (set (cons 9 cube))) ;It's not actually the correct cube, but it's close enough`
`+          (list cube))`
`+        :else`
`+        (apply concat (for [x (range 9) :when (not (cube x))]`
`+                  (expound-cube (set (cons x cube)))))))`
`+`
`+(defn expound-cubes [cubes]`
`+  (let [cube1s (expound-cube (first cubes))`
`+        cube2s (expound-cube (frest cubes))]`
`+    (for [x cube1s`
`+          y cube2s]`
`+      (list x y))))`
`+`
`+(defn num-cubes []`
`+  (pipeline`
`+    :count`
`+    :set`
`+    :mapcat expound-cubes`
`+;;     :filter #(and (<= (count (first %)) 7)`
`+;;                   (<= (count (frest %)) 7))`
`+    :map #(set (list (set (ffirst %))`
`+                     (set (first (frest %)))))`
`+    (generate-cubes must-create '(()) '(()))))`
`+`
`+;; (time (num-cubes))`
`+;; "Elapsed time: 1478.547 msecs"`
`+;; 1066`
`+`
`+;}}}`
`+`
`+`
`+`
`+`
`+`
`+`
`+;; memoize`
`+;; comp f,g,h -> f(g(h(*)))`
`+`