Commits

Anonymous committed 2f269be

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

Comments (0)

Files changed (1)

     (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(*)))
+