Sum and product puzzle: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added (efficient) code for Matlab) |
||
Line 1,733: | Line 1,733: | ||
1 candidates |
1 candidates |
||
a=4, b=13; S=17, P=52</pre> |
a=4, b=13; S=17, P=52</pre> |
||
=={{header|Matlab}}== |
|||
<syntaxhighlight lang="Matlab"> |
|||
function SumProductPuzzle(maxSum, m) |
|||
% SumProductPuzzle(maxSum=100, m=2) |
|||
% Efficiently solve the Sum and Product puzzle. |
|||
% No solution if maxSum < 65; multiple solutions if maxSum >= 1685. |
|||
if nargin<2 |
|||
m = 2; % minimum number |
|||
if nargin<1 |
|||
maxSum = 100; |
|||
end |
|||
end |
|||
%Step 1: Determine viable sums; i.e. sums for which all possibilities have |
|||
% non-unique products |
|||
productCount = zeros(1,floor((maxSum/2)^2)); % Memory hog |
|||
for i = m:(maxSum/2-1) |
|||
j = i+1:maxSum-i; |
|||
ij = i*j; |
|||
productCount(ij) = productCount(ij) +1; |
|||
end |
|||
viableSum = true(1,maxSum); |
|||
viableSum(1:2*m) = false; |
|||
for s = 2*m+1:maxSum |
|||
i = m:(s-1)/2; |
|||
j = s-i; |
|||
if any(productCount(i.*j) == 1) |
|||
viableSum(s) = false; |
|||
end |
|||
end |
|||
tmp = 1:maxSum; |
|||
sums = tmp(viableSum); |
|||
N1 = sum(floor((sums+1)/2) - m); |
|||
fprintf( 1, 'After step 1: %d viable sums (%d total possibilities).\n', length(sums), N1 ); |
|||
%Step 2: Determine which possibilities now have unique products |
|||
productCount = zeros(1,floor((maxSum/2)^2)); |
|||
for s = sums |
|||
i = m:(s-1)/2; |
|||
j = s-i; |
|||
ij = i.*j; |
|||
productCount(ij) = productCount(ij) +1; |
|||
end |
|||
A = zeros(2,N1); %Pre-allocate for speed |
|||
n = 1; |
|||
for s = sums |
|||
i = m:(s-1)/2; |
|||
j = s-i; |
|||
ii = productCount(i.*j) == 1; |
|||
ij = [i(ii); j(ii)]; |
|||
nn = n + size(ij,2); |
|||
A(:,n:nn-1) = ij; |
|||
n = nn; |
|||
end |
|||
A(:,nn:end) = []; |
|||
fprintf( 1, 'After step 2: %d possibilities.\n', size(A,2) ); |
|||
%Step 3: Narrow down to pairs that have unique sums. |
|||
% Since the values are in sum order, just check the neighbor's sum. |
|||
d = diff(sum(A))==0; |
|||
ii = [d false] | [false d]; |
|||
A(:,ii) = []; |
|||
switch size(A,2) |
|||
case 0 |
|||
fprintf(1,'No solution.\n'); |
|||
case 1 |
|||
fprintf(1,'Puzzle solved! The numbers are %d and %d.\n', A(1:2)); |
|||
otherwise |
|||
fprintf(1,'After step 3 there are still multiple possibilities:'); |
|||
fprintf(1,' (%d, %d)', A(1:2,:)); |
|||
fprintf(1,'\n'); |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
>> tic; SumProductPuzzle; toc |
|||
After step 1: 10 viable sums (145 total possibilities). |
|||
After step 2: 86 possibilities. |
|||
Puzzle solved! The numbers are 4 and 13. |
|||
Elapsed time is 0.004797 seconds. |
|||
>> tic; SumProductPuzzle(1685); toc |
|||
After step 1: 235 viable sums (51011 total possibilities). |
|||
After step 2: 17567 possibilities. |
|||
After step 3 there are still multiple possibilities: (4, 13) (4, 61) |
|||
Elapsed time is 0.038874 seconds. |
|||
>> tic; SumProductPuzzle(1970); toc |
|||
After step 1: 278 viable sums (70475 total possibilities). |
|||
After step 2: 23985 possibilities. |
|||
After step 3 there are still multiple possibilities: (4, 13) (4, 61) (16, 73) |
|||
Elapsed time is 0.041495 seconds. |
|||
</pre> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |