Solving the Impossible puzzle in Clojure

I found this puzzle recently. I should say I rediscovered it, as I knew it from before. I wanted to solve it in Clojure – here’s one possible solution, with comments on the thought process involved in solving it (in the comments before the actual code).

```(ns com.icyrock.clojure.prb.xynum)

; http://puzzling.stackexchange.com/questions/251/i-dont-know-the-two-numbers-but-now-i-do
; http://en.wikipedia.org/wiki/Impossible_Puzzle
; http://people.sc.fsu.edu/~jburkardt/fun/puzzles/impossible_solution.html

; Two numbers, 1 < x < y, x + y < n (n = 100 in the linked question)
; p = x * y
; s = x + y

; p: I cannot determine the two numbers.
;   => p not unique: p = x1 * y1 = x2 * y2 = ...
;      Let's call this an ambiguous product

; s: I knew that.
;   => s can be created from one or multiple pairs: s = x1 + y1 = x2 + y2 = ...
;      Those pairs form these products:
;        p1 = x1 * y1
;        p2 = x2 * y2
;        ...
;      Each of these products can be created from multiple pairs (i.e. is ambiguous):
;        p1 = x11 * y11 = x12 * y12 = ...
;        p2 = x21 * y21 = x12 * y22 = ...
;        ...
;      Let's call this product-ambiguous sum

; p: Now I can determine them.
;   => p = x1 * y1 = x2 * y2 = ...
;      Only one of (xk, yk) forms a product-ambiguous sum
;      Let's call this unambiguous product

; s: So can I.
;   => s = x1 + y1 = x2 + y2 = ...
;      Only one of all the possible products:
;        p1 = x1 * y1
;        p2 = x2 * y2
;        ...
;      is an unambiguous product
;      Let's call this unambiguous sum

(defn xynum [n]
(let [pairs (for [y (range 2 n) x (range 2 y) :when (< (+ x y) n)] [x y])
sum-map (group-by (partial apply +) pairs)
prod-map (group-by (partial apply *) pairs)
; Pair forms a product. That product can be formed from at least some other pair.
is-ambiguous-product (fn [pair]
(> (count (prod-map (apply * pair))) 1))
; Pair forms a sum. That sum can be formed from other pairs. Those pairs form some products. All those products are ambiguous.
is-product-ambiguous-sum (fn [pair]
(every? true? (map is-ambiguous-product (sum-map (apply + pair)))))
; Pair forms a product. That product can be formed from other pairs. Only one of those pairs forms a product-ambiguous sum.
is-unambiguous-product (fn [pair]
(= 1 (count (filter true? (map is-product-ambiguous-sum (prod-map (apply * pair)))))))
; Pair forms a sum. That sum can be formed from other pairs. Only one of those pairs forms an unambiguous product.
is-unambiguous-sum (fn [pair]
(= 1 (count (filter true? (map is-unambiguous-product (sum-map (apply + pair)))))))
is-pair-a-candidate (fn [pair] (and
(is-ambiguous-product pair)
(is-product-ambiguous-sum pair)
(is-unambiguous-product pair)
(is-unambiguous-sum pair)))
candidates (filter is-pair-a-candidate pairs)]
(println "Pair count:" (count pairs))
(println "Sum map count:" (count sum-map))
(println "Product map count:" (count prod-map))
(println "Candidates count:" (count candidates))
(println "Candidates: " candidates)))

(defn -main []
(xynum 100))

(-main)
```

Note also the Wikipedia entry, which contains solutions in other languages. I particularly liked the Scala version, notably for its conciseness and readability.