changeset 3:c8e35134bf8e

working on qotd.
author Robert McIntyre <rlm@mit.edu>
date Wed, 18 Jan 2012 05:18:57 -0700
parents c7df1ea6fd71
children 12d1367cf1aa
files src/rlm/function_utils.clj src/rlm/qotd.clj src/rlm/rlm_commands.clj
diffstat 3 files changed, 99 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
     1.1 --- a/src/rlm/function_utils.clj	Tue Dec 27 23:27:22 2011 -0700
     1.2 +++ b/src/rlm/function_utils.clj	Wed Jan 18 05:18:57 2012 -0700
     1.3 @@ -80,6 +80,22 @@
     1.4  	 (dorun (map future-cancel futures))
     1.5  	 answer))))
     1.6  
     1.7 +(defn mix-pred
     1.8 +  "Takes any number of mathematically equal functions with
     1.9 +   possibly different run-times and returns a function that
    1.10 +   runs each in a separate thread, returns the result from
    1.11 +   the first thread which finishes, and cancels the other threads."
    1.12 +  {:author "Robert McIntyre"}
    1.13 +  ([pred & functions]
    1.14 +     (fn [& args]
    1.15 +       (let [result (promise)
    1.16 +	     futures (doall (for [fun functions]
    1.17 +                              (let [answer (apply fun args)]
    1.18 +                                (if (pred answer)
    1.19 +                                  (future (deliver result (apply fun args)))))))
    1.20 +	     answer @result]
    1.21 +	 (dorun (map future-cancel futures))
    1.22 +	 answer))))
    1.23  
    1.24  
    1.25  
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/rlm/qotd.clj	Wed Jan 18 05:18:57 2012 -0700
     2.3 @@ -0,0 +1,80 @@
     2.4 +(ns rlm.qotd)
     2.5 +(rlm.rlm-commands/help)
     2.6 +
     2.7 +;;;There is a pair of integers, 1 < m < n, whose sum is less
     2.8 +;;;than 100.
     2.9 +
    2.10 +(def pos (fn [a]
    2.11 +           (filter (fn [[a b]] (< a b))
    2.12 +                   (map #(vector % a) (range 1 (- 100 a))))))
    2.13 +
    2.14 +(def p0 (reduce concat (map pos (range 2 99))))
    2.15 +
    2.16 +;;; Person S knows their sum, but nothing else about them.
    2.17 +;;; Person P knows their product, but nothing else about
    2.18 +;;; them.
    2.19 +
    2.20 +;;; Now, Persons S and P know the above information, and each
    2.21 +;;; one knows that the other one knows it. They have the
    2.22 +;;; following conversation:
    2.23 +
    2.24 +;;; P: I can't figure out what the numbers are.
    2.25 +
    2.26 +
    2.27 +
    2.28 +;; Eliminate pairs with a unique product.
    2.29 +
    2.30 +(defn group-by
    2.31 +  "Split coll into groups where the f maps each element in a
    2.32 +  group to the same value in O(n*log(n)) time."
    2.33 +  [f coll]
    2.34 +  (partition-by f (sort-by f coll)))
    2.35 +
    2.36 +(defn unique-by
    2.37 +  "Remove all elements a,b of coll that for which
    2.38 +   (= (f a) (f b)) in O(n*log(n)) time."
    2.39 +  [f coll]
    2.40 +  (reduce
    2.41 +    concat
    2.42 +    (filter #(= (count %) 1) (group-by f coll))))
    2.43 +  
    2.44 +(defn multiple-by
    2.45 +  "Keep all elements a,b, a!=b of coll for which
    2.46 +   (= (f a) (f b)) in O(n*log(n)) time."
    2.47 +  [f coll]
    2.48 +  (reduce
    2.49 +    concat
    2.50 +    (filter #(> (count %) 1) (group-by f coll))))
    2.51 +
    2.52 +(defn prod [[a b]] (* a b))
    2.53 +
    2.54 +(def p1 (multiple-by prod p0))
    2.55 +
    2.56 +;;; S: I was sure you couldn't.
    2.57 +
    2.58 +;; Each possible sum s has a set of possible pairs [a b]
    2.59 +;; where (= s (+ a b)). Partition p0 (since he *was* sure)
    2.60 +;; by sum, and keep those pairs that belong in partitions
    2.61 +;; where each pair in that partition is in p1.
    2.62 +
    2.63 +(defn sum [[a b]] (+ a b))
    2.64 +
    2.65 +(def p2
    2.66 +  (reduce
    2.67 +   concat
    2.68 +   (filter
    2.69 +    (partial every? (set p1))
    2.70 +    (group-by sum p0))))
    2.71 +
    2.72 +
    2.73 +;;; P: Then I have.
    2.74 +
    2.75 +;; Keep those pairs that have a unique product out of the
    2.76 +;; ones that are left.
    2.77 +
    2.78 +(def p3
    2.79 +  (unique-by prod p2))
    2.80 +
    2.81 +
    2.82 +;;; S: Then I have, too.
    2.83 +
     3.1 --- a/src/rlm/rlm_commands.clj	Tue Dec 27 23:27:22 2011 -0700
     3.2 +++ b/src/rlm/rlm_commands.clj	Wed Jan 18 05:18:57 2012 -0700
     3.3 @@ -124,7 +124,9 @@
     3.4     "/home/r/java/jdk6u30-docs/jdk/api")
     3.5    (clojure.java.javadoc/add-local-javadoc
     3.6     "/home/r/java/jdk6u30-docs/jre/api")
     3.7 -  
     3.8 +  (clojure.java.javadoc/add-local-javadoc
     3.9 +   "/home/r/proj/jmeCapture/docs")
    3.10 +
    3.11    nil)
    3.12  
    3.13