Task[edit]
Solve the "Impossible Puzzle":


X and Y are two different whole numbers greater than 1. Their sum is no greater than 100, and Y is greater than X. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X+Y and P knows the product X*Y. Both S and P know all the information in this paragraph.
The following conversation occurs:

 S says "P does not know X and Y."
 P says "Now I know X and Y."
 S says "Now I also know X and Y!"
What are X and Y?


Guidance
It can be hard to wrap one's head around what the three lines of dialog between S (the "sum guy") and P (the "product guy") convey about the values of X and Y.

So for your convenience, here's a break-down:





 Quote

 Implied fact


 1)

 S says "P does not know X and Y."

 For every possible sum decomposition of the number X+Y, the product has in turn more than one product decomposition.


 2)

 P says "Now I know X and Y."

 The number X*Y has only one product decomposition for which fact 1 is true.


 3)

 S says "Now I also know X and Y."

 The number X+Y has only one sum decomposition for which fact 2 is true.

Terminology:

 "sum decomposition" of a number = Any pair of positive integers (A, B) so that A+B equals the number. Here, with the additional constraint 2 ≤ A < B.
 "product decomposition" of a number = Any pair of positive integers (A, B) so that A*B equals the number. Here, with the additional constraint 2 ≤ A < B.


Your program can solve the puzzle by considering all possible pairs (X, Y) in the range 2 ≤ X < Y ≤ 98, and then successively eliminating candidates based on the three facts. It turns out only one solution remains!

See the Python example for an implementation that uses this approach with a few optimizations.

See also
   Wikipedia:   Sum and Product Puzzle

import sequtils, sets, sugar, tables
 
var
  xycandidates = toSeq(2..98)
  sums = collect(initHashSet, for s in 5..100: {s})   # Set of possible sums.
  factors: Table[int, seq[(int, int)]]                # Mapping product -> list of factors.
 
# Build the factor mapping.
for i in 0..<xycandidates.high:
  let x = xycandidates[i]
  for j in (i + 1)..xycandidates.high:
    let y = xycandidates[j]
    factors.mgetOrPut(x * y, @[]).add (x, y)
 
iterator terms(n: int): (int, int) =
  ## Yield the possible terms (x, y) of a given sum.
  for x in 2..(n - 1) div 2:
    yield (x, n - x)
 
# S says "P does not know X and Y."
# => For every decomposition of S, there is no product with a single decomposition.
for s in toSeq(sums):
  for (x, y) in s.terms():
    let p = x * y
    if factors[p].len == 1:
      sums.excl s
      break
 
# P says "Now I know X and Y."
# => P has only one decomposition with sum in "sums".
for p in toSeq(factors.keys):
  var sums = collect(initHashSet):
               for (x, y) in factors[p]:
                 if x + y in sums: {x + y}
  if card(sums) > 1: factors.del p
 
# S says "Now I also know X and Y."
# => S has only one decomposition with product in "factors".
for s in toSeq(sums):
  var prods = collect(initHashSet):
                for (x, y) in s.terms():
                  if x * y in factors: {x * y}
  if card(prods) > 1: sums.excl s
 
# Now, combine the sums and the products.
for s in sums:
  for (x, y) in s.terms:
    if x * y in factors: echo (x, y)