Sum and product puzzle
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
<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
<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.
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)
- Find all pairs, for which no sum decomposition has unique product
- 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))]
- 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]
- 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)]
Ruby
<lang ruby>s1 = (a = *2...100).product(a).select{|x,y| x<y && x+y<100}
def add(x,y) x + y end def mul(x,y) x * y end
sumEq = ->(p){ s1.select{|q| add(*p) == add(*q)} } mulEq = ->(p){ s1.select{|q| mul(*p) == mul(*q)} }
s2 = s1.select{|p| sumEq[p].all?{|q| mulEq[q].size != 1} } s3 = s2.select{|p| (mulEq[p] & s2).size == 1} p s3.select{|p| (sumEq[p] & s3).size == 1}</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.