Sum and product puzzle

Sum and product puzzle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Solve the Impossible Puzzle:

X and Y are two different integers, greater than 1, with sum less than or equal to 100. S and P are two mathematicians; S knows the sum X+Y, P knows the product X*Y, and both are perfect logicians. Both S and P know the information in these two sentences. 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?

See also: Sum and Product Puzzle

D

Translation of: Scala

<lang d>void main() {

   import std.stdio, std.algorithm, std.range, std.typecons;

   const s1 = cartesianProduct(iota(1, 101), iota(1, 101))
              .filter!(p => 1 < p[0] && p[0] < p[1] && p[0] + p[1] < 100)
              .array;

   alias P = const Tuple!(int, int);
   enum add   = (P p) => p[0] + p[1];
   enum mul   = (P p) => p[0] * p[1];
   enum sumEq = (P p) => s1.filter!(q => add(q) == add(p));
   enum mulEq = (P p) => s1.filter!(q => mul(q) == mul(p));

   const s2 = s1.filter!(p => sumEq(p).all!(q => mulEq(q).walkLength != 1)).array;
   const s3 = s2.filter!(p => mulEq(p).setIntersection(s2).walkLength == 1).array;
   s3.filter!(p => sumEq(p).setIntersection(s3).walkLength == 1).writeln;

}</lang>

Output:

[const(Tuple!(int, int))(4, 13)]

With an older version of the LDC2 compiler replace the cartesianProduct line with: <lang d>

   const s1 = iota(1, 101).map!(x => iota(1, 101).map!(y => tuple(x, y))).joiner

</lang> The .array turn the lazy ranges into arrays. This is a necessary optimization because D lazy Ranges aren't memoized as Haskell lazy lists.

Run-time: about 0.43 seconds with dmd, 0.08 seconds with ldc2.

Haskell

Translation of: D

<lang haskell>import Data.List (intersect)

s1, s2, s3, s4 :: [(Int, Int)] s1 = [(x, y) | x <- [1 .. 100], y <- [1 .. 100], 1 < x && x < y && x + y < 100]

add, mul :: (Int, Int) -> Int add (x, y) = x + y mul (x, y) = x * y

sumEq, mulEq :: (Int, Int) -> [(Int, Int)] sumEq p = filter (\q -> add q == add p) s1 mulEq p = filter (\q -> mul q == mul p) s1

s2 = filter (\p -> all (\q -> (length $ mulEq q) /= 1) (sumEq p)) s1 s3 = filter (\p -> length (mulEq p `intersect` s2) == 1) s2 s4 = filter (\p -> length (sumEq p `intersect` s3) == 1) s3

main = print s4</lang>

Output:

[(4,13)]

Run-time: about 1.97 seconds.

Scala

<lang scala>object ImpossiblePuzzle extends App {

 type XY = (Int, Int)
 val step0 = for {
   x <- 1 to 100
   y <- 1 to 100
   if 1 < x && x < y && x + y < 100
 } yield (x, y)

 def sum(xy: XY) = xy._1 + xy._2
 def prod(xy: XY) = xy._1 * xy._2
 def sumEq(xy: XY) = step0 filter { sum(_) == sum(xy) }
 def prodEq(xy: XY) = step0 filter { prod(_) == prod(xy) }

 val step2 = step0 filter { sumEq(_) forall { prodEq(_).size != 1 }}
 val step3 = step2 filter { prodEq(_).intersect(step2).size == 1 }
 val step4 = step3 filter { sumEq(_).intersect(step3).size == 1 }
 println(step4)

}</lang>

Output:

Vector((4,13))

Run-time: about 3.82 seconds.