Sum and product puzzle: Difference between revisions
Added various BASIC dialects (BASIC256 and Gambas)
(Added various BASIC dialects (BASIC256 and Gambas)) |
|||
| (11 intermediate revisions by 5 users not shown) | |||
Line 1:
{{task}}
;Task:
Solve the "<i>Impossible Puzzle</i>":
Line 86:
<pre>
[(4, 13)]
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # solve the sum and product puzzle: find X, Y where 1 < X < Y; X + Y <= 100 #
# mathematician S knows X + Y and P knows X * Y #
# S says P doesn't know X and Y, P says they now know X and Y which leads S #
# to also know X and Y #
# which leads to the following (from the task) #
# 1: For every possible sum decomposition of the number X+Y, #
# the product has in turn more than one product decomposition #
# 2: The number X*Y has only one product decomposition for which 1: is true #
# 3: The number X+Y has only one sum decomposition for which 2: is true #
# determine the possible sums and products and count their occurances #
INT max n = 98, min n = 2;
[ 0 : max n * max n ]INT s count, p count;
[ min n : max n, min n : max n ]BOOL candidate;
FOR x FROM LWB p count TO UPB p count DO p count[ x ] := s count[ x ] := 0 OD;
FOR x FROM min n TO max n DO FOR y FROM min n TO max n DO candidate[ x, y ] := FALSE OD OD;
FOR x FROM min n TO max n - min n DO
FOR y FROM x + 1 TO max n - x DO
s count[ x + y ] +:= 1;
p count[ x * y ] +:= 1
OD
OD;
# shows the count of the candidates #
PROC show candidates = ( STRING stage )VOID:
BEGIN
INT c count := 0;
FOR x FROM min n TO max n DO
FOR y FROM min n TO max n DO IF candidate[ x, y ] THEN c count +:= 1 FI OD
OD;
print( ( stage, " ", whole( c count, - 5 ), " candidate", IF c count = 1 THEN "" ELSE "s" FI, newline ) )
END # show candidates # ;
# checks 1: is TRUE for x plus y, returns TRUE if it is, FALSE otherwose #
PROC all sums have multiple product decompositions = ( INT x plus y )BOOL:
BEGIN
BOOL all multiple p := TRUE;
FOR x FROM min n TO x plus y OVER 2 WHILE all multiple p DO
INT y = x plus y - x;
IF y > x AND y <= max n THEN
# x, y is a sum decomposition of x plus y #
IF candidate[ x, y ] THEN all multiple p := all multiple p AND p count[ x * y ] > 1 FI
FI
OD;
all multiple p
END # all sums have multiple product decompositions # ;
# checks 2: is TRUE for x times y, returns TRUE if it is, FALSE otherwose #
PROC only one product decomposition = ( INT x times y )BOOL:
BEGIN
INT multiple p := 0;
FOR x FROM min n TO ENTIER sqrt( x times y ) DO
IF x times y MOD x = 0 THEN
INT y = x times y OVER x;
IF y > x AND y <= max n THEN
# x, y is a product decomposition of x times y #
IF candidate[ x, y ] THEN
IF all sums have multiple product decompositions( x + y ) THEN
multiple p +:= 1
FI
FI
FI
FI
OD;
multiple p = 1
END # only one product decomposition # ;
# start off with all min n .. max n as candidates #
FOR x FROM min n TO max n DO
FOR y FROM x + 1 TO max n DO
IF x + y <= 100 THEN candidate[ x, y ] := TRUE FI
OD
OD;
show candidates( "Sum and product puzzle " );
# Statement 1: S says P doesn't know X and Y #
FOR x plus y FROM min n TO max n + min n DO
IF NOT all sums have multiple product decompositions( x plus y ) THEN
FOR x FROM min n TO x plus y OVER 2 DO
INT y = x plus y - x;
IF y > x AND y <= max n THEN candidate[ x, y ] := FALSE FI
OD
FI
OD;
show candidates( "After statement 1 " );
# Statement 2: P says they now know X and Y #
FOR x times y FROM min n * ( min n + 1 ) TO max n * max n DO
IF NOT only one product decomposition( x times y ) THEN
FOR x FROM min n TO ENTIER sqrt( x times y ) DO
IF x times y MOD x = 0 THEN
INT y = x times y OVER x;
IF y > x AND y <= max n THEN candidate[ x, y ] := FALSE FI
FI
OD
FI
OD;
show candidates( "After statement 2 " );
# Statement 3: S says they now also know X and Y, check 3: #
FOR x plus y FROM min n TO max n + min n DO
INT multiple s := 0;
FOR x FROM min n TO x plus y OVER 2 DO
INT y = x plus y - x;
IF y > x AND y <= max n THEN
# x, y is a sum decomposition of x plus y #
IF candidate[ x, y ] THEN
IF only one product decomposition( x * y ) THEN multiple s +:= 1 FI
FI
FI
OD;
IF multiple s /= 1 THEN
FOR x FROM min n TO x plus y OVER 2 DO
INT y = x plus y - x;
IF y > x AND y <= max n THEN candidate[ x, y ] := FALSE FI
OD
FI
OD;
show candidates( "After statement 3 " );
print( ( newline, "solution: " ) );
FOR x FROM min n TO max n DO
FOR y FROM min n TO max n DO
IF candidate[ x, y ] THEN print( ( whole( x, 0 ), ", ", whole( y, 0 ), newline ) ) FI
OD
OD
END
</syntaxhighlight>
{{out}}
<pre>
Sum and product puzzle 2352 candidates
After statement 1 145 candidates
After statement 2 86 candidates
After statement 3 1 candidate
solution: 4, 13
</pre>
Line 158 ⟶ 299:
17 (4+13)
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">for s = 2 to 100
a = satisfies_statement3(s)
if a <> 0 then print s & " (" & a & "+" & s - a & ")"
next s
end
function is_prime(x)
if x <= 1 then return false
for i = 2 to sqr(x)
if x mod i = 0 then return false
next i
return True
end function
function satisfies_statement1(s)
for a = 2 to s \ 2
if is_prime(a) and is_prime(s - a) then return false
next a
return true
end function
function satisfies_statement2(p)
winner = 0
for i = 2 to sqr(p)
if p mod i = 0 then
j = p \ i
if j < 2 or j > 99 then continue for
if satisfies_statement1(i + j) then
if winner then return false
winner = 1
end if
end if
next i
return winner
end function
function satisfies_statement3(s)
if not satisfies_statement1(s) then return false
winner = 0
for a = 2 to s \ 2
b = s - a
if satisfies_statement2(a * b) then
if winner then return false
winner = a
end if
next a
return winner
end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Function is_prime(x As Integer) As Boolean
If x <= 1 Then Return False
For i As Integer = 2 To Sqr(x)
If x Mod i = 0 Then Return False
Next
Return True
End Function
Function satisfies_statement1(s As Integer) As Boolean
For a As Integer = 2 To s \ 2
If is_prime(a) And is_prime(s - a) Then Return False
Next
Return True
End Function
Function satisfies_statement2(p As Integer) As Integer
Dim winner As Integer = 0
For i As Integer = 2 To Sqr(p)
If p Mod i = 0 Then
Dim j As Integer = p \ i
If j < 2 Or j > 99 Then Continue
If satisfies_statement1(i + j) Then
If winner Then Return False
winner = 1
End If
End If
Next
Return winner
End Function
Function satisfies_statement3(s As Integer) As Integer
If Not satisfies_statement1(s) Then Return False
Dim winner As Integer = 0
For a As Integer = 2 To s \ 2
Dim b As Integer = s - a
If satisfies_statement2(a * b) Then
If winner Then Return False
winner = a
End If
Next
Return winner
End Function
Public Sub Main()
For s As Integer = 2 To 100
Dim a As Integer = satisfies_statement3(s)
If a <> 0 Then Print s; " ("; a; "+"; s - a; ")"
Next
End </syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C}}==
Line 909 ⟶ 1,169:
Running time: 0.241637693 seconds
</pre>
=={{header|FreeBASIC}}==
{{trans|AWK}}
Runs in 0.001s
<syntaxhighlight lang="vbnet">Function is_prime(x As Integer) As Boolean
If x <= 1 Then Return False
For i As Integer = 2 To Sqr(x)
If x Mod i = 0 Then Return False
Next i
Return True
End Function
Function satisfies_statement1(s As Integer) As Boolean
For a As Integer = 2 To s \ 2
If is_prime(a) And is_prime(s - a) Then Return False
Next a
Return True
End Function
Function satisfies_statement2(p As Integer) As Integer
Dim As Integer i, j
Dim winner As Integer = 0
For i = 2 To Sqr(p)
If p Mod i = 0 Then
j = p \ i
If j < 2 Or j > 99 Then Continue For
If satisfies_statement1(i + j) Then
If winner Then Return False
winner = 1
End If
End If
Next i
Return winner
End Function
Function satisfies_statement3(s As Integer) As Integer
Dim As Integer a, b
If Not satisfies_statement1(s) Then Return False
Dim winner As Integer = 0
For a = 2 To s \ 2
b = s - a
If satisfies_statement2(a * b) Then
If winner Then Return False
winner = a
End If
Next a
Return winner
End Function
Dim As Integer s, a
For s = 2 To 100
a = satisfies_statement3(s)
If a <> 0 Then
Print s & " (" & a & "+" & s - a & ")"
End If
Next s
Sleep</syntaxhighlight>
{{out}}
<pre>17 (4+13)</pre>
=={{header|Go}}==
Line 1,093 ⟶ 1,413:
=={{header|J}}==
'''Tacit Solution'''
<syntaxhighlight lang="j">(S=. X + Y) (P=. X * Y) (X=. 0&{"1) (Y=. 1&{"1)
(
candidates=. ([ echo o (' candidates' ,~ ": (o=. @:) #))
Line 1,100 ⟶ 1,420:
filter0=. candidates o (constraints # ])
pmtod=. P o ; o (pd #~ 1 < P #/. ]) NB. products with more than one decomposition
filter1=. candidates o ((patesd ('' -: -.)&>"0 _ < o pmtod) ; o # sd)
Line 1,112 ⟶ 1,430:
show=. 'X=' , ": o X ,' Y=' , ": o Y , ' X+Y=' , ": o (X+Y) , ' X*Y=' , ": o (X*Y)
solve=. show :: (''"_) o filter3 o filter2 o filter1 o (] filter0 decompositions) f.
</syntaxhighlight>
Example use:
Line 1,122 ⟶ 1,441:
X=4 Y=13 X+Y=17 X*Y=52
solve
solve 1685
Line 1,134 ⟶ 1,453:
17567 candidates
2 candidates
X=4 4 Y=13 61 X+Y=17 65 X*Y=52 244
solve 1970
967272 candidates
70475 candidates
23985 candidates
3 candidates
X=4 4 16 Y=13 61 73 X+Y=17 65 89 X*Y=52 244 1168
solve 2522
1586340 candidates
116238 candidates
37748 candidates
4 candidates
X=4 4 16 16 Y=13 61 73 111 X+Y=17 65 89 127 X*Y=52 244 1168 1776</syntaxhighlight>
The code is tacit and fixed (in other words, it is point-free):
<syntaxhighlight lang="j"> _80 [\ (5!:5)<'solve'
('X=' , ":@:(0&{"1) , ' Y=' , ":@:(1&{"1) , ' X+Y=' , ":@:(0&{"1 + 1&{"1) , ' X*
Y=' , ":@:(0&{"1 * 1&{"1)) ::(''"_)@:(([ 0 0&$@(1!:2&2)@:(' candidates' ,~ ":@:#
))@:;@:(((0&{"1 + 1&{"1) </. ]) #~ 1 = #&>@:((0&{"1 + 1&{"1) </. ])))@:(([ 0 0&$
@(1!:2&2)@:(' candidates' ,~ ":@:#))@:;@:(((0&{"1 * 1&{"1) </. ]) #~ 1 = #&>@:((
0&{"1 * 1&{"1) </. ])))@:(([ 0 0&$@(1!:2&2)@:(' candidates' ,~ ":@:#))@:((((0&{"
1 + 1&{"1) <@:(0&{"1 * 1&{"1)/. ]) ('' -: -.)&>"0 _ <@:((0&{"1 * 1&{"1)@:;@:(((0
&{"1 * 1&{"1) </. ]) #~ 1 < (0&{"1 * 1&{"1) #/. ]))) ;@:# (0&{"1 + 1&{"1) </. ])
)@:(] ([ 0 0&$@(1!:2&2)@:(' candidates' ,~ ":@:#))@:((([ >: (0&{"1 + 1&{"1)@:])
*. ((1 < 0&{"1) *. (1 < 1&{"1) *. 0&{"1 < 1&{"1)@:]) # ]) >@:,@:{@:(;~)@:i.)</syntaxhighlight>
=={{header|Java}}==
Line 1,791 ⟶ 2,124:
a=4, b=13; S=17, P=52</pre>
=={{header|
<syntaxhighlight lang="Matlab">
function SumProductPuzzle(maxSum, m)
Line 1,885 ⟶ 2,218:
Elapsed time is 0.041495 seconds.
</pre>
=={{header|Nim}}==
Line 3,007 ⟶ 3,339:
<pre>
[[4, 13]]
</pre>
=={{header|Rust}}==
{{trans|Julia}}
<syntaxhighlight lang="rust">use primes::is_prime;
fn satisfy1(x: u64) -> bool {
let upper_limit = (x as f64).sqrt() as u64 + 1;
for i in 2..upper_limit {
if is_prime(i) && is_prime(x - i) {
return false;
}
}
return true;
}
fn satisfy2(x: u64) -> bool {
let mut once: bool = false;
let upper_limit = (x as f64).sqrt() as u64 + 1;
for i in 2..upper_limit {
if x % i == 0 {
let j = x / i;
if 2 < j && j < 100 && satisfy1(i + j) {
if once {
return false;
}
once = true;
}
}
}
return once
}
fn satisfyboth(x: u64) -> u64 {
if !satisfy1(x) {
return 0;
}
let mut found = 0;
for i in 2..=(x/2) {
if satisfy2(i * (x - i)) {
if found > 0 {
return 0;
}
found = i;
}
}
return found;
}
fn main() {
for i in 2..100 {
let j = satisfyboth(i);
if j > 0 {
println!("Solution: ({}, {})", j, i - j);
}
}
}
</syntaxhighlight>{{out}}
<pre>
Solution: (4, 13)
</pre>
Line 3,120 ⟶ 3,512:
{{libheader|Wren-dynamic}}
{{libheader|Wren-seq}}
<syntaxhighlight lang="
import "./seq" for Lst
var P = Tuple.create("P", ["x", "y", "sum", "prod"])
| |||