rlm@3: (ns rlm.qotd)
rlm@3: (rlm.rlm-commands/help)
rlm@3: 
rlm@3: ;;;There is a pair of integers, 1 < m < n, whose sum is less
rlm@3: ;;;than 100.
rlm@3: 
rlm@3: (def pos (fn [a]
rlm@3:            (filter (fn [[a b]] (< a b))
rlm@3:                    (map #(vector % a) (range 1 (- 100 a))))))
rlm@3: 
rlm@3: (def p0 (reduce concat (map pos (range 2 99))))
rlm@3: 
rlm@3: ;;; Person S knows their sum, but nothing else about them.
rlm@3: ;;; Person P knows their product, but nothing else about
rlm@3: ;;; them.
rlm@3: 
rlm@3: ;;; Now, Persons S and P know the above information, and each
rlm@3: ;;; one knows that the other one knows it. They have the
rlm@3: ;;; following conversation:
rlm@3: 
rlm@3: ;;; P: I can't figure out what the numbers are.
rlm@3: 
rlm@3: 
rlm@3: 
rlm@3: ;; Eliminate pairs with a unique product.
rlm@3: 
rlm@3: (defn group-by
rlm@3:   "Split coll into groups where the f maps each element in a
rlm@3:   group to the same value in O(n*log(n)) time."
rlm@3:   [f coll]
rlm@3:   (partition-by f (sort-by f coll)))
rlm@3: 
rlm@3: (defn unique-by
rlm@3:   "Remove all elements a,b of coll that for which
rlm@3:    (= (f a) (f b)) in O(n*log(n)) time."
rlm@3:   [f coll]
rlm@3:   (reduce
rlm@3:     concat
rlm@3:     (filter #(= (count %) 1) (group-by f coll))))
rlm@3:   
rlm@3: (defn multiple-by
rlm@3:   "Keep all elements a,b, a!=b of coll for which
rlm@3:    (= (f a) (f b)) in O(n*log(n)) time."
rlm@3:   [f coll]
rlm@3:   (reduce
rlm@3:     concat
rlm@3:     (filter #(> (count %) 1) (group-by f coll))))
rlm@3: 
rlm@3: (defn prod [[a b]] (* a b))
rlm@3: 
rlm@3: (def p1 (multiple-by prod p0))
rlm@3: 
rlm@3: ;;; S: I was sure you couldn't.
rlm@3: 
rlm@3: ;; Each possible sum s has a set of possible pairs [a b]
rlm@3: ;; where (= s (+ a b)). Partition p0 (since he *was* sure)
rlm@3: ;; by sum, and keep those pairs that belong in partitions
rlm@3: ;; where each pair in that partition is in p1.
rlm@3: 
rlm@3: (defn sum [[a b]] (+ a b))
rlm@3: 
rlm@3: (def p2
rlm@3:   (reduce
rlm@3:    concat
rlm@3:    (filter
rlm@3:     (partial every? (set p1))
rlm@3:     (group-by sum p0))))
rlm@3: 
rlm@3: 
rlm@3: ;;; P: Then I have.
rlm@3: 
rlm@3: ;; Keep those pairs that have a unique product out of the
rlm@3: ;; ones that are left.
rlm@3: 
rlm@3: (def p3
rlm@3:   (unique-by prod p2))
rlm@3: 
rlm@3: 
rlm@3: ;;; S: Then I have, too.
rlm@3: