Mercurial > rlm

     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
author	Robert McIntyre <rlm@mit.edu>
date	Wed, 18 Jan 2012 05:18:57 -0700
parents
children	12d1367cf1aa