1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/rlm/qotd.clj	Wed Jan 18 05:18:57 2012 -0700
     1.3 @@ -0,0 +1,80 @@
     1.4 +(ns rlm.qotd)
     1.5 +(rlm.rlm-commands/help)
     1.6 +
     1.7 +;;;There is a pair of integers, 1 < m < n, whose sum is less
     1.8 +;;;than 100.
     1.9 +
    1.10 +(def pos (fn [a]
    1.11 +           (filter (fn [[a b]] (< a b))
    1.12 +                   (map #(vector % a) (range 1 (- 100 a))))))
    1.13 +
    1.14 +(def p0 (reduce concat (map pos (range 2 99))))
    1.15 +
    1.16 +;;; Person S knows their sum, but nothing else about them.
    1.17 +;;; Person P knows their product, but nothing else about
    1.18 +;;; them.
    1.19 +
    1.20 +;;; Now, Persons S and P know the above information, and each
    1.21 +;;; one knows that the other one knows it. They have the
    1.22 +;;; following conversation:
    1.23 +
    1.24 +;;; P: I can't figure out what the numbers are.
    1.25 +
    1.26 +
    1.27 +
    1.28 +;; Eliminate pairs with a unique product.
    1.29 +
    1.30 +(defn group-by
    1.31 +  "Split coll into groups where the f maps each element in a
    1.32 +  group to the same value in O(n*log(n)) time."
    1.33 +  [f coll]
    1.34 +  (partition-by f (sort-by f coll)))
    1.35 +
    1.36 +(defn unique-by
    1.37 +  "Remove all elements a,b of coll that for which
    1.38 +   (= (f a) (f b)) in O(n*log(n)) time."
    1.39 +  [f coll]
    1.40 +  (reduce
    1.41 +    concat
    1.42 +    (filter #(= (count %) 1) (group-by f coll))))
    1.43 +  
    1.44 +(defn multiple-by
    1.45 +  "Keep all elements a,b, a!=b of coll for which
    1.46 +   (= (f a) (f b)) in O(n*log(n)) time."
    1.47 +  [f coll]
    1.48 +  (reduce
    1.49 +    concat
    1.50 +    (filter #(> (count %) 1) (group-by f coll))))
    1.51 +
    1.52 +(defn prod [[a b]] (* a b))
    1.53 +
    1.54 +(def p1 (multiple-by prod p0))
    1.55 +
    1.56 +;;; S: I was sure you couldn't.
    1.57 +
    1.58 +;; Each possible sum s has a set of possible pairs [a b]
    1.59 +;; where (= s (+ a b)). Partition p0 (since he *was* sure)
    1.60 +;; by sum, and keep those pairs that belong in partitions
    1.61 +;; where each pair in that partition is in p1.
    1.62 +
    1.63 +(defn sum [[a b]] (+ a b))
    1.64 +
    1.65 +(def p2
    1.66 +  (reduce
    1.67 +   concat
    1.68 +   (filter
    1.69 +    (partial every? (set p1))
    1.70 +    (group-by sum p0))))
    1.71 +
    1.72 +
    1.73 +;;; P: Then I have.
    1.74 +
    1.75 +;; Keep those pairs that have a unique product out of the
    1.76 +;; ones that are left.
    1.77 +
    1.78 +(def p3
    1.79 +  (unique-by prod p2))
    1.80 +
    1.81 +
    1.82 +;;; S: Then I have, too.
    1.83 +