Sum and product puzzle

I enjoyed working out this sum and product puzzle, in which two random numbers are chosen between 0 and 100, then one player is given their sum and another is given their product. The two players then repeatedly tell each other they don't know the randomly chosen numbers, and after several iterations, one of them does know the numbers. If you're interested in working out the puzzle yourself, go read Alex's writeup for the full question and stop reading here, because I'm going to spoil it below by working out a solution in Clojure.

While the two players seem to be childishly repeating over and over that they don't know the numbers, each of them is actually modeling what the other could know and doesn't, and using that information to update their own model of what they could know and don't. Each statement adds information, which is why eventually one of the players does know the answer.

The player given the product, Peter, is first to state that he doesn't know the two numbers, which means that the product he was told was not the product of two primes. And he knows more than that, because he knows the two random numbers are between 0 and 100 exclusive, so he can also rule out factors like 99 and 99, which, while not prime, are the only two numbers less than 100 whose product is 9801. Thus, if Peter doesn't know the numbers based on their product, then the product is not unique among all the products of two numbers between 0 and 100, and the player told the sum, Sandy, can eliminate those candidate pairs.

To model this in Clojure, we'll use a list of candidate number pairs:

(defn candidates [n]
  (distinct
    (for [i (range 1 n)
          j (range 1 n)]
      (sort [i j]))))

The pairs are sorted so distinct will remove pairs that are the same as another pair, just in a different order.

Any time Peter says he doesn't know the two numbers, it means the two numbers don't have a unique product among the candidates, and anytime Sandy doesn't know, the two numbers don't have a unique sum among the candidates. To remove candidates with unique products or sums, let's create a higher-order function that removes candidates based on the uniqueness of the result returned from then given function:

(defn remove-unique [f candidates]
  (->> candidates
    (group-by (partial apply f))
    (remove #(= 1 (count (second %))))
    (mapcat second)))

We'll use the thread-last macro to remove unique products:

(->> (candidates 10)
  (remove-unique *))

((3 8)
 (4 6)
 (1 4)
 (2 2)
 (4 9)
 (6 6)
 (1 6)
 (2 3)
 (2 6)
 (3 4)
 (1 9)
 (3 3)
 (2 8)
 (4 4)
 (2 9)
 (3 6)
 (1 8)
 (2 4))

A plain list is hard to read and notice differences in, so here's a table of products:

Removing unique products gives us

Sandy has the same candidates as Peter, but she's looking at sums instead of products:

Since Sandy still doesn't know the two numbers, Peter can eliminate any unique sums:

(->> (candidates 10)
  (remove-unique *)
  (remove-unique +))

That eliminates some non-unique products, which leaves some new unique products Peter can now eliminate:

Altogether, Peter and Sandy exchange 14 "I don't know the numbers":

(->> (candidates 100)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +))

When Peter finally says he does know the numbers, we switch from removing unique products to finding unique products:

(defn unique [f candidates]
  (->> candidates
    (group-by (partial apply f))
    (filter #(= 1 (count (second %))))
    (mapcat second)))

(->> (candidates 100)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (remove-unique *)
  (remove-unique +)
  (unique *))

((77 84))

Found it!

I like how this approach transparently restates the original problem as declarative code. All those remove-uniques seem repetitive, but this encoding aligns perfectly with the puzzle statement.

We'll tackle Alex's extra credit questions in the next post.