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.

Go

<lang go>package main

import "fmt"

type pair struct{ x, y int }

func main() { //const max = 100 // Use 1685 (the highest with a unique answer) instead // of 100 just to make it work a little harder :). const max = 1685 var all []pair for a := 2; a < max; a++ { for b := a + 1; b < max-a; b++ { all = append(all, pair{a, b}) } } fmt.Println("There are", len(all), "pairs where a+b <", max, "(and a<b)") products := countProducts(all)

// Those for which no sum decomposition has unique product to are // S mathimatician's possible pairs. var sPairs []pair pairs: for _, p := range all { s := p.x + p.y // foreach a+b=s (a<b) for a := 2; a < s/2+s&1; a++ { b := s - a if products[a*b] == 1 { // Excluded because P would have a unique product continue pairs } } sPairs = append(sPairs, p) } fmt.Println("S starts with", len(sPairs), "possible pairs.") //fmt.Println("S pairs:", sPairs) sProducts := countProducts(sPairs)

// Look in sPairs for those with a unique product to get // P mathimatician's possible pairs. var pPairs []pair for _, p := range sPairs { if sProducts[p.x*p.y] == 1 { pPairs = append(pPairs, p) } } fmt.Println("P then has", len(pPairs), "possible pairs.") //fmt.Println("P pairs:", pPairs) pSums := countSums(pPairs)

// Finally, look in pPairs for those with a unique sum var final []pair for _, p := range pPairs { if pSums[p.x+p.y] == 1 { final = append(final, p) } }

// Nicely show any answers. switch len(final) { case 1: fmt.Println("Answer:", final[0].x, "and", final[0].y) case 0: fmt.Println("No possible answer.") default: fmt.Println(len(final), "possible answers:", final) } }

func countProducts(list []pair) map[int]int { m := make(map[int]int) for _, p := range list { m[p.x*p.y]++ } return m }

func countSums(list []pair) map[int]int { m := make(map[int]int) for _, p := range list { m[p.x+p.y]++ } return m }

// not used, manually inlined above func decomposeSum(s int) []pair { pairs := make([]pair, 0, s/2) for a := 2; a < s/2+s&1; a++ { pairs = append(pairs, pair{a, s - a}) } return pairs }</lang>

Output:

For x + y < 100 (max = 100):

There are 2304 pairs where a+b < 100 (and a<b)
S starts with 145 possible pairs.
P then has 86 possible pairs.
Answer: 4 and 13

For x + y < 1685 (max = 1685):

There are 706440 pairs where a+b < 1685 (and a<b)
S starts with 50485 possible pairs.
P then has 17485 possible pairs.
Answer: 4 and 13

Run-time ~1 msec and ~600 msec respectively. Could be slightly faster if the slices and maps were given an estimated capacity to start (e.g. (max/2)² for all pairs) to avoid re-allocations (and resulting copies).

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 = uncurry (+) mul = uncurry (*)

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.

Python

From Wikipedia: <lang python>from collections import Counter

all_pairs=set((a,b) for a in range(2,100) for b in range(a+1,100) if a+b<100)

def decompose_sum(s):

   return [(a,s-a) for a in range(2,int(s/2+1))]

_prod_counts=Counter(a*b for a,b in all_pairs) unique_products=set((a,b) for a,b in all_pairs if _prod_counts[a*b]==1)

1. Find all pairs, for which no sum decomposition has unique product
2. In other words, for which all sum decompositions have non-unique product

s_pairs=[(a,b) for a,b in all_pairs if

   all((x,y) not in unique_products for (x,y) in decompose_sum(a+b))]

1. Since product guy now knows, possible pairs are those out of above for which product is unique

product_pairs=[(a,b) for a,b in s_pairs if Counter(c*d for c,d in s_pairs)[a*b]==1]

1. Since the sum guy now knows

final_pairs=[(a,b) for a,b in product_pairs if Counter(c+d for c,d in product_pairs)[a+b]==1]

print(final_pairs) # [(4, 13)]</lang>

Output:

[(4, 13)]

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.