Mercurial > rlm
comparison src/rlm/qotd.clj @ 3:c8e35134bf8e
working on qotd.
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Wed, 18 Jan 2012 05:18:57 -0700 |
| parents | |
| children | 12d1367cf1aa |
comparison
equal
deleted
inserted
replaced
| 2:c7df1ea6fd71 | 3:c8e35134bf8e |
|---|---|
| 1 (ns rlm.qotd) | |
| 2 (rlm.rlm-commands/help) | |
| 3 | |
| 4 ;;;There is a pair of integers, 1 < m < n, whose sum is less | |
| 5 ;;;than 100. | |
| 6 | |
| 7 (def pos (fn [a] | |
| 8 (filter (fn [[a b]] (< a b)) | |
| 9 (map #(vector % a) (range 1 (- 100 a)))))) | |
| 10 | |
| 11 (def p0 (reduce concat (map pos (range 2 99)))) | |
| 12 | |
| 13 ;;; Person S knows their sum, but nothing else about them. | |
| 14 ;;; Person P knows their product, but nothing else about | |
| 15 ;;; them. | |
| 16 | |
| 17 ;;; Now, Persons S and P know the above information, and each | |
| 18 ;;; one knows that the other one knows it. They have the | |
| 19 ;;; following conversation: | |
| 20 | |
| 21 ;;; P: I can't figure out what the numbers are. | |
| 22 | |
| 23 | |
| 24 | |
| 25 ;; Eliminate pairs with a unique product. | |
| 26 | |
| 27 (defn group-by | |
| 28 "Split coll into groups where the f maps each element in a | |
| 29 group to the same value in O(n*log(n)) time." | |
| 30 [f coll] | |
| 31 (partition-by f (sort-by f coll))) | |
| 32 | |
| 33 (defn unique-by | |
| 34 "Remove all elements a,b of coll that for which | |
| 35 (= (f a) (f b)) in O(n*log(n)) time." | |
| 36 [f coll] | |
| 37 (reduce | |
| 38 concat | |
| 39 (filter #(= (count %) 1) (group-by f coll)))) | |
| 40 | |
| 41 (defn multiple-by | |
| 42 "Keep all elements a,b, a!=b of coll for which | |
| 43 (= (f a) (f b)) in O(n*log(n)) time." | |
| 44 [f coll] | |
| 45 (reduce | |
| 46 concat | |
| 47 (filter #(> (count %) 1) (group-by f coll)))) | |
| 48 | |
| 49 (defn prod [[a b]] (* a b)) | |
| 50 | |
| 51 (def p1 (multiple-by prod p0)) | |
| 52 | |
| 53 ;;; S: I was sure you couldn't. | |
| 54 | |
| 55 ;; Each possible sum s has a set of possible pairs [a b] | |
| 56 ;; where (= s (+ a b)). Partition p0 (since he *was* sure) | |
| 57 ;; by sum, and keep those pairs that belong in partitions | |
| 58 ;; where each pair in that partition is in p1. | |
| 59 | |
| 60 (defn sum [[a b]] (+ a b)) | |
| 61 | |
| 62 (def p2 | |
| 63 (reduce | |
| 64 concat | |
| 65 (filter | |
| 66 (partial every? (set p1)) | |
| 67 (group-by sum p0)))) | |
| 68 | |
| 69 | |
| 70 ;;; P: Then I have. | |
| 71 | |
| 72 ;; Keep those pairs that have a unique product out of the | |
| 73 ;; ones that are left. | |
| 74 | |
| 75 (def p3 | |
| 76 (unique-by prod p2)) | |
| 77 | |
| 78 | |
| 79 ;;; S: Then I have, too. | |
| 80 |