Sum to 100: Difference between revisions
m
Minor edit to Rust code
m (Minor edit to Rust code) |
|||
| (120 intermediate revisions by 38 users not shown) | |||
Line 3:
;Task:
Find solutions to the <big> ''sum to one hundred'' </big> puzzle.
Add (insert) the mathematical
operators <big> '''+''' </big> or <big><big> '''
or minus) before any of the digits in the
<br>decimal numeric string <big> '''123456789''' </big> such that the
Line 15:
Example:
<big> <big> <b> <big> 123 + 4 - 5 + 67 - 89 = 100 </big> </b> </big> </big>
Show all output here.
Line 21:
:* Show all solutions that sum to <big> '''100''' </big>
:* Show the sum that has the maximum ''number'' of solutions (from zero to infinity<sup>
:* Show the lowest positive sum that ''can't'' be expressed (has no solutions), using the rules for this task
:* Show the ten highest numbers that can be expressed using the rules for this task (extra credit)
<br>
<sup><big>‡</big></sup> (where ''infinity'' would be a relatively small 123,456,789)
An example of a sum that can't be expressed (within the rules of this task) is: '''5074'''
<
<br><br>
=={{header|11l}}==
{{trans|Kotlin}}
<syntaxhighlight lang="11l">-V
NUMBER_OF_DIGITS = 9
THREE_POW_4 = 3 * 3 * 3 * 3
NUMBER_OF_EXPRESSIONS = 2 * THREE_POW_4 * THREE_POW_4
T.enum Op
ADD
SUB
JOIN
T Expression
code = [Op.ADD] * :NUMBER_OF_DIGITS
F inc()
L(i) 0 .< .code.len
.code[i] = Op((Int(.code[i]) + 1) % 3)
I .code[i] != ADD
L.break
F toInt()
V value = 0
V number = 0
V sign = 1
L(digit) 1..9
V c = .code[:NUMBER_OF_DIGITS - digit]
I c == ADD {value += sign * number; number = digit; sign = 1}
E I c == SUB {value += sign * number; number = digit; sign = -1}
E {number = 10 * number + digit}
R value + sign * number
F String()
V s = ‘’
L(digit) 1 .. :NUMBER_OF_DIGITS
V c = .code[:NUMBER_OF_DIGITS - digit]
I c == ADD
I digit > 1
s ‘’= ‘ + ’
E I c == SUB
s ‘’= ‘ - ’
s ‘’= String(digit)
R s.ltrim(‘ ’)
F printe(givenSum)
V expression = Expression()
L 0 .< :NUMBER_OF_EXPRESSIONS
I expression.toInt() == givenSum
print(‘#9’.format(givenSum)‘ = ’expression)
expression.inc()
T Stat
DefaultDict[Int, Int] countSum
DefaultDict[Int, Set[Int]] sumCount
F ()
V expression = Expression()
L 0 .< :NUMBER_OF_EXPRESSIONS
V sum = expression.toInt()
.countSum[sum]++
expression.inc()
L(k, v) .countSum
.sumCount[v].add(k)
print("100 has the following solutions:\n")
printe(100)
V stat = Stat()
V maxCount = max(stat.sumCount.keys())
V maxSum = max(stat.sumCount[maxCount])
print("\n#. has the maximum number of solutions, namely #.".format(maxSum, maxCount))
V value = 0
L value C stat.countSum
value++
print("\n#. is the lowest positive number with no solutions".format(value))
print("\nThe ten highest numbers that do have solutions are:\n")
L(i) sorted(stat.countSum.keys(), reverse' 1B)[0.<10]
printe(i)</syntaxhighlight>
{{out}}
<pre>
100 has the following solutions:
100 = 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
100 = 1 + 2 + 34 - 5 + 67 - 8 + 9
100 = 1 + 23 - 4 + 5 + 6 + 78 - 9
100 = 1 + 23 - 4 + 56 + 7 + 8 + 9
100 = 12 + 3 + 4 + 5 - 6 - 7 + 89
100 = 12 + 3 - 4 + 5 + 67 + 8 + 9
100 = 12 - 3 - 4 + 5 - 6 + 7 + 89
100 = 123 + 4 - 5 + 67 - 89
100 = 123 + 45 - 67 + 8 - 9
100 = 123 - 4 - 5 - 6 - 7 + 8 - 9
100 = 123 - 45 - 67 + 89
100 = - 1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
9 has the maximum number of solutions, namely 46
211 is the lowest positive number with no solutions
The ten highest numbers that do have solutions are:
123456789 = 123456789
23456790 = 1 + 23456789
23456788 = - 1 + 23456789
12345687 = 12345678 + 9
12345669 = 12345678 - 9
3456801 = 12 + 3456789
3456792 = 1 + 2 + 3456789
3456790 = - 1 + 2 + 3456789
3456788 = 1 - 2 + 3456789
3456786 = - 1 - 2 + 3456789
</pre>
=={{header|Ada}}==
Line 38 ⟶ 155:
Between any two consecutive digits, there can be a "+", a "-", or no operator. E.g., the digits "4" and "5" occur in the string as either of the following three substrings: "4+5", "4-5", or "45". For the first digit, we only have two choices: "+1" (written as "1"), and "-1". This makes 2*3^8 (two times (three to the power of eight)) different strings. Essential is the generic function Eval in the package Sum_To calls the procedure Callback for each such string Str, with the number Int holding the sum corresponding to the evaluation of Str. The second generic procedure Print is for convenience. If the Sum fits the condition, i.e., if Print_If(Sum, Number), then Print writes Sum = Str to the output.
<
generic
Line 49 ⟶ 166:
procedure Print(S: String; Sum: Integer);
end Sum_To;</
The implementation of Eval follows the observation above: Eval calls Rec_Eval with the initial string "1" and "-1". For each call, Rec_Eval recursively evaluates a ternary tree with 3^8 leafs. At each leaf, Rec_Eval calls Callback. The implementation of Print is straightforward.
<
package body Sum_To is
Line 92 ⟶ 209:
end Print;
end Sum_To;</
===The First Subtask===
Line 98 ⟶ 215:
Given the package Sum_To, the solution to the first subtask (print all solution for the sum 100) is trivial: Eval_100 calls Print_100 for all 2*3^8 strings, and Print_100 writes the output if the sum is equal to 100.
<
procedure Sum_To_100 is
Line 107 ⟶ 224:
begin
Eval_100;
end Sum_To_100;</
{{out}}
Line 127 ⟶ 244:
For the three other subtasks, we maintain an ordered map of sums (as the keys) and counters for the number of solutions (as the elements). The procedure Generate_Map generates the Map by calling the procedure Insert_Solution for all 2*3^8 solutions. Finding (1) the sum with the maximal number of solutions, (2) the first sum>=0 without a solution and (3) the ten largest sums with a solution (extra credit) are done by iterating this map.
<
use Ada.Text_IO;
Line 193 ⟶ 310:
end loop;
New_Line;
end Three_others;</
{{out}}
Line 203 ⟶ 320:
Highest sum: 123456789
Next nine: 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786</pre>
=={{header|Aime}}==
<syntaxhighlight lang="aime">integer b, i, j, k, l, p, s, z;
index r, w;
i = 0;
while (i < 512) {
b = i.bcount;
j = 0;
while (j < 1 << b) {
data e;
j += 1;
k = s = p = 0;
l = j;
z = 1;
while (k < 9) {
if (i & 1 << k) {
e.append("-+"[l & 1]);
s += p * z;
z = (l & 1) * 2 - 1;
l >>= 1;
p = 0;
}
e.append('1' + k);
p = p * 10 + 1 + k;
k += 1;
}
s += p * z;
if (e[0] != '+') {
if (s == 100) {
o_(e, "\n");
}
w[s] += 1;
}
}
i += 1;
}
w.wcall(i_fix, 1, 1, r);
o_(r.back, "\n");
k = 0;
for (+k in w) {
if (!w.key(k + 1)) {
o_(k + 1, "\n");
break;
}
}
i = 10;
for (k of w) {
o_(k, "\n");
if (!(i -= 1)) {
break;
}
}</syntaxhighlight>
{{Out}}
<pre>123-45-67+89
123+4-5+67-89
12+3+4+5-6-7+89
12-3-4+5-6+7+89
1+23-4+5+6+78-9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9
123+45-67+8-9
1+2+34-5+67-8+9
12+3-4+5+67+8+9
1+23-4+56+7+8+9
123-4-5-6-7+8-9
9
211
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786</pre>
=={{header|ALGOL 68}}==
<
# find the numbers the string 123456789 ( with "+/-" optionally inserted #
# before each digit ) can generate #
Line 232 ⟶ 438:
# we don't distinguish between strings starting "+1" and starting " 1" #
FOR s1 FROM -1 TO 0 DO
IF number >= LWB solutions
solutions[ number ] +:= ";"
count [
BOOL inserted
FOR l pos FROM LWB largest TO UPB largest
IF number > largest[ l pos
# found a
FOR m pos FROM UPB largest BY
largest [ m
largest
largest
largest count[ l pos ] :=
ELIF number
# have another way of generating this number
largest
inserted :=
OD
OD
OD
OD
OD
OD
OD
OD
OD;
Line 317 ⟶ 521:
FI
OD;
print( ( whole( number with max, 0 ), " has the maximum number of solutions: "
print( ( whole( max solutions, 0 ), newline ) );
# find the smallest positive number that has no solutions #
BOOL have solutions := TRUE;
Line 335 ⟶ 540:
print( ( newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
Line 360 ⟶ 566:
{{Trans|JavaScript}}
AppleScript is essentially out of its depth at this scale. The first task (number of distinct paths to 100) is accessible within a few seconds. Subsequent tasks, however, terminate only (if at all) after impractical amounts of time. Note the contrast with the lighter and more optimised JavaScript interpreter, which takes less than half a second to return full results for all the listed tasks.
<
property pSigns : {1, 0, -1} --> ( + | unsigned | - )
Line 372 ⟶ 578:
on asSum(xs)
script
on
if sign ≠ 0 then
{digits:{}, n:(n of a) + (sign * ((i & digits of a) as string as integer))}
Line 378 ⟶ 584:
{digits:{i} & (digits of a), n:n of a}
end if
end
end script
Line 394 ⟶ 600:
on asString(xs)
script
on
set d to i as string
if sign ≠ 0 then
Line 405 ⟶ 611:
a & d
end if
end
end script
Line 434 ⟶ 640:
script groupLength
on
set intA to length of a
set intB to length of b
Line 444 ⟶ 650:
0
end if
end
end script
set lstMaxSum to maximumBy(groupLength, plstSumGroups)
intercalate(linefeed,
{"Most common sum: " & item 1 of lstMaxSum, ¬
"Number of instances: " & length of lstMaxSum})
end mostCommonSum
Line 487 ⟶ 695:
script nextDigit
on
set {divided, remainder} to quotRem(residue, intBase)
{valid:divided > 0, value:(item (remainder + 1) of xs), new:divided}
end
end script
Line 507 ⟶ 715:
set cmp to mReturn(f)
script max
on
if a is missing value or cmp's
b
else
a
end if
end
end script
Line 522 ⟶ 730:
on group(xs)
script eq
on
a = b
end
end script
Line 535 ⟶ 743:
script enGroup
on
if length of (active of a) > 0 then
set h to item 1 of active of a
Line 542 ⟶ 750:
end if
if h is not missing value and mf's
{active:(active of a) & x, sofar:sofar of a}
else
{active:{x}, sofar:(sofar of a) & {active of a}}
end if
end
end script
Line 605 ⟶ 813:
set lng to length of xs
repeat with i from lng to 1 by -1
set v to
end repeat
return v
Line 617 ⟶ 825:
set lng to length of xs
repeat with i from 1 to lng
set v to
end repeat
return v
Line 627 ⟶ 835:
set mf to mReturn(f)
set lst to {}
set recM to mf's
repeat while (valid of recM) is true
set end of lst to value of recM
set recM to mf's
end repeat
lst & value of recM
Line 641 ⟶ 849:
tell mReturn(f)
repeat until mp's
set v to
end repeat
end tell
return v
end |until|
-- map :: (a -> b) -> [a] -> [b]
Line 668 ⟶ 862:
set lst to {}
repeat with i from 1 to lng
set end of lst to
end repeat
return lst
Line 682 ⟶ 876:
else
script
property
end script
end if
end mReturn</
{{Out}}
<pre>Sums to 100:
Line 704 ⟶ 897:
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">output:=""
for k, v in (sum2num(100))
output .= k "`n"
MsgBox, 262144, , % output
mx := []
loop 123456789{
x := sum2num(A_Index)
mx[x.Count()] := mx[x.Count()] ? mx[x.Count()] ", " A_Index : A_Index
}
MsgBox, 262144, , % mx[mx.MaxIndex()] " has " mx.MaxIndex() " solutions"
loop {
if !sum2num(A_Index).Count(){
MsgBox, 262144, , % "Lowest positive sum that can't be expressed is " A_Index
break
}
}
return
sum2num(num){
output := []
loop % 6561
oper := SubStr("00000000" ConvertBase(10, 3, A_Index-1), -7)
oper := StrReplace(oper, 0, "+")
oper := StrReplace(oper, 1, "-")
oper := StrReplace(oper, 2, ".")
str := ""
loop 9
str .= A_Index . SubStr(oper, A_Index, 1)
str := StrReplace(str, ".")
loop 2
{
val := 0
for i, v in StrSplit(str, "+")
for j, m in StrSplit(v, "-")
val += A_Index=1 ? m : 0-m
output[str] := true
str := "-" str
}
}
Sort, output
return output
}
; https://www.autohotkey.com/boards/viewtopic.php?p=21143&sid=02b9c92ea98737f1db6067b80a2a59cd#p21143
ConvertBase(InputBase, OutputBase, nptr){
static u := A_IsUnicode ? "_wcstoui64" : "_strtoui64"
static v := A_IsUnicode ? "_i64tow" : "_i64toa"
VarSetCapacity(s, 66, 0)
value := DllCall("msvcrt.dll\" u, "Str", nptr, "UInt", 0, "UInt", InputBase, "CDECL Int64")
DllCall("msvcrt.dll\" v, "Int64", value, "Str", s, "UInt", OutputBase, "CDECL")
return s
}</syntaxhighlight>
{{out}}
<pre>
---------------------------
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
Line 747 ⟶ 967:
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
---------------------------
9 has 46 solutions
---------------------------
Lowest positive sum that can't be expressed is 211
---------------------------
</pre>
=={{header|AWK}}==
{{trans|Fortran IV}}
Awk is a weird language: there are no integers, no switch-case (in the standard language version), programs are controlled by data flow, the interpreter speed is moderate. The advantage of Awk are associative arrays, used here for counting how many times we get the same sum as the result of calculations.
<syntaxhighlight lang="awk">#
# RossetaCode: Sum to 100, AWK.
#
# Find solutions to the "sum to one hundred" puzzle.
function evaluate(code)
{
value = 0
number = 0
power = 1
for ( k = 9; k >= 1; k-- )
{
number = power*k + number
op = code % 3
if ( op == 0 ) {
value = value + number
number = 0
power = 1
} else if (op == 1 ) {
value = value - number
number = 0
power = 1
} else if ( op == 2) {
power = power * 10
} else {
}
code = int(code / 3);
}
return value;
}
function show(code)
{
s = ""
a = 19683
b = 6561
for ( k = 1; k <= 9; k++ )
{
op = int( (code % a) / b )
if ( op == 0 && k > 1 )
s = s "+"
else if ( op == 1 )
s = s "-"
else {
}
a = b
b = int(b / 3)
s = s k
}
printf "%9d = %s\n", evaluate(code), s;
}
BEGIN {
nexpr = 13122
print
print "Show all solutions that sum to 100"
print
for ( i = 0; i < nexpr; i++ ) if ( evaluate(i) == 100 ) show(i);
print
print "Show the sum that has the maximum number of solutions"
print
for ( i = 0; i < nexpr; i++ ) {
sum = evaluate(i);
if ( sum >= 0 )
stat[sum]++;
}
best = (-1);
for ( sum in stat )
if ( best < stat[sum] ) {
best = stat[sum]
bestSum = sum
}
delete stat
printf "%d has %d solutions\n", bestSum, best
print
print "Show the lowest positive number that can't be expressed"
print
for ( i = 0; i <= 123456789; i++ ){
for ( j = 0; j < nexpr; j++ )
if ( i == evaluate(j) )
break;
if ( i != evaluate(j) )
break;
}
printf "%d\n",i
print
print "Show the ten highest numbers that can be expressed"
print
limit = 123456789 + 1;
for ( i = 1; i <= 10; i++ )
{
best = 0;
for ( j = 0; j < nexpr; j++ )
{
test = evaluate(j);
if ( test < limit && test > best ) best = test;
}
for ( j = 0; j < nexpr; j++ ) if ( evaluate(j) == best ) show(j)
limit = best
}
}</syntaxhighlight>
{{Out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|C}}==
=== Optimized for speed ===
{{Works with|GCC|5.1}}
{{Works with|Microsoft Visual Studio|2015}}
Warning: '''this version requires at least four byte integers.'''
<syntaxhighlight lang="c">/*
* RossetaCode: Sum to 100, C99, an algorithm using ternary numbers.
*
Line 757 ⟶ 1,133:
*/
#include <stdio.h>
#include <stdlib.h>
Line 765 ⟶ 1,141:
*/
#define NUMBER_OF_EXPRESSIONS (2 * 3*3*3*3 * 3*3*3*3 )
enum OP { ADD, SUB, JOIN };
typedef int (*cmp)(const void*, const void*);
// Replacing struct Expression and struct CountSum by a tuple like
// struct Pair { int first; int last; } is possible but would make the source
// code less readable.
struct Expression{
Line 773 ⟶ 1,153:
}expressions[NUMBER_OF_EXPRESSIONS];
int expressionsLength = 0;
int compareExpressionBySum(const struct Expression* a, const struct Expression* b){
return a->sum - b->sum;
}
struct
int counts;
int sum;
}
int
int compareCountSumsByCount(const struct CountSum* a, const struct CountSum* b){
return a->counts - b->counts;
}
int
int value = 0, number = 0, power = 1;
for ( int
case SUB: value = value - number; number = 0; power = 1; break;
case JOIN: power = power * 10 ; break;
}
}
return value;
}
void print(int code){
static char s[19]; char* p = s;
int a = 19683, b = 6561;
case
}
b = b / 3;
*p++ = '0' + k;
}
*
printf("%9d = %s\n", evaluate(code), s);
}
void comment(char* string){
printf("\n\n%s\n\n", string);
}
void
for ( int i = 0; i < NUMBER_OF_EXPRESSIONS; i++ ){
expressions[i].sum =
expressions[i].code = i;
}
expressionsLength = NUMBER_OF_EXPRESSIONS;
qsort(expressions,expressionsLength,sizeof(struct Expression),
int j = 0;
for ( int i = 0; i < expressionsLength; i++ ){
if (
j++;
}
else
}
qsort(
}
int main(void){
init();
comment("Show all solutions that sum to 100");
const int givenSum = 100;
struct Expression ex = { givenSum, 0 };
struct Expression* found;
if ( found = bsearch(&ex,expressions,expressionsLength,
sizeof(struct Expression),(cmp)compareExpressionBySum) ){
while ( found != expressions && (found-1)->sum == givenSum )
found--;
while ( found != &expressions[expressionsLength] && found->sum == givenSum )
print(found++->code);
}
int maxSumIndex =
while(
maxSumIndex--;
printf("%d has %d solutions\n",
for ( int value = 0; ; value++ ){
struct Expression ex = { value, 0 };
if (!bsearch(&ex,expressions,expressionsLength,
sizeof(struct Expression),
printf("%d\n", value);
break;
Line 899 ⟶ 1,257:
}
for ( int i = expressionsLength-1; i >= expressionsLength-10; i-- )
return 0;
}</
{{Out}}
<pre>
Line 947 ⟶ 1,305:
</pre>
===Optimized for memory consumption ===
{{trans | Fortran 95}}
{{Works with|GCC|5.1}}
Warning: '''this program needs at least four byte integers'''.
<syntaxhighlight lang="c">/*
* RossetaCode: Sum to 100, C11, MCU friendly.
*
* Find solutions to the "sum to one hundred" puzzle.
*
* We optimize algorithms for size. Therefore we don't use arrays, but recompute
* all values again and again. It is a little surprise that the time efficiency
* is quite acceptable.
*/
#include <stdio.h>
enum OP { ADD, SUB, JOIN };
int evaluate(int code){
int value =
for ( int k = 9; k >= 1; k-- ){
number = power*k + number;
case ADD: value = value + number; number = 0; power = 1; break;
case JOIN: power =
}
code /= 3;
}
return value;
}
void print(int code){
static char s[19]; char* p = s;
for ( int k = 1; k <= 9; k++ ){
}
a =
b = b / 3;
*p++ = '0' + k;
}
*p = 0;
printf("%9d = %s\n", evaluate(code), s);
}
int main(void){
int i,j;
const int nexpr = 13122;
#define LOOP(K) for (K = 0; K < nexpr; K++)
puts("\nShow all solutions that sum to 100\n");
LOOP(i) if ( evaluate(i) == 100 ) print(i);
int test = evaluate(i);
if ( test > 0 ){
int ntest = 0;
LOOP(j) if ( evaluate(j) == test ) ntest++;
}
}
printf("%d has %d solutions\n", best,nbest);
puts("\nShow the lowest positive number that can't be expressed\n");
for ( i = 0; i <= 123456789; i++ ){
LOOP(j) if ( i == evaluate(j) ) break;
if ( i != evaluate(j) ) break;
}
printf("%d\n",i);
puts("\nShow the ten highest numbers that can be expressed\n");
int limit = 123456789 + 1;
for ( i = 1; i <= 10; i++ ) {
int best = 0;
LOOP(j){
int test = evaluate(j);
if ( test < limit && test > best ) best = test;
}
LOOP(j) if ( evaluate(j) == best ) print(j);
limit = best;
}
return 0;
}</
{{Out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
Line 1,100 ⟶ 1,434:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
using System.Linq;
Line 1,226 ⟶ 1,560:
return left;
}
}</
{{out}}
<pre>
Line 1,257 ⟶ 1,591:
3456788
3456786
</pre>
=={{header|C++}}==
{{Works with|GCC|5.1}}
{{Works with|Microsoft Visual Studio|2010}}
For each expression of sum s, there is at least one expression whose sum is -s. If the sum s can be represented by n expressions, the sum -s can also be represented by n expressions. The change of all signs in an expression change the sign of the sum of this expression. For example, -1+23-456+789 has the opposite sign than +1-23+456-789. Therefore only the positive sum with the maximum number of solutions is shown. The program does not check uniqueness of this sum. We can easily check (modifying the program) that: sum 9 has 46 solutions; sum -9 has 46 solutions; any other sum has less than 46 solutions.
<syntaxhighlight lang="cpp">/*
* RossetaCode: Sum to 100, C++, STL, OOP.
* Works with: MSC 16.0 (MSVS2010); GCC 5.1 (use -std=c++11 or -std=c++14 etc.).
*
* Find solutions to the "sum to one hundred" puzzle.
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
class Expression{
private:
enum { NUMBER_OF_DIGITS = 9 }; // hack for C++98, use const int in C++11
enum Op { ADD, SUB, JOIN };
int code[NUMBER_OF_DIGITS];
public:
static const int NUMBER_OF_EXPRESSIONS;
Expression(){
for ( int i = 0; i < NUMBER_OF_DIGITS; i++ )
code[i] = ADD;
}
Expression& operator++(int){ // post incrementation
for ( int i = 0; i < NUMBER_OF_DIGITS; i++ )
if ( ++code[i] > JOIN ) code[i] = ADD;
else break;
return *this;
}
operator int() const{
int value = 0, number = 0, sign = (+1);
for ( int digit = 1; digit <= 9; digit++ )
switch ( code[NUMBER_OF_DIGITS - digit] ){
case ADD: value += sign*number; number = digit; sign = (+1); break;
case SUB: value += sign*number; number = digit; sign = (-1); break;
case JOIN: number = 10*number + digit; break;
}
return value + sign*number;
}
operator string() const{
string s;
for ( int digit = 1; digit <= NUMBER_OF_DIGITS; digit++ ){
switch( code[NUMBER_OF_DIGITS - digit] ){
case ADD: if ( digit > 1 ) s.push_back('+'); break;
case SUB: s.push_back('-'); break;
}
s.push_back('0' + digit);
}
return s;
}
};
const int Expression::NUMBER_OF_EXPRESSIONS = 2 * 3*3*3*3 * 3*3*3*3;
ostream& operator<< (ostream& os, Expression& ex){
ios::fmtflags oldFlags(os.flags());
os << setw(9) << right << static_cast<int>(ex) << " = "
<< setw(0) << left << static_cast<string>(ex) << endl;
os.flags(oldFlags);
return os;
}
struct Stat{
map<int,int> countSum;
map<int, set<int> > sumCount;
Stat(){
Expression expression;
for ( int i = 0; i < Expression::NUMBER_OF_EXPRESSIONS; i++, expression++ )
countSum[expression]++;
for ( auto it = countSum.begin(); it != countSum.end(); it++ )
sumCount[it->second].insert(it->first);
}
};
void print(int givenSum){
Expression expression;
for ( int i = 0; i < Expression::NUMBER_OF_EXPRESSIONS; i++, expression++ )
if ( expression == givenSum )
cout << expression;
}
void comment(string commentString){
cout << endl << commentString << endl << endl;
}
int main(){
Stat stat;
comment( "Show all solutions that sum to 100" );
const int givenSum = 100;
print(givenSum);
comment( "Show the sum that has the maximum number of solutions" );
auto maxi = max_element(stat.sumCount.begin(),stat.sumCount.end());
auto it = maxi->second.begin();
while ( *it < 0 ) it++;
cout << static_cast<int>(*it) << " has " << maxi->first << " solutions" << endl;
comment( "Show the lowest positive number that can't be expressed" );
int value = 0;
while(stat.countSum.count(value) != 0) value++;
cout << value << endl;
comment( "Show the ten highest numbers that can be expressed" );
auto rit = stat.countSum.rbegin();
for ( int i = 0; i < 10; i++, rit++ ) print(rit->first);
return 0;
}</syntaxhighlight>
{{Out}}
<pre>
Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
=={{header|Common Lisp}}==
<syntaxhighlight lang="lisp">(defun f (lst &optional (sum 100) (so-far nil))
"Takes a list of digits as argument"
(if (null lst)
(cond ((= sum 0) (format t "~d = ~{~@d~}~%" (apply #'+ so-far) (reverse so-far)) 1)
(t 0) )
(let ((total 0)
(len (length lst)) )
(dotimes (i len total)
(let* ((str1 (butlast lst i))
(num1 (or (numlist-to-string str1) 0))
(rem (nthcdr (- len i) lst)) )
(incf total
(+ (f rem (- sum num1) (cons num1 so-far))
(f rem (+ sum num1) (cons (- num1) so-far)) )))))))
(defun numlist-to-string (lst)
"Convert a list of digits into an integer"
(when lst
(parse-integer (format nil "~{~d~}" lst)) ))
</syntaxhighlight>
{{out}}
<pre>
>(f '(1 2 3 4 5 6 7 8 9))
100 = +123+45-67+8-9
100 = +123-45-67+89
100 = +123+4-5+67-89
100 = +123-4-5-6-7+8-9
100 = +12+3+4+5-6-7+89
100 = +12+3-4+5+67+8+9
100 = +12-3-4+5-6+7+89
100 = +1+23-4+56+7+8+9
100 = +1+23-4+5+6+78-9
100 = +1+2+34-5+67-8+9
100 = +1+2+3-4+5+6+78+9
100 = -1+2-3+4+5+6+78+9
12
</pre>
The other subtasks are not yet implemented.
=={{header|D}}==
{{Trans|Java}}
<syntaxhighlight lang="d">import std.stdio;
void main() {
import std.algorithm : each, max, reduce, sort;
import std.range : take;
Stat stat = new Stat();
comment("Show all solutions that sum to 100");
immutable givenSum = 100;
print(givenSum);
comment("Show the sum that has the maximum number of solutions");
const int maxCount = reduce!max(stat.sumCount.keys);
int maxSum;
foreach(key, entry; stat.sumCount[maxCount]) {
if (key >= 0) {
maxSum = key;
break;
}
}
writeln(maxSum, " has ", maxCount, " solutions");
comment("Show the lowest positive number that can't be expressed");
int value = 0;
while (value in stat.countSum) {
value++;
}
writeln(value);
comment("Show the ten highest numbers that can be expressed");
const int n = stat.countSum.keys.length;
auto sums = stat.countSum.keys;
sums.sort!"a>b"
.take(10)
.each!print;
}
void comment(string commentString) {
writeln();
writeln(commentString);
writeln();
}
void print(int givenSum) {
Expression expression = new Expression();
for (int i=0; i<Expression.NUMBER_OF_EXPRESSIONS; i++, expression.next()) {
if (expression.toInt() == givenSum) {
expression.print();
}
}
}
class Expression {
private enum NUMBER_OF_DIGITS = 9;
private enum ADD = 0;
private enum SUB = 1;
private enum JOIN = 2;
enum NUMBER_OF_EXPRESSIONS = 2 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3;
byte[NUMBER_OF_DIGITS] code;
Expression next() {
for (int i=0; i<NUMBER_OF_DIGITS; i++) {
if (++code[i] > JOIN) {
code[i] = ADD;
} else {
break;
}
}
return this;
}
int toInt() {
int value = 0;
int number = 0;
int sign = (+1);
for (int digit=1; digit<=9; digit++) {
switch (code[NUMBER_OF_DIGITS - digit]) {
case ADD:
value += sign * number;
number = digit;
sign = (+1);
break;
case SUB:
value += sign * number;
number = digit;
sign = (-1);
break;
case JOIN:
number = 10 * number + digit;
break;
default:
assert(false);
}
}
return value + sign * number;
}
void toString(scope void delegate(const(char)[]) sink) const {
import std.conv : to;
import std.format : FormatSpec, formatValue;
import std.range : put;
auto fmt = FormatSpec!char("s");
for (int digit=1; digit<=NUMBER_OF_DIGITS; digit++) {
switch (code[NUMBER_OF_DIGITS - digit]) {
case ADD:
if (digit > 1) {
put(sink, '+');
}
break;
case SUB:
put(sink, '-');
break;
default:
break;
}
formatValue(sink, digit, fmt);
}
}
void print() {
print(stdout);
}
void print(File printStream) {
printStream.writefln("%9d = %s", toInt(), this);
}
}
class Stat {
int[int] countSum;
bool[int][int] sumCount;
this() {
Expression expression = new Expression();
for (int i=0; i<Expression.NUMBER_OF_EXPRESSIONS; i++, expression.next()) {
int sum = expression.toInt();
countSum[sum]++;
}
foreach (key, entry; countSum) {
bool[int] set;
if (entry in sumCount) {
set = sumCount[entry];
} else {
set.clear();
}
set[key] = true;
sumCount[entry] = set;
}
}
}</syntaxhighlight>
{{out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Sum_to_100#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
ADD = 0
SUB = 1
nexpr = 13122 - 1
len f[] nexpr + 1
arrbase f[] 0
#
func evaluate code .
power = 1
for k = 9 downto 1
numb += power * k
m = code mod 3
if m = ADD
value += numb
numb = 0
power = 1
elif m = SUB
value -= numb
numb = 0
power = 1
else
power *= 10
.
code = code div 3
.
return value
.
proc init . .
for i = 0 to nexpr
f[i] = evaluate i
.
.
call init
proc out code . .
a = 19683
b = 6561
for k = 1 to 9
h = code mod a div b
if h = ADD
if k > 1
s$ &= "+"
.
elif h = SUB
s$ &= "-"
.
a = b
b = b div 3
s$ &= strchar (48 + k)
.
print evaluate code & " = " & s$
.
print "Show all solutions that sum to 100\n"
for i = 0 to nexpr
if f[i] = 100
out i
.
.
print "\nShow the sum that has the maximum number of solutions\n"
for i = 0 to nexpr
test = f[i]
if test > 0
ntest = 0
for j = 0 to nexpr
if f[j] = test
ntest += 1
.
.
if ntest > nbest
best = test
nbest = ntest
.
.
.
print best & " has " & nbest & " solutions"
print "\nShow the lowest positive number that can't be expressed\n"
for i = 0 to 123456789
for j = 0 to nexpr
if i = f[j]
break 1
.
.
if j > nexpr
break 1
.
.
print i
print "\nShow the ten highest numbers that can be expressed\n"
limit = 123456789 + 1
for i = 1 to 10
best = 0
for j = 0 to nexpr
test = f[j]
if test < limit and test > best
best = test
.
.
for j = 0 to nexpr
if f[j] = best
out j
.
.
limit = best
.
</syntaxhighlight>
{{out}}
<pre>
Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
=={{header|Elixir}}==
<
def to(val) do
generate
Line 1,305 ⟶ 2,177:
Sum.max_solve
Sum.min_solve
Sum.highest_sums</
{{out}}
Line 1,329 ⟶ 2,201:
=={{header|F_Sharp|F#}}==
<
(*
Generate the data set
Line 1,348 ⟶ 2,220:
yield! fn -1 2 0 -1 "-1"
}
</syntaxhighlight>
{{out}}
<
N |> Seq.filter(fun n->n.g=100) |> Seq.iter(fun n->printfn "%s" n.n)
</syntaxhighlight>
<pre>
1+2+3-4+5+6+78+9
Line 1,367 ⟶ 2,239:
-1+2-3+4+5+6+78+9
</pre>
<
let n,g = N |> Seq.filter(fun n->n.g>=0) |> Seq.countBy(fun n->n.g) |> Seq.maxBy(snd)
printfn "%d has %d solutions" n g
</syntaxhighlight>
<pre>
9 has 46 solutions
</pre>
<
match N |> Seq.filter(fun n->n.g>=0) |> Seq.distinctBy(fun n->n.g) |> Seq.sortBy(fun n->n.g) |> Seq.pairwise |> Seq.tryFind(fun n->(snd n).g-(fst n).g > 1) with
|Some(n) -> printfn "least non-value is %d" ((fst n).g+1)
|None -> printfn "No non-values found"
</syntaxhighlight>
<pre>
least non-value is 211
</pre>
<
N |> Seq.filter(fun n->n.g>=0) |> Seq.distinctBy(fun n->n.g) |> Seq.sortBy(fun n->(-n.g)) |> Seq.take 10 |> Seq.iter(fun n->printfn "%d" n.g )
</syntaxhighlight>
<pre>
123456789
Line 1,396 ⟶ 2,268:
3456788
3456786
</pre>
=={{header|Forth}}==
{{works with|Gforth|0.7.3}}
This solution uses <code>EVALUATE</code> on a string buffer to compute the sum. Given the copious string manipulations, <code>EVALUATE</code>, and the large byte-array used to keep sum counts, this implementation is optimized neither for speed nor for memory. On my machine it runs in about 3.8 seconds, compared to the speed-optimized C solution which runs in about 0.005 seconds.
<syntaxhighlight lang="forth">CREATE *OPS CHAR + C, CHAR - C, CHAR # C,
CREATE 0OPS CHAR - C, CHAR # C,
CREATE BUFF 43 C, 43 CHARS ALLOT
CREATE PTR CELL ALLOT
CREATE LIMITS 2 C, 3 C, 3 C, 3 C, 3 C, 3 C, 3 C, 3 C, 3 C,
CREATE INDX 0 C, 0 C, 0 C, 0 C, 0 C, 0 C, 0 C, 0 C, 0 C,
CREATE OPS 0OPS , *OPS , *OPS , *OPS , *OPS , *OPS , *OPS , *OPS , *OPS ,
: B0 BUFF 1+ dup PTR ! 43 blank ;
: B, ( c --) PTR @ C! 1 PTR +! ;
CREATE STATS 123456790 ALLOT STATS 123456790 ERASE
: inc ( c-addr c-lim u -- t|f)
1- tuck + >r swap dup rot + ( addr a-addr) ( R: l-addr)
BEGIN dup C@ 1+ dup r@ C@ =
IF drop 2dup =
IF 2drop FALSE rdrop EXIT \ no inc, contents invalid
ELSE 0 over C! 1- r> 1- >r \ reset and carry
THEN
ELSE swap C! drop TRUE rdrop EXIT
THEN
AGAIN ;
: INDX+ INDX LIMITS 9 inc 0= ;
: SYNTH B0 [CHAR] 0 B, 9 0 DO
INDX I + C@ OPS I CELLS + @ + C@
dup [CHAR] # <> IF BL B, B, BL B, ELSE drop THEN
I [CHAR] 1 + B,
LOOP BUFF COUNT ;
: .MOST cr ." Sum that has the maximum number of solutions" cr 4 spaces
STATS 0 STATS 1+ 123456789 bounds DO
dup I c@ < IF drop drop I I c@ THEN
LOOP swap STATS - . ." has " . ." solutions" ;
: .CANT cr ." Lowest positive sum that can't be expressed" cr 4 spaces
STATS 1+ ( 0 not positive) BEGIN dup c@ WHILE 1+ REPEAT STATS - . ;
: .BEST cr ." Ten highest numbers that can be expressed" cr 4 spaces
0 >r [ STATS 123456789 + ]L
BEGIN r@ 10 < over STATS >= and
WHILE dup c@ IF dup STATS - . r> 1+ >r THEN 1-
REPEAT r> drop ;
: . 0 <# #S #> TYPE ;
: .INFX cr 4 spaces 9 0 DO
INDX I + C@ OPS I cells + @ + C@
dup [char] # <> IF emit ELSE drop THEN I 1+ .
LOOP ;
: REPORT ( n) dup 100 = IF .INFX THEN
dup 0> IF STATS + dup c@ 1+ swap c! ELSE drop THEN ;
: >NUM 0. bl word count >number 2drop d>s ;
: # 10 * + ; \ numeric concatenation
: + >NUM + ; \ infix +
: - >NUM - ; \ infix -
: .SOLUTIONS cr ." Solutions that sum to 100:"
BEGIN SYNTH EVALUATE REPORT INDX+ UNTIL ;
: SUM100 .SOLUTIONS .MOST .CANT .BEST cr ;</syntaxhighlight>
{{Out}}
Note: must start Gforth with a larger-than-default dictionary size:
<pre>gforth -m 124M sum100.fs -e SUM100</pre>
<pre>Solutions that sum to 100:
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
Sum that has the maximum number of solutions
9 has 46 solutions
Lowest positive sum that can't be expressed
211
Ten highest numbers that can be expressed
123456789 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786</pre>
=={{header|Fortran}}==
=== Fortran IV ===
{{trans|Fortran 95}}
{{works with|gfortran|5.1}}
The program below is written in Fortran IV. Nevertheless, Fortran IV had a variety of dialects. It did not work the same on every type of computer. The source code below is compiled without problems using today's compilers. '''It have not been checked on any old mainframe.''' Sorry, I have no access to CDC6000. The algorithm used is not very fast, but uses little memory. In practice, this program took about 15 seconds to complete the task on PC (in 2017). For comparison: the program written in C ++ (using maps and STL collections) took about 1 second on the same machine.
<pre>C ROSSETACODE: SUM TO 100, FORTRAN IV
C FIND SOLUTIONS TO THE "SUM TO ONE HUNDRED" PUZZLE
C =================================================
PROGRAM SUMTO100
DATA NEXPRM1/13121/
WRITE(6,110)
110 FORMAT(1X/1X,34HSHOW ALL SOLUTIONS THAT SUM TO 100/)
DO 10 I = 0,NEXPRM1
10 IF ( IEVAL(I) .EQ. 100 ) CALL PREXPR(I)
WRITE(6,120)
120 FORMAT(1X/1X,
153HSHOW THE SUM THAT HAS THE MAXIMUM NUMBER OF SOLUTIONS/)
NBEST = -1
DO 30 I = 0, NEXPRM1
ITEST = IEVAL(I)
IF ( ITEST .LT. 0 ) GOTO 30
NTEST = 0
DO 20 J = 0, NEXPRM1
20 IF ( IEVAL(J) .EQ. ITEST ) NTEST = NTEST + 1
IF ( NTEST .LE. NBEST ) GOTO 30
IBEST = ITEST
NBEST = NTEST
30 CONTINUE
WRITE(6,121) IBEST, NBEST
121 FORMAT(1X,I8,5H HAS ,I8,10H SOLUTIONS/)
WRITE(6,130)
130 FORMAT(1X/1X,
155HSHOW THE LOWEST POSITIVE NUMBER THAT CAN'T BE EXPRESSED/)
DO 50 I = 0,123456789
DO 40 J = 0,NEXPRM1
40 IF ( I .EQ. IEVAL(J) ) GOTO 50
GOTO 60
50 CONTINUE
60 WRITE(6,131) I
131 FORMAT(1X,I8)
WRITE(6,140)
140 FORMAT(1X/1X,
150HSHOW THE TEN HIGHEST NUMBERS THAT CAN BE EXPRESSED/)
ILIMIT = 123456789
DO 90 I = 1,10
IBEST = 0
DO 70 J = 0, NEXPRM1
ITEST = IEVAL(J)
70 IF( (ITEST .LE. ILIMIT) .AND. (ITEST .GT. IBEST)) IBEST = ITEST
DO 80 J = 0, NEXPRM1
80 IF ( IEVAL(J) .EQ. IBEST ) CALL PREXPR(J)
90 ILIMIT = IBEST - 1
END
C EVALUATE THE VALUE OF THE GIVEN ENCODED EXPRESSION
C --------------------------------------------------
FUNCTION IEVAL(ICODE)
IC = ICODE
IEVAL = 0
N = 0
IP = 1
DO 50 K = 9,1,-1
N = IP*K + N
GOTO (10,20,40,30) MOD(IC,3)+1
10 IEVAL = IEVAL + N
GOTO 30
20 IEVAL = IEVAL - N
30 N = 0
IP = 1
GOTO 50
40 IP = IP * 10
50 IC = IC / 3
END
C PRINT THE ENCODED EXPRESSION IN THE READABLE FORMAT
C ---------------------------------------------------
SUBROUTINE PREXPR(ICODE)
DIMENSION IH(9),IHPMJ(4)
DATA IHPMJ/1H+,1H-,1H ,1H?/
IA = 19683
IB = 6561
DO 10 K = 1,9
IH(K) = IHPMJ(MOD(ICODE,IA) / IB+1)
IA = IB
10 IB = IB / 3
IVALUE = IEVAL(ICODE)
WRITE(6,110) IVALUE, IH
110 FORMAT(I9,3H = 1A1,1H1,1A1,1H2,1A1,1H3,1A1,1H4,1A1,1H5,1A1,1H6,1A1
1,1H7,1A1,1H8,1A1,1H9)
END</pre>
{{Out}}
<pre>SHOW ALL SOLUTIONS THAT SUM TO 100
100 = +1+2+3-4+5+6+7 8+9
100 = +1+2+3 4-5+6 7-8+9
100 = +1+2 3-4+5+6+7 8-9
100 = +1+2 3-4+5 6+7+8+9
100 = +1 2+3+4+5-6-7+8 9
100 = +1 2+3-4+5+6 7+8+9
100 = +1 2-3-4+5-6+7+8 9
100 = +1 2 3+4-5+6 7-8 9
100 = +1 2 3+4 5-6 7+8-9
100 = +1 2 3-4-5-6-7+8-9
100 = +1 2 3-4 5-6 7+8 9
100 = -1+2-3+4+5+6+7 8+9
SHOW THE SUM THAT HAS THE MAXIMUM NUMBER OF SOLUTIONS
9 HAS 46 SOLUTIONS
SHOW THE LOWEST POSITIVE NUMBER THAT CAN'T BE EXPRESSED
211
SHOW THE TEN HIGHEST NUMBERS THAT CAN BE EXPRESSED
123456789 = +1 2 3 4 5 6 7 8 9
23456790 = +1+2 3 4 5 6 7 8 9
23456788 = -1+2 3 4 5 6 7 8 9
12345687 = +1 2 3 4 5 6 7 8+9
12345669 = +1 2 3 4 5 6 7 8-9
3456801 = +1 2+3 4 5 6 7 8 9
3456792 = +1+2+3 4 5 6 7 8 9
3456790 = -1+2+3 4 5 6 7 8 9
3456788 = +1-2+3 4 5 6 7 8 9
3456786 = -1-2+3 4 5 6 7 8 9</pre>
=== Fortran 95 ===
{{works with|gfortran|5.1}}
<syntaxhighlight lang="fortran">! RossetaCode: Sum to 100, Fortran 95, an algorithm using ternary numbers.
!
! Find solutions to the 'sum to one hundred' puzzle.
!
! We optimize algorithms for size. Therefore we don't use arrays, but recompute
! all values again and again. It is a little surprise that the time efficiency
! is quite acceptable. Actually the code is more compact than the implementation
! in C++ (STL maps and sets). We purposely break DRY and use magic values.
! Nevertheless, it is Fortran 95, free form lines, do-endo etc.
program sumto100
parameter (nexpr = 13122)
print *
print *, 'Show all solutions that sum to 100'
print *
do i = 0, nexpr-1
if ( ievaluate(i) .eq. 100 ) then
call printexpr(i)
endif
enddo
print *
print *, 'Show the sum that has the maximum number of solutions'
print *
ibest = -1
nbest = -1
do i = 0, nexpr-1
itest = ievaluate(i)
if ( itest .ge. 0 ) then
ntest = 0
do j = 0, nexpr-1
if ( ievaluate(j) .eq. itest ) then
ntest = ntest + 1
endif
enddo
if ( (ntest .gt. nbest) ) then
ibest = itest
nbest = ntest
endif
endif
enddo
print *, ibest, ' has ', nbest, ' solutions'
print *
! do i = 0, nexpr-1
! if ( ievaluate(i) .eq. ibest ) then
! call printexpr(i)
! endif
! enddo
print *
print *, 'Show the lowest positive number that can''t be expressed'
print *
loop: do i = 0,123456789
do j = 0,nexpr-1
if ( i .eq. ievaluate(j) ) then
cycle loop
endif
enddo
exit
enddo loop
print *, i
print *
print *, 'Show the ten highest numbers that can be expressed'
print *
ilimit = 123456789
do i = 1,10
ibest = 0
do j = 0, nexpr-1
itest = ievaluate(j)
if ( (itest .le. ilimit) .and. (itest .gt. ibest ) ) then
ibest = itest
endif
enddo
do j = 0, nexpr-1
if ( ievaluate(j) .eq. ibest ) then
call printexpr(j)
endif
enddo
ilimit = ibest - 1;
enddo
end
function ievaluate(icode)
ic = icode
ievaluate = 0
n = 0
ip = 1
do k = 9,1,-1
n = ip*k + n
select case(mod(ic,3))
case ( 0 )
ievaluate = ievaluate + n
n = 0
ip = 1
case ( 1 )
ievaluate = ievaluate - n
n = 0
ip = 1
case ( 2 )
ip = ip * 10
end select
ic = ic / 3
enddo
end
subroutine printexpr(icode)
character(len=32) s
ia = 19683
ib = 6561
s = ""
do k = 1,9
ic = mod(icode,ia) / ib
ia = ib
ib = ib / 3
select case(mod(ic,3))
case ( 0 )
if ( k .gt. 1 ) then
s = trim(s) // '+'
endif
case ( 1 )
s = trim(s) // '-'
end select
s = trim(s) // char(ichar('0')+k)
end do
ivalue = ievaluate(icode)
print *, ivalue, ' = ', s
end</syntaxhighlight>
{{Out}}
<pre>
Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
===Batch processing===
By the simple expedient of storing all evaluations in an array (which is not so large) and then sorting the array, the required results appear in a blink. The source is essentially F77 except for the usage of an array assignment of OP = -1, writing out the highest ten results via an array expression instead of a DO-loop, array OPNAME extending from -1 to +1, a CYCLE statement rather than a GO TO, and the use of the I0 format code. Subroutine DEBLANK is straightforward, and omitted. It was only to remove spaces from the text of the expression. Reading the expression from right to left is about as picky as left-to-right. <syntaxhighlight lang="fortran"> INTEGER NDIGITS,TARGET !Document the shape.
PARAMETER (NDIGITS = 9, TARGET = 100)
INTEGER*1 OP(NDIGITS) !A set of operation codes, associated with each digit.
INTEGER N,D,P !Number, digit, power.
CHARACTER*1 OPNAME(-1:+1) !Encodement of the operations.
PARAMETER (OPNAME = (/"-"," ","+"/)) !These will look nice.
CHARACTER*20 TEXT !A scratchpad for the expression. Single digits only.
INTEGER I,L,H,ME !Assistants.
LOGICAL CURSE !Needed for a Comb Sort.
INTEGER LOOP,NHIT !Some counters.
INTEGER ENUFF !Collect the results.
PARAMETER (ENUFF = 20000) !Surely big enough...
INTEGER VALUE(ENUFF) !A table.
INTEGER V,VV,PV,VE !For scanning the table.
INTEGER MSG !I/O unit number.
MSG = 6 !Standard output.
WRITE(MSG,1) NDIGITS,TARGET !Announce.
1 FORMAT ("To find expressions of ",I0," digits in order, "
1 "interspersed with + or -, adding to ",I0,/)
NHIT = 0 !No matches to TARGET.
LOOP = 0 !Because none have been made.
OP = -1 !Start the expression sequence.
Calculate the value of the expression given by OP(i) i pairs.
100 LOOP = LOOP + 1 !Here we go again.
N = 0 !Clear the number.
D = 0 !No previous digits have been seen.
P = 1 !The power for the first digit.
DO I = NDIGITS,1,-1 !Going backwards sees the digits before the sign.
D = D + I*P !Assimilate the digit string backwards.
IF (OP(I).EQ.0) THEN !A no-operation?
P = P*10 !Yes. Prepare the power for the next digit leftwards.
ELSE !Otherwise, add or subtract the digit string's value.
N = N + SIGN(D,OP(I)) !By transferring the sign to D..
D = 0 !Clear, ready for the next digit string.
P = 1 !The starting power, again.
END IF !So much for that step.
END DO !On to the next.
IF (OP(1).EQ.0) N = N + D !Provide an implicit add for an unsigned start.
VALUE(LOOP) = N !Save the value for later...
IF (N.EQ.TARGET) THEN !Well then?
NHIT = NHIT + 1 !Yay!
WRITE (TEXT,101) (OPNAME(OP(I)),I, I = 1,NDIGITS) !Translate the expression.
101 FORMAT (10(A1,I1)) !Single-character operation codes, single-digit number parts.
CALL DEBLANK(TEXT,L) !Squeeze out the no-operations, so numbers are together.
WRITE (MSG,102) N,TEXT(1:L) !Result!
102 FORMAT (I5,": ",A) !This should do.
END IF !So much for that.
Concoct the next expression, working as if with a bignumber in base three, though offset.
200 P = NDIGITS !Start with the low-order digit.
201 OP(P) = OP(P) + 1 !Add one to it.
IF (OP(P).GT.1) THEN !Is a carry needed?
OP(P) = -1 !Yes. Set the digit back to the start.
P = P - 1 !Go up a power.
IF (P.GT.0) GO TO 201 !And augment the next digit up.
END IF !Once the carry fizzles, the increment is complete.
IF (OP(1).LE.0) GO TO 100 !A leading + is equivalent to a leading no-op.
Contemplate the collection.
300 WRITE (6,301) LOOP,NHIT
301 FORMAT (/,I0," evaluations, ",I0," hit the target.")
Crank up a comb sort.
H = LOOP - 1 !Last - First, and not +1.
IF (H.LE.0) STOP "Huh?" !Ha ha.
310 H = MAX(1,H*10/13) !The special feature.
IF (H.EQ.9 .OR. H.EQ.10) H = 11 !A twiddle.
CURSE = .FALSE. !So far, so good.
DO I = LOOP - H,1,-1 !If H = 1, this is a BubbleSort.
IF (VALUE(I) .GT. VALUE(I + H)) THEN !One compare.
N = VALUE(I);VALUE(I)=VALUE(I+H);VALUE(I+H)=N !One swap.
CURSE = .TRUE. !One curse.
END IF !One test.
END DO !One loop.
IF (CURSE .OR. H.GT.1) GO TO 310 !Work remains?
Chase after some results.
H = 0 !Hunt the first omitted positive number.
VE = 0 !No equal values have been seen.
ME = 0 !So, their maximum run length is short.
PV = VALUE(1) !Grab the first value,
DO I = 2,LOOP !And scan the successors.
V = VALUE(I) !The value of the moment.
IF (V.LE.0) CYCLE !Only positive numbers are of interest.
IF (V.GT.PV + 1) THEN !Is there a gap?
IF (H.LE.0) H = PV + 1 !Recall the first such.
END IF !Perhaps a list of the first dew?
IF (V.EQ.PV) THEN !Is it the same as the one before?
VE = VE + 1 !Yes. Count up the length of the run.
IF (VE.GT.ME) THEN !Is this a longer run?
ME = VE !Yes. Remember its length.
VV = V !And its value.
END IF !So much for runs of equal values.
ELSE !But if it is not the same,
VE = 0 !A fresh count awaits.
END IF !So much for comparing one value to its predecessor.
PV = V !Be ready for the next time around.
END DO !On to the next.
Cast forth the results.
IF (ME.GT.1) WRITE (MSG,320) VV,ME + 1 !Counting started with the second occurrence.
320 FORMAT (I0," has the maximum number of attainments:",I0)
IF (H.GT.0) WRITE (MSG,321) H !Surely there will be one.
321 FORMAT ("The lowest positive sum that can't be expressed is ",I0)
WRITE (MSG,322) VALUE(LOOP - 9:LOOP) !Surely LOOP > 9.
322 FORMAT ("The ten highest sums: ",10(I0:","))
END !That was fun!</syntaxhighlight>
Results:
<pre>
To find expressions of 9 digits in order, interspersed with + or -, adding to 100
1: -1+2-3+4+5+6+78+9
2: 12-3-4+5-6+7+89
3: 123-4-5-6-7+8-9
4: 123-45-67+89
5: 123+4-5+67-89
6: 123+45-67+8-9
7: 12+3-4+5+67+8+9
8: 12+3+4+5-6-7+89
9: 1+23-4+56+7+8+9
10: 1+23-4+5+6+78-9
11: 1+2+3-4+5+6+78+9
12: 1+2+34-5+67-8+9
13122 evaluations, 12 hit the target.
9 has the maximum number of attainments:46
The lowest positive sum that can't be expressed is 211
The ten highest sums: 3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">
#define PERM 13122
'Between any two adjacent digits there can be nothing, a plus, or a minus.
'And the first term can only be + or -
'This is equivalent to an eight-digit base 3 number. We therefore only need
'to consider 2*3^8=13122 possibilities
function ndig(n as uinteger) as uinteger
return 1+int(log(n+0.5)/log(10))
end function
function calculate( byval n as uinteger, outstr as string ) as integer
'calculates the sum given by one of the 13122 possibilities, as well as
'storing the equation itself as a string
outstr = "9"
dim as integer ret = 0, curr = 9
dim as boolean firstplus = n>=PERM/2
for i as integer = 8 to 1 step -1
select case n mod 3
case 0 'no symbol means we just prepend the next number
curr += i*10^(ndig(curr))
case 1 'addition: add the current term to the running sum, and clear the current term
ret += curr
curr = i
outstr = " + " + outstr
case 2 'subtraction: minus the current term from the running sum, and clear the current term
ret -= curr
curr = i
outstr = " - " + outstr
end select
outstr = str(i) + outstr 'prepend the previous digit to the string
n \= 3 'get next symbol
next i
if firstplus = 0 then
outstr = "-"+outstr
ret -= curr
else
ret += curr
end if
outstr = outstr + " = " + str(ret)
return ret
end function
'calculate and store all 13122 solutions
dim as string eqn
dim as integer n, sum(0 to PERM-1), curr
for n = 0 to PERM-1
curr = calculate(n, eqn)
sum(n) = curr
if curr = 100 then print eqn
next n
'what is the sum that has the most solutions?
dim as integer champ = 0, cnum = 0, i, j, acc
for i = 0 to PERM-1
acc = 0
for j = i to PERM-1
if sum(j) = sum(i) then acc+=1
next j
if acc>cnum then
champ = sum(i)
cnum=acc
end if
next i
print "The sum with the most occurrences is ";champ;", which shows up ";cnum;" times."
'what is the first nonnegative number that has no solution
for i = 0 to 123456788
for j = 0 to PERM-1
if sum(j)=i then goto nexti
next j
print "The first number that has no solution is ";i
exit for
nexti:
next i
'What are the ten highest numbers?
'this partially destroys the information in the array, but who cares?
'We're almost done and these excessive questionnaires are the worst
'and most boring part of Rosetta Code tasks
print "The ten highest numbers attainable are:"
champ = 0
for i = 1 to 10
for j = 0 to PERM-1
if sum(j)>sum(champ) then champ = j
next j
calculate(champ, eqn)
print eqn
sum(champ) = -9999 'overwrite to stop this being found a second time
next i</syntaxhighlight>
{{out}}<pre>
-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9 = 100
123 + 45 - 67 + 8 - 9 = 100
123 + 4 - 5 + 67 - 89 = 100
123 - 45 - 67 + 89 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
The sum with the most occurrences is 9, which shows up 46 times.
The first number that has no solution is 211
The ten highest numbers attainable are:
123456789 = 123456789
1 + 23456789 = 23456790
-1 + 23456789 = 23456788
12345678 + 9 = 12345687
12345678 - 9 = 12345669
12 + 3456789 = 3456801
1 + 2 + 3456789 = 3456792
-1 + 2 + 3456789 = 3456790
1 - 2 + 3456789 = 3456788
-1 - 2 + 3456789 = 3456786
</pre>
=={{header|Frink}}==
<syntaxhighlight lang="frink">
digits = array[1 to 9]
opList = makeArray[[8], ["", " + ", " - "]]
opList.pushFirst[["", "-"]]
countDict = new dict
multifor ops = opList
{
str = ""
for d = rangeOf[digits]
str = str + ops@d + digits@d
e = eval[str]
countDict.increment[e, 1]
if e == 100
println[str]
}
println[]
// Find the sum that has the maximum number of solutions
freq = toArray[countDict]
sort[freq, {|a,b| -(a@1 <=> b@1)}]
max = freq@0@1
print["Maximum count is $max at: "]
n = 0
while freq@n@1 == max
{
print[freq@n@0 + " "]
n = n + 1
}
println[]
// Find the smallest non-representable positive sum
sort[freq, {|a,b| a@0 <=> b@0}]
last = 0
for [num, count] = freq
{
if num > 0 and last+1 != num
{
println["Lowest non-representable positive sum is " + (last+1)]
break
}
last = num
}
// Find highest 10 representable numbers
println["\nHighest representable numbers:"]
size = length[freq]
for i = size-10 to size-1
println[freq@i@0]
</syntaxhighlight>
{{out}}
<pre>
123 + 45 - 67 + 8 - 9
123 + 4 - 5 + 67 - 89
123 - 45 - 67 + 89
123 - 4 - 5 - 6 - 7 + 8 - 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
1 + 23 - 4 + 56 + 7 + 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
Maximum count is 46 at: 9 -9
Lowest non-representable positive sum is 211
Highest representable numbers:
3456786
3456788
3456790
3456792
3456801
12345669
12345687
23456788
23456790
123456789
</pre>
=={{header|Go}}==
{{trans|C}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"sort"
)
const pow3_8 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 // 3^8
const pow3_9 = 3 * pow3_8 // 3^9
const maxExprs = 2 * pow3_8 // not 3^9 since first op can't be Join
type op uint8
const (
Add op = iota // insert a "+"
Sub // or a "-"
Join // or just join together
)
// code is an encoding of [9]op, the nine "operations"
// we do on each each digit. The op for 1 is in
// the highest bits, the op for 9 in the lowest.
type code uint16
// evaluate 123456789 with + - or "" prepended to each as indicated by `c`.
func (c code) evaluate() (sum int) {
num, pow := 0, 1
for k := 9; k >= 1; k-- {
num += pow * k
switch op(c % 3) {
case Add:
sum += num
num, pow = 0, 1
case Sub:
sum -= num
num, pow = 0, 1
case Join:
pow *= 10
}
c /= 3
}
return sum
}
func (c code) String() string {
buf := make([]byte, 0, 18)
a, b := code(pow3_9), code(pow3_8)
for k := 1; k <= 9; k++ {
switch op((c % a) / b) {
case Add:
if k > 1 {
buf = append(buf, '+')
}
case Sub:
buf = append(buf, '-')
}
buf = append(buf, '0'+byte(k))
a, b = b, b/3
}
return string(buf)
}
type sumCode struct {
sum int
code code
}
type sumCodes []sumCode
type sumCount struct {
sum int
count int
}
type sumCounts []sumCount
// For sorting (could also use sort.Slice with just Less).
func (p sumCodes) Len() int { return len(p) }
func (p sumCodes) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p sumCodes) Less(i, j int) bool { return p[i].sum < p[j].sum }
func (p sumCounts) Len() int { return len(p) }
func (p sumCounts) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p sumCounts) Less(i, j int) bool { return p[i].count > p[j].count }
// For printing.
func (sc sumCode) String() string {
return fmt.Sprintf("% 10d = %v", sc.sum, sc.code)
}
func (sc sumCount) String() string {
return fmt.Sprintf("% 10d has %d solutions", sc.sum, sc.count)
}
func main() {
// Evaluate all expressions.
expressions := make(sumCodes, 0, maxExprs/2)
counts := make(sumCounts, 0, 1715)
for c := code(0); c < maxExprs; c++ {
// All negative sums are exactly like their positive
// counterpart with all +/- switched, we don't need to
// keep track of them.
sum := c.evaluate()
if sum >= 0 {
expressions = append(expressions, sumCode{sum, c})
}
}
sort.Sort(expressions)
// Count all unique sums
sc := sumCount{expressions[0].sum, 1}
for _, e := range expressions[1:] {
if e.sum == sc.sum {
sc.count++
} else {
counts = append(counts, sc)
sc = sumCount{e.sum, 1}
}
}
counts = append(counts, sc)
sort.Sort(counts)
// Extract required results
fmt.Println("All solutions that sum to 100:")
i := sort.Search(len(expressions), func(i int) bool {
return expressions[i].sum >= 100
})
for _, e := range expressions[i:] {
if e.sum != 100 {
break
}
fmt.Println(e)
}
fmt.Println("\nThe positive sum with maximum number of solutions:")
fmt.Println(counts[0])
fmt.Println("\nThe lowest positive number that can't be expressed:")
s := 1
for _, e := range expressions {
if e.sum == s {
s++
} else if e.sum > s {
fmt.Printf("% 10d\n", s)
break
}
}
fmt.Println("\nThe ten highest numbers that can be expressed:")
for _, e := range expressions[len(expressions)-10:] {
fmt.Println(e)
}
}</syntaxhighlight>
{{out}}
<pre>
All solutions that sum to 100:
100 = -1+2-3+4+5+6+78+9
100 = 1+23-4+5+6+78-9
100 = 123+45-67+8-9
100 = 123+4-5+67-89
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 12+3-4+5+67+8+9
100 = 1+23-4+56+7+8+9
100 = 123-45-67+89
100 = 12-3-4+5-6+7+89
100 = 12+3+4+5-6-7+89
100 = 123-4-5-6-7+8-9
The positive sum with maximum number of solutions:
9 has 46 solutions
The lowest positive number that can't be expressed:
211
The ten highest numbers that can be expressed:
3456786 = -1-2+3456789
3456788 = 1-2+3456789
3456790 = -1+2+3456789
3456792 = 1+2+3456789
3456801 = 12+3456789
12345669 = 12345678-9
12345687 = 12345678+9
23456788 = -1+23456789
23456790 = 1+23456789
123456789 = 123456789
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang
import Data.Char (intToDigit)
import
( find,
group,
intercalate,
nub,
sort,
sortBy,
)
import Data.Monoid ((<>))
import Data.Ord (comparing)
data Sign
Line 1,411 ⟶ 3,194:
| Minus
deriving (Eq, Show)
------------------------ SUM TO 100 ----------------------
universe :: [[(Int, Sign)]]
universe =
zip [1 .. 9]
<$> filter
((/= Plus) . head)
(replicateM 9 [Unsigned, Plus, Minus])
allNonNegativeSums :: [Int]
allNonNegativeSums =
sort $
filter
(>= 0)
(asSum <$> universe)
uniqueNonNegativeSums :: [Int]
Line 1,425 ⟶ 3,216:
asSum :: [(Int, Sign)] -> Int
asSum xs =
n
+ (
)
where
(n, s) = foldr readSign (0, []) xs
readSign ::
(Int, Sign) ->
(Int, String) ->
(Int, String)
readSign (i, x) (n, s)
| x == Unsigned = (n, intToDigit i : s)
| otherwise =
( (
)
n
(read (show i <> s) :: Int),
)
asString :: [(Int, Sign)] -> String
Line 1,448 ⟶ 3,245:
| x == Unsigned = intToDigit i : s
| otherwise =
(
<> s
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
unlines
[ "Sums to 100:",
unlines
(asString <$> filter ((100 ==) . asSum) universe),
"\n10 commonest sums (sum, number of routes to it):",
10
( sortBy
(group allNonNegativeSums)
)
),
"\nFirst positive integer not expressible "
<> "as a sum of this kind:",
maybeReport
( find
(uncurry (/=))
(zip [0 ..] uniqueNonNegativeSums)
),
"\n10 largest sums:",
show
( take
10
( sortBy
(flip compare)
uniqueNonNegativeSums
)
)
]
where
maybeReport ::
String
maybeReport (Just (x, _)) = show x
maybeReport _ = "No gaps found"</
{{Out}}
(Run in Atom editor, through Script package)
Line 1,501 ⟶ 3,320:
[Finished in 1.204s]</pre>
=={{header|J}}==
Since J has no verb precedence, -1-2 would evaluate to 1 and not to -3. That's why I decided to multiply each of the partitions of '123456789' (like '123','45', '6', '78', '9') with each possible +1/-1 vectors of length 9 (like 1 1 -1 1 -1 -1 1 1 -1) and to add up the results. This leads to 512*256 results, that of course include a lot of duplicates. To use directly ~. (nub) on the 512x256x9 vector is very slow and that's why I computed a sort of a hash to use it to get only the unique expressions. The rest is trivial - I check which expressions add up to 100; sort the sum vector and find the longest sequence ot repeating sums; get the 10 largest sums and finnaly check which sum differs with more then 1 from the previous one.
<syntaxhighlight lang="j">
p =: ,"2".>(#: (+ i.)2^8) <;.1 '123456789'
m =. (9$_1x)^"1#:i.2^9
s =. 131072 9 $ ,m *"1/ p
s2 =: (~: (10x^i._9)#.s)#s
ss =: +/"1 s2
'100=';<'bp<+>' 8!:2 (I.100=ss){s2
pos =: (0<ss)#ss =: /:~ss
({.;'times';{:)>{.\:~(#,{.) each </.~ ss
'Ten largest:';,.(->:i.10){ss
'First not expressible:';>:pos{~ 1 i.~ 1<|2-/\pos
</syntaxhighlight>
{{out}}
<pre>
┌───┬────────────────────────┐
│100│+12 +3 +4 +5 -6 -7 +89 │
│ │+1 +2 +3 -4 +5 +6 +78+9│
│ │+1 +2 +34-5 +67-8 +9 │
│ │+12 +3 -4 +5 +67+8 +9 │
│ │+1 +23-4 +56+7 +8 +9 │
│ │+1 +23-4 +5 +6 +78-9 │
│ │+123+45-67+8 -9 │
│ │+123+4 -5 +67-89 │
│ │+123-45-67+89 │
│ │+12 -3 -4 +5 -6 +7 +89 │
│ │+123-4 -5 -6 -7 +8 -9 │
│ │-1 +2 -3 +4 +5 +6 +78+9│
└───┴────────────────────────┘
┌──┬─────┬─┐
│46│times│9│
└──┴─────┴─┘
┌────────────┬─────────┐
│Ten largest:│123456789│
│ │ 23456790│
│ │ 23456788│
│ │ 12345687│
│ │ 12345669│
│ │ 3456801│
│ │ 3456792│
│ │ 3456790│
│ │ 3456788│
│ │ 3456786│
└────────────┴─────────┘
┌───────────────────────┬───┐
│First not expressible :│211│
└───────────────────────┴───┘
</pre>
=={{header|Java}}==
{{Works with|Java|8}}
{{trans|C++}}
For each expression of sum s, there is at least one expression whose sum is -s. If the sum s can be represented by n expressions, the sum -s can also be represented by n expressions. The change of all signs in an expression change the sign of the sum of this expression. For example, -1+23-456+789 has the opposite sign than +1-23+456-789. Therefore only the positive sum with the maximum number of solutions is shown. The program does not check uniqueness of this sum. We can easily check (modifying the program) that: sum 9 has 46 solutions; sum -9 has 46 solutions; any other sum has less than 46 solutions.
<syntaxhighlight lang="java">/*
* RossetaCode: Sum to 100, Java 8.
*
Line 1,671 ⟶ 3,544:
}
}
}</
{{Out}}
<pre>Show all solutions that sum to 100
Line 1,712 ⟶ 3,585:
===ES5===
{{Trans|Haskell}}
<
'use strict';
Line 1,938 ⟶ 3,811:
show(take(10, uniqueNonNegativeSums.sort(flip(compare))))
].join('\n') + '\n';
})();</
{{Out}}
Line 1,975 ⟶ 3,848:
===ES6===
{{Trans|Haskell}}
<
'use strict';
Line 2,158 ⟶ 4,031:
show(take(10, uniqueNonNegativeSums.sort(flip(compare))))
].join('\n') + '\n';
})();</
{{Out}}
Line 2,193 ⟶ 4,066:
[Finished in 0.382s]</pre>
===ES3 (JScript)===
{{Works with|Microsoft Windows Script Host}}
{{Trans|AWK}}
<syntaxhighlight lang="javascript">SumTo100();
function SumTo100()
{
var
ADD = 0,
SUB = 1,
JOIN = 2;
var
nexpr = 13122;
function out(something)
{
WScript.Echo(something);
}
function evaluate(code)
{
var
value = 0,
number = 0,
power = 1;
for ( var k = 9; k >= 1; k-- )
{
number = power*k + number;
switch( code % 3 )
{
case ADD: value = value + number; number = 0; power = 1; break;
case SUB: value = value - number; number = 0; power = 1; break;
case JOIN: power = power * 10 ; break;
}
code = Math.floor(code/3);
}
return value;
}
function print(code)
{
var
s = "";
var
a = 19683,
b = 6561;
for ( var k = 1; k <= 9; k++ )
{
switch( Math.floor( (code % a) / b ) ){
case ADD: if ( k > 1 ) s = s + '+'; break;
case SUB: s = s + '-'; break;
}
a = b;
b = Math.floor(b/3);
s = s + String.fromCharCode(0x30+k);
}
out(evaluate(code) + " = " + s);
}
function comment(commentString)
{
out("");
out(commentString);
out("");
}
comment("Show all solutions that sum to 100");
for ( var i = 0; i < nexpr; i++)
if ( evaluate(i) == 100 )
print(i);
comment("Show the sum that has the maximum number of solutions");
var stat = {};
for ( var i = 0; i < nexpr; i++ )
{
var sum = evaluate(i);
if (stat[sum])
stat[sum]++;
else
stat[sum] = 1;
}
var best = 0;
var nbest = -1;
for ( var i = 0; i < nexpr; i++ )
{
var sum = evaluate(i);
if ( sum > 0 )
if ( stat[sum] > nbest )
{
best = i;
nbest = stat[sum];
}
}
out("" + evaluate(best) + " has " + nbest + " solutions");
comment("Show the lowest positive number that can't be expressed");
for ( var i = 0; i <= 123456789; i++ )
{
for ( var j = 0; j < nexpr; j++)
if ( i == evaluate(j) ) break;
if ( i != evaluate(j) ) break;
}
out(i);
comment("Show the ten highest numbers that can be expressed");
var limit = 123456789 + 1;
for ( i = 1; i <= 10; i++ )
{
var best = 0;
for ( var j = 0; j < nexpr; j++)
{
var test = evaluate(j);
if ( test < limit && test > best )
best = test;
}
for ( var j = 0; j < nexpr; j++)
if ( evaluate(j) == best ) print(j);
limit = best;
}
}
</syntaxhighlight>
{{Out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|jq}}==
For ease of understanding, the problems will be solved separately, using the machinery defined in the following section.
'''All possible sums'''
<syntaxhighlight lang="jq"># Generate a "sum" in the form: [I, 1, X, 2, X, 3, ..., X, n] where I is "-" or "", and X is "+", "-", or ""
def generate(n):
def pm: ["+"], ["-"], [""];
if n == 1 then (["-"], [""]) + [1]
else generate(n-1) + pm + [n]
end;
# The numerical value of a "sum"
def addup:
reduce .[] as $x ({sum:0, previous: "0"};
if $x == "+" then .sum += (.previous|tonumber) | .previous = ""
elif $x == "-" then .sum += (.previous|tonumber) | .previous = "-"
elif $x == "" then .
else .previous += ($x|tostring)
end)
| .sum + (.previous | tonumber) ;
# Pretty-print a "sum", e.g. ["",1,"+", 2] => 1 + 2
def pp: map(if . == "+" or . == "-" then " " + . else tostring end) | join("");
</syntaxhighlight>
'''Solutions to "Sum to 100" problem'''
<syntaxhighlight lang="jq">generate(9) | select(addup == 100) | pp</syntaxhighlight>
{{out}}
<pre>
1 +23 -4 +56 +7 +8 +9
12 +3 -4 +5 +67 +8 +9
1 +2 +34 -5 +67 -8 +9
-1 +2 -3 +4 +5 +6 +78 +9
1 +2 +3 -4 +5 +6 +78 +9
123 -4 -5 -6 -7 +8 -9
123 +45 -67 +8 -9
1 +23 -4 +5 +6 +78 -9
12 -3 -4 +5 -6 +7 +89
12 +3 +4 +5 -6 -7 +89
123 -45 -67 +89
123 +4 -5 +67 -89</pre>
'''Helper Functions'''
For brevity, we define an efficient function for computing a histogram in the form of a JSON object, and
a helper function for identifying the values with the n highest frequencies.
<syntaxhighlight lang="jq">def histogram(s): reduce s as $x ({}; ($x|tostring) as $k | .[$k] += 1);
# Emit an array of [ value, frequency ] pairs
def greatest(n):
to_entries
| map( [.key, .value] )
| sort_by(.[1])
| .[(length-n):]
| reverse ; </syntaxhighlight>
'''Maximum number of solutions'''
<syntaxhighlight lang="jq">histogram(generate(9) | addup | select(.>0)) | greatest(1)</syntaxhighlight>
{{out}}
<pre>[["9",46]]</pre>
'''Ten most frequent sums'''
<syntaxhighlight lang="jq">histogram(generate(9) | addup | select(.>0)) | greatest(1)</syntaxhighlight>
{{out}}
<pre>[["9",46],["27",44],["1",43],["21",43],["15",43],["45",42],["3",41],["5",40],["7",39],["17",39]]</pre>
'''First unsolvable'''
<syntaxhighlight lang="jq">def first_missing(s):
first( foreach s as $i (null;
if . == null or $i == . or $i == .+1 then $i else [.+1] end;
select(type == "array") | .[0]));
first_missing( [generate(9) | addup | select(.>0) ] | unique[])</syntaxhighlight>
{{out}}
211
'''Ten largest sums'''
<syntaxhighlight lang="jq">[generate(9) | addup | select(.>0)] | unique | .[(length-10):]</syntaxhighlight>
{{out}}
[3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789]
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Printf, IterTools, DataStructures
expr(p::String...)::String = @sprintf("%s1%s2%s3%s4%s5%s6%s7%s8%s9", p...)
function genexpr()::Vector{String}
op = ["+", "-", ""]
return collect(expr(p...) for (p) in Iterators.product(op, op, op, op, op, op, op, op, op) if p[1] != "+")
end
using DataStructures
function allexpr()::Dict{Int,Int}
rst = DefaultDict{Int,Int}(0)
for e in genexpr()
val = eval(Meta.parse(e))
rst[val] += 1
end
return rst
end
sumto(val::Int)::Vector{String} = filter(e -> eval(Meta.parse(e)) == val, genexpr())
function maxsolve()::Dict{Int,Int}
ae = allexpr()
vmax = maximum(values(ae))
smax = filter(ae) do (v, f)
f == vmax
end
return smax
end
function minsolve()::Int
ae = keys(allexpr())
for i in 1:typemax(Int)
if i ∉ ae
return i
end
end
end
function highestsums(n::Int)::Vector{Int}
sums = collect(keys(allexpr()))
return sort!(sums; rev=true)[1:n]
end
const solutions = sumto(100)
const smax = maxsolve()
const smin = minsolve()
const hsums = highestsums(10)
println("100 =")
foreach(println, solutions)
println("\nMax number of solutions:")
for (v, f) in smax
@printf("%3i -> %2i\n", v, f)
end
println("\nMin number with no solutions: $smin")
println("\nHighest sums representable:")
foreach(println, hsums)
</syntaxhighlight>{{out}}
<pre>100 =
1+23-4+56+7+8+9
12+3-4+5+67+8+9
1+2+34-5+67-8+9
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
123-4-5-6-7+8-9
123+45-67+8-9
1+23-4+5+6+78-9
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123-45-67+89
123+4-5+67-89
Max number of solutions:
9 -> 46
-9 -> 46
Min number with no solutions: 211
Highest sums representable:
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786</pre>
=={{header|Kotlin}}==
{{trans|C++}}
<syntaxhighlight lang="scala">// version 1.1.51
class Expression {
private enum class Op { ADD, SUB, JOIN }
private val code = Array<Op>(NUMBER_OF_DIGITS) { Op.ADD }
companion object {
private const val NUMBER_OF_DIGITS = 9
private const val THREE_POW_4 = 3 * 3 * 3 * 3
private const val FMT = "%9d"
const val NUMBER_OF_EXPRESSIONS = 2 * THREE_POW_4 * THREE_POW_4
fun print(givenSum: Int) {
var expression = Expression()
repeat(Expression.NUMBER_OF_EXPRESSIONS) {
if (expression.toInt() == givenSum) println("${FMT.format(givenSum)} = $expression")
expression++
}
}
}
operator fun inc(): Expression {
for (i in 0 until code.size) {
code[i] = when (code[i]) {
Op.ADD -> Op.SUB
Op.SUB -> Op.JOIN
Op.JOIN -> Op.ADD
}
if (code[i] != Op.ADD) break
}
return this
}
fun toInt(): Int {
var value = 0
var number = 0
var sign = +1
for (digit in 1..9) {
when (code[NUMBER_OF_DIGITS - digit]) {
Op.ADD -> { value += sign * number; number = digit; sign = +1 }
Op.SUB -> { value += sign * number; number = digit; sign = -1 }
Op.JOIN -> { number = 10 * number + digit }
}
}
return value + sign * number
}
override fun toString(): String {
val sb = StringBuilder()
for (digit in 1..NUMBER_OF_DIGITS) {
when (code[NUMBER_OF_DIGITS - digit]) {
Op.ADD -> if (digit > 1) sb.append(" + ")
Op.SUB -> sb.append(" - ")
Op.JOIN -> {}
}
sb.append(digit)
}
return sb.toString().trimStart()
}
}
class Stat {
val countSum = mutableMapOf<Int, Int>()
val sumCount = mutableMapOf<Int, MutableSet<Int>>()
init {
var expression = Expression()
repeat (Expression.NUMBER_OF_EXPRESSIONS) {
val sum = expression.toInt()
countSum.put(sum, 1 + (countSum[sum] ?: 0))
expression++
}
for ((k, v) in countSum) {
val set = if (sumCount.containsKey(v))
sumCount[v]!!
else
mutableSetOf<Int>()
set.add(k)
sumCount.put(v, set)
}
}
}
fun main(args: Array<String>) {
println("100 has the following solutions:\n")
Expression.print(100)
val stat = Stat()
val maxCount = stat.sumCount.keys.max()
val maxSum = stat.sumCount[maxCount]!!.max()
println("\n$maxSum has the maximum number of solutions, namely $maxCount")
var value = 0
while (stat.countSum.containsKey(value)) value++
println("\n$value is the lowest positive number with no solutions")
println("\nThe ten highest numbers that do have solutions are:\n")
stat.countSum.keys.toIntArray().sorted().reversed().take(10).forEach { Expression.print(it) }
}</syntaxhighlight>
{{out}}
<pre>
100 has the following solutions:
100 = 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
100 = 1 + 2 + 34 - 5 + 67 - 8 + 9
100 = 1 + 23 - 4 + 5 + 6 + 78 - 9
100 = 1 + 23 - 4 + 56 + 7 + 8 + 9
100 = 12 + 3 + 4 + 5 - 6 - 7 + 89
100 = 12 + 3 - 4 + 5 + 67 + 8 + 9
100 = 12 - 3 - 4 + 5 - 6 + 7 + 89
100 = 123 + 4 - 5 + 67 - 89
100 = 123 + 45 - 67 + 8 - 9
100 = 123 - 4 - 5 - 6 - 7 + 8 - 9
100 = 123 - 45 - 67 + 89
100 = - 1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
9 has the maximum number of solutions, namely 46
211 is the lowest positive number with no solutions
The ten highest numbers that do have solutions are:
123456789 = 123456789
23456790 = 1 + 23456789
23456788 = - 1 + 23456789
12345687 = 12345678 + 9
12345669 = 12345678 - 9
3456801 = 12 + 3456789
3456792 = 1 + 2 + 3456789
3456790 = - 1 + 2 + 3456789
3456788 = 1 - 2 + 3456789
3456786 = - 1 - 2 + 3456789
</pre>
=={{header|Lua}}==
{{trans|C}}
<syntaxhighlight lang="lua">local expressionsLength = 0
function compareExpressionBySum(a, b)
return a.sum - b.sum
end
local countSumsLength = 0
function compareCountSumsByCount(a, b)
return a.counts - b.counts
end
function evaluate(code)
local value = 0
local number = 0
local power = 1
for k=9,1,-1 do
number = power*k + number
local mod = code % 3
if mod == 0 then
-- ADD
value = value + number
number = 0
power = 1
elseif mod == 1 then
-- SUB
value = value - number
number = 0
power = 1
elseif mod == 2 then
-- JOIN
power = 10 * power
else
print("This should not happen.")
end
code = math.floor(code / 3)
end
return value
end
function printCode(code)
local a = 19683
local b = 6561
local s = ""
for k=1,9 do
local temp = math.floor((code % a) / b)
if temp == 0 then
-- ADD
if k>1 then
s = s .. '+'
end
elseif temp == 1 then
-- SUB
s = s .. '-'
end
a = b
b = math.floor(b/3)
s = s .. tostring(k)
end
print("\t"..evaluate(code).." = "..s)
end
-- Main
local nexpr = 13122
print("Show all solutions that sum to 100")
for i=0,nexpr-1 do
if evaluate(i) == 100 then
printCode(i)
end
end
print()
print("Show the sum that has the maximum number of solutions")
local nbest = -1
for i=0,nexpr-1 do
local test = evaluate(i)
if test>0 then
local ntest = 0
for j=0,nexpr-1 do
if evaluate(j) == test then
ntest = ntest + 1
end
if ntest > nbest then
best = test
nbest = ntest
end
end
end
end
print(best.." has "..nbest.." solutions\n")
print("Show the lowest positive number that can't be expressed")
local code = -1
for i=0,123456789 do
for j=0,nexpr-1 do
if evaluate(j) == i then
code = j
break
end
end
if evaluate(code) ~= i then
code = i
break
end
end
print(code.."\n")
print("Show the ten highest numbers that can be expressed")
local limit = 123456789 + 1
for i=1,10 do
local best=0
for j=0,nexpr-1 do
local test = evaluate(j)
if (test<limit) and (test>best) then
best = test
end
end
for j=0,nexpr-1 do
if evaluate(j) == best then
printCode(j)
end
end
limit = best
end</syntaxhighlight>
{{out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Defining all possible sums:
<syntaxhighlight lang="mathematica">operations = DeleteCases[Tuples[{"+", "-", ""}, 9], {x_, y__} /; x == "+"];
sums = Map[StringJoin[Riffle[#, CharacterRange["1", "9"]]] &, operations];</syntaxhighlight>
Sums to 100:
<syntaxhighlight lang="mathematica"> TableForm@Select[sums, ToExpression@# == 100 &] </syntaxhighlight>
{{out}}
<pre>-1+2-3+4+5+6+78+9
Line 2,224 ⟶ 4,720:
Maximum number of solutions:
<syntaxhighlight lang
{{out}}
<pre> <|9 -> 46, -9 -> 46|> </pre>
First unsolvable:
<syntaxhighlight lang="mathematica"> pos = Cases[ToExpression@sums, _?Positive];
n = 1; While[MemberQ[pos, n], ++n]; </syntaxhighlight>
{{out}}
<pre>
Ten largest sums:
<syntaxhighlight lang="mathematica"> {#, ToExpression@#}&/@TakeLargestBy[sums, ToExpression, 10]//TableForm </syntaxhighlight>
{{out}}
<pre> 123456789 123456789
1+23456789 23456790
-1+23456789 23456788
12345678+9 12345687
12345678-9 12345669
12+3456789 3456801
1+2+3456789 3456792
-1+2+3456789 3456790
1-2+3456789 3456788
-1-2+3456789 3456786 </pre>
=={{header|Modula-2}}==
{{trans|C}}
<syntaxhighlight lang="modula2">MODULE SumTo100;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
PROCEDURE Evaluate(code : INTEGER) : INTEGER;
VAR
value,number,power,k : INTEGER;
BEGIN
value := 0;
number := 0;
power := 1;
FOR k:=9 TO 1 BY -1 DO
number := power * k + number;
IF code MOD 3 = 0 THEN
(* ADD *)
value := value + number;
number := 0;
power := 1
ELSIF code MOD 3 = 1 THEN
(* SUB *)
value := value - number;
number := 0;
power := 1
ELSE
(* CAT *)
power := power * 10
END;
code := code / 3
END;
RETURN value
END Evaluate;
PROCEDURE Print(code : INTEGER);
VAR
expr,buf : ARRAY[0..63] OF CHAR;
a,b,k,p : INTEGER;
BEGIN
a := 19683;
b := 6561;
p := 0;
FOR k:=1 TO 9 DO
IF (code MOD a) / b = 0 THEN
IF k > 1 THEN
expr[p] := '+';
INC(p)
END
ELSIF (code MOD a) / b = 1 THEN
expr[p] := '-';
INC(p)
END;
a := b;
b := b / 3;
expr[p] := CHR(k + 30H);
INC(p)
END;
expr[p] := 0C;
FormatString("%9i = %s\n", buf, Evaluate(code), expr);
WriteString(buf)
END Print;
(* Main *)
CONST nexpr = 13122;
VAR
i,j : INTEGER;
best,nbest,test,ntest,limit : INTEGER;
buf : ARRAY[0..63] OF CHAR;
BEGIN
WriteString("Show all solution that sum to 100");
WriteLn;
FOR i:=0 TO nexpr-1 DO
IF Evaluate(i) = 100 THEN
Print(i)
END
END;
WriteLn;
WriteString("Show the sum that has the maximum number of solutions");
WriteLn;
nbest := -1;
FOR i:=0 TO nexpr-1 DO
test := Evaluate(i);
IF test > 0 THEN
ntest := 0;
FOR j:=0 TO nexpr-1 DO
IF Evaluate(j) = test THEN
INC(ntest)
END;
IF ntest > nbest THEN
best := test;
nbest := ntest
END
END
END
END;
FormatString("%i has %i solutions\n\n", buf, best, nbest);
WriteString(buf);
WriteString("Show the lowest positive number that can't be expressed");
WriteLn;
FOR i:=0 TO 123456789 DO
FOR j:=0 TO nexpr-1 DO
IF i = Evaluate(j) THEN
BREAK
END
END;
IF i # Evaluate(j) THEN
BREAK
END
END;
FormatString("%i\n\n", buf, i);
WriteString(buf);
WriteString("Show the ten highest numbers that can be expressed");
WriteLn;
limit := 123456789 + 1;
FOR i:=1 TO 10 DO
best := 0;
FOR j:=0 TO nexpr-1 DO
test := Evaluate(j);
IF (test < limit) AND (test > best) THEN
best := test
END
END;
FOR j:=0 TO nexpr-1 DO
IF Evaluate(j) = best THEN
Print(j)
END
END;
limit := best
END;
ReadChar
END SumTo100.</syntaxhighlight>
{{out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|Nim}}==
Recursive solution.
<syntaxhighlight lang="nim">import algorithm, parseutils, sequtils, strutils, tables
type Expression = string
proc buildExprs(start: Natural = 0): seq[Expression] =
let item = if start == 0: "" else: $start
if start == 9: return @[item]
for expr in buildExprs(start + 1):
result.add item & expr
result.add item & '-' & expr
if start != 0: result.add item & '+' & expr
proc evaluate(expr: Expression): int =
var idx = 0
var val: int
while idx < expr.len:
let n = expr.parseInt(val, idx)
inc idx, n
result += val
let exprs = buildExprs()
var counts: CountTable[int]
echo "The solutions for 100 are:"
for expr in exprs:
let sum = evaluate(expr)
if sum == 100: echo expr
if sum > 0: counts.inc(sum)
let (n, count) = counts.largest()
echo "\nThe maximum count of positive solutions is $1 for number $2.".format(count, n)
var s = 1
while true:
if s notin counts:
echo "\nThe smallest number than cannot be expressed is: $1.".format(s)
break
inc s
echo "\nThe ten highest numbers than can be expressed are:"
let numbers = sorted(toSeq(counts.keys), Descending)
echo numbers[0..9].join(", ")</syntaxhighlight>
{{out}}
<pre>The solutions for 100 are:
123+4-5+67-89
123-45-67+89
12+3+4+5-6-7+89
12-3-4+5-6+7+89
1+23-4+5+6+78-9
123+45-67+8-9
123-4-5-6-7+8-9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9
1+2+34-5+67-8+9
12+3-4+5+67+8+9
1+23-4+56+7+8+9
The maximum count of positive solutions is 46 for number 9.
The smallest number than cannot be expressed is: 211.
The ten highest numbers than can be expressed are:
123456789, 23456790, 23456788, 12345687, 12345669, 3456801, 3456792, 3456790, 3456788, 3456786</pre>
Iterative previous solution written in French (updated).
<syntaxhighlight lang="nim">import strutils
var
Line 2,260 ⟶ 5,007:
liS = split(li," ")
for i in liS:
if i.len > 0: result += parseInt(i)
echo "Valeur à atteindre : ",aAtteindre
Line 2,315 ⟶ 5,062:
echo "Plus grandes valeurs pouvant être atteintes :"
for i in 1..10:
echo calcul(plusGrandes[i])," = ",plusGrandes[i]</
{{out}}
<pre>Valeur à atteindre : 100
Line 2,348 ⟶ 5,095:
</pre>
=={{header|
{{works with|
{{trans|C}}
<syntaxhighlight lang="pascal">{ RossetaCode: Sum to 100, Pascal.
Find solutions to the "sum to one hundred" puzzle.
We don't use arrays, but recompute all values again and again.
It is a little surprise that the time efficiency is quite acceptable. }
program sumto100;
const
ADD = 0; SUB = 1; JOIN = 2; { opcodes inserted between digits }
NEXPR = 13122; { the total number of expressions }
var
i, j: integer;
loop: boolean;
test, ntest, best, nbest, limit: integer;
function evaluate(code: integer): integer;
var
k: integer;
value, number, power: integer;
begin
value := 0;
number := 0;
power := 1;
for k := 9 downto 1 do
begin
number := power * k + number;
case code mod 3 of
ADD: begin value := value + number; number := 0; power := 1; end;
SUB: begin value := value - number; number := 0; power := 1; end;
JOIN: power := power * 10
end;
code := code div 3
end;
evaluate := value
end;
procedure print(code: integer);
var
k: integer;
a, b: integer;
begin
a := 19683;
b := 6561;
write( evaluate(code):9 );
write(' = ');
for k := 1 to 9 do
begin
case ((code mod a) div b) of
ADD: if k > 1 then write('+');
SUB: { always } write('-');
end;
a := b;
b := b div 3;
write( k:1 )
end;
writeln
end;
begin
writeln;
writeln('Show all solutions that sum to 100');
writeln;
for i := 0 to NEXPR - 1 do
if evaluate(i) = 100 then
print(i);
writeln;
writeln('Show the sum that has the maximum number of solutions');
writeln;
nbest := (-1);
for i := 0 to NEXPR - 1 do
begin
test := evaluate(i);
if test > 0 then
begin
ntest := 0;
for j := 0 to NEXPR - 1 do
if evaluate(j) = test then
ntest := ntest + 1;
if ntest > nbest then
begin
best := test;
nbest := ntest;
end
end
end;
writeln(best, ' has ', nbest, ' solutions');
writeln;
writeln('Show the lowest positive number that can''t be expressed');
writeln;
i := 0;
loop := TRUE;
while (i <= 123456789) and loop do
begin
j := 0;
while (j < NEXPR - 1) and (i <> evaluate(j)) do
j := j + 1;
if i <> evaluate(j) then
loop := FALSE
else
i := i + 1;
end;
writeln(i);
writeln;
writeln('Show the ten highest numbers that can be expressed');
writeln;
limit := 123456789 + 1;
for i := 1 to 10 do
begin
best := 0;
for j := 0 to NEXPR - 1 do
begin
test := evaluate(j);
if (test < limit) and (test > best) then
best := test;
end;
for j := 0 to NEXPR - 1 do
if evaluate(j) = best then
print(j);
limit := best;
end
end.</syntaxhighlight>
{{Out}}
<pre>
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
100 = -1+2-3+4+5+6+78+9
Show the sum that has the maximum number of solutions
9 has 46 solutions
Show the lowest positive number that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
=={{header|Perl}}==
{{works with|Perl|5.10}}
<syntaxhighlight lang="perl">#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
my $string = '123456789';
my $length = length $string;
my @possible_ops = ("" , '+', '-');
{
my @ops;
return @ops = (0) x ($length) unless @ops;
while ($i < $length) {
if ($ops[$i]++ > $#possible_ops - 1) {
$ops[$i++] = 0;
next
}
# + before the first number
next if 0 == $i && '+' eq $possible_ops[ $ops[0] ];
return @ops
}
return
}
}
sub evaluate {
my ($expression) = @_;
my $sum;
$sum += $_ for $expression =~ /([-+]?[0-9]+)/g;
return $sum
}
my %count = ( my $max_count = 0 => 0 );
say 'Show all solutions that sum to 100';
while (my @ops = Next()) {
my $expression = "";
for my $i (0 .. $length - 1) {
$expression .= $possible_ops[ $ops[$i] ];
$expression .= substr $string, $i, 1;
}
my $sum = evaluate($expression);
++$count{$sum};
$max_count = $sum if $count{$sum} > $count{$max_count};
say $expression if 100 == $sum;
}
say 'Show the sum that has the maximum number of solutions';
say "sum: $max_count; solutions: $count{$max_count}";
my $n = 1;
++$n until ! exists $count{$n};
say "Show the lowest positive sum that can't be expressed";
say $n;
say 'Show the ten highest numbers that can be expressed';
say for (sort { $b <=> $a } keys %count)[0 .. 9];</syntaxhighlight>
{{Out}}
<pre>Show all solutions that sum to 100
123-45-67+89
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123+4-5+67-89
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
12+3-4+5+67+8+9
1+23-4+56+7+8+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
123+45-67+8-9
123-4-5-6-7+8-9
Show the sum that has the maximum number of solutions
sum: 9; solutions: 46
Show the lowest positive sum that can't be expressed
211
Show the ten highest numbers that can be expressed
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786</pre>
===oneliner version===
The first task posed can be solved simply with (pay attention to doublequotes around the program: adjust for you OS):
<syntaxhighlight lang="perl">
perl -E "say for grep{eval $_ == 100} glob '{-,}'.join '{+,-,}',1..9"
</syntaxhighlight>
While the whole task can be solved by:
<syntaxhighlight lang="perl">
perl -MList::Util="first" -E "@c[0..10**6]=(0..10**6);say for grep{$e=eval;$c[$e]=undef if $e>=0;$h{$e}++;eval $_==100}glob'{-,}'.join'{+,-,}',1..9;END{say for(sort{$h{$b}<=>$h{$a}}grep{$_>=0}keys %h)[0],first{defined $_}@c;say for(sort{$b<=>$a}grep{$_>0}keys %h)[0..9]}"
</syntaxhighlight>
which outputs
<pre>
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
9
211
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786
</pre>
=={{header|Phix}}==
{{libheader|Phix/basics}}
This is just a trivial count in base 3, with a leading '+' being irrelevant, so from 0(3)000_000_000 to 0(3)122_222_222 which is only (in decimal) 13,122 ...<br>
Admittedly, categorising them into 3429 bins is slightly more effort, but otherwise I am somewhat bemused by all the applescript/javascript/Haskell shenanegins.<br>
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #000000;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">SUB</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NOP</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ADD</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ADD</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">NOP</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">*</span><span style="color: #000000;">tmp</span>
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">*</span><span style="color: #000000;">tmp</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">NOP</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">','</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- Logically this intersperses -/nop/+ between each digit, but you do not actually need the digit.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (==> ..nop+add*8)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxr</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">done</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">evaluate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">solns</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?{}:</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)))</span>
<span style="color: #000000;">solns</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxl</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">NOP</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">ADD</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SUB</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d solutions considered (dictionary size: %d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">()})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s100</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There are %d sums to 100:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s100</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">show</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The positive sum of %d has the maximum number of solutions: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxl</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">missing</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000080;font-style:italic;">/*data*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000080;font-style:italic;">/*pkey*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*user_data=-2*/</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">key</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">traverse_dict_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">missing</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The lowest positive sum that cannot be expressed: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">highest</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">top10</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000080;font-style:italic;">/*data*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">highest</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">key</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">highest</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">10</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">--DEV named params on builtins need pre-loading...:
--traverse_dict(top10,rev:=1)</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">top10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The 10 highest sums: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">highest</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
Line 2,494 ⟶ 5,508:
</pre>
=={{header|
<syntaxhighlight lang="picat">main =>
L = "23456789",
gen(L,Str),
Exp = parse_term(['1'|Str]),
Exp =:= 100,
println(['1'|Str]).
gen(L@[_],Str) => Str = L.
gen([D|Ds],Str) ?=> Str = [D|StrR], gen(Ds,StrR). % no operator
gen([D|Ds],Str) ?=> Str = ['+',D|StrR], gen(Ds,StrR). % insert +
gen([D|Ds],Str) => Str = ['-',D|StrR], gen(Ds,StrR). % insert -
</syntaxhighlight>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">#START=6561
#STOPP=19682
#SUMME=100
#BASIS="123456789"
Structure TSumTerm
sum.i
ter.s
EndStructure
NewList Solutions.TSumTerm()
NewMap SolCount.i()
Dim op.s{1}(8)
Dim b.s{1}(8)
PokeS(@b(),#BASIS)
Procedure StripTerm(*p_Term)
If PeekS(*p_Term,1)="+" : PokeC(*p_Term,' ') : EndIf
EndProcedure
Procedure.s Triadisch(v)
While v : r$=Str(v%3)+r$ : v/3 : Wend
ProcedureReturn r$
EndProcedure
Procedure.i Calc(t$)
While Len(t$)
x=Val(t$) : r+x
If x<0 : s$=Str(x) : Else : s$="+"+Str(x) : EndIf
t$=RemoveString(t$,s$,#PB_String_NoCase,1,1)
Wend
ProcedureReturn r
EndProcedure
For n=#START To #STOPP
PokeS(@op(),Triadisch(n))
Term$=""
For i=0 To 8
Select op(i)
Case "0" : Term$+ b(i)
Case "1" : Term$+"+"+b(i)
Case "2" : Term$+"-"+b(i)
EndSelect
Next
AddElement(Solutions()) : Solutions()\sum=Calc(Term$) : StripTerm(@Term$) : Solutions()\ter=Term$
Next
SortStructuredList(Solutions(),#PB_Sort_Ascending,OffsetOf(TSumTerm\sum),TypeOf(TSumTerm\sum))
If OpenConsole()
PrintN("Show all solutions that sum to 100:")
ForEach Solutions()
If Solutions()\sum=#SUMME : PrintN(#TAB$+Solutions()\ter) : EndIf
SolCount(Str(Solutions()\sum))+1
Next
ForEach SolCount()
If SolCount()>MaxCount : MaxCount=SolCount() : MaxVal$=MapKey(SolCount()) : EndIf
Next
PrintN("Show the positve sum that has the maximum number of solutions:")
PrintN(#TAB$+MaxVal$+" has "+Str(MaxCount)+" solutions")
If LastElement(Solutions())
MaxVal=Solutions()\sum
PrintN("Show the lowest positive number that can't be expressed:")
For i=1 To MaxVal
If SolCount(Str(i))=0 : PrintN(#TAB$+Str(i)) : Break : EndIf
Next
PrintN("Show the 10 highest numbers that can be expressed:")
For i=1 To 10
PrintN(#TAB$+LSet(Str(Solutions()\sum),9)+" = "+Solutions()\ter)
If Not PreviousElement(Solutions()) : Break : EndIf
Next
EndIf
Input()
EndIf</syntaxhighlight>
{{out}}
<pre>Show all solutions that sum to 100:
123+45-67+8-9
123+4-5+67-89
123-45-67+89
123-4-5-6-7+8-9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9
Show the positve sum that has the maximum number of solutions:
9 has 46 solutions
Show the lowest positive number that can't be expressed:
211
Show the 10 highest numbers that can be expressed:
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">from itertools import product, islice
Line 2,549 ⟶ 5,679:
max_solve()
min_solve()
highest_sums()</syntaxhighlight>
{{out}}
<pre>(100, '-1+2-3+4+5+6+78+9')
(100, '1+2+3-4+5+6+78+9')
(100, '1+2+34-5+67-8+9')
(100, '1+23-4+5+6+78-9')
(100, '1+23-4+56+7+8+9')
(100, '12+3+4+5-6-7+89')
(100, '12+3-4+5+67+8+9')
(100, '12-3-4+5-6+7+89')
(100, '123+4-5+67-89')
(100, '123+45-67+8-9')
(100, '123-4-5-6-7+8-9')
(100, '123-45-67+89')
Sum 9 has the maximum number of solutions: 46
Lowest positive sum that can't be expressed: 211
Highest Sums: [123456789, 23456790, 23456788, 12345687, 12345669, 3456801, 3456792, 3456790, 3456788, 3456786]</pre>
=== Alternate solution ===
Mostly the same algorithm, but both shorter and faster.
<syntaxhighlight lang="python">import itertools
from collections import defaultdict, Counter
s = "123456789"
h = defaultdict(list)
for v in itertools.product(["+", "-", ""], repeat=9):
if v[0] != "+":
e = "".join("".join(u) for u in zip(v, s))
h[eval(e)].append(e)
print("Solutions for 100")
for e in h[100]:
print(e)
c = Counter({k: len(v) for k, v in h.items() if k >= 0})
k, m = c.most_common(1)[0]
print("Maximum number of solutions for %d (%d solutions)" % (k, m))
v = sorted(c.keys())
for i in range(v[-1]):
if i not in c:
print("Lowest impossible sum: %d" % i)
break
print("Ten highest sums")
for k in reversed(v[-10:]):
print(k)</syntaxhighlight>
{{out}}
<pre>Solutions for 100
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
Maximum number of solutions for 9 (46 solutions)
Lowest impossible sum: 211
Ten highest sums
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786</pre>
=={{header|Racket}}==
<
(define list-partitions
Line 2,621 ⟶ 5,828:
(check-equal? (partition-digits-to-numbers '()) '(()))
(check-equal? (partition-digits-to-numbers '(1)) '((1)))
(check-equal? (partition-digits-to-numbers '(1 2)) '((1 2) (12))))</
{{out}}
Line 2,644 ⟶ 5,851:
Show the ten highest numbers that can be expressed using the rules for this task
'(123456789 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786)</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.03}}
<syntaxhighlight lang="raku" line>my $sum = 100;
my $N = 10;
my @ops = ['-', ''], |( [' + ', ' - ', ''] xx 8 );
my @str = [X~] map { .Slip }, ( @ops Z 1..9 );
my %sol = @str.classify: *.subst( ' - ', ' -', :g )\
.subst( ' + ', ' ', :g ).words.sum;
my %count.push: %sol.map({ .value.elems => .key });
my $max-solutions = %count.max( + *.key );
my $first-unsolvable = first { %sol{$_} :!exists }, 1..*;
sub n-largest-sums (Int $n) { %sol.sort(-*.key)[^$n].fmt: "%8s => %s\n" }
given %sol{$sum}:p {
say "{.value.elems} solutions for sum {.key}:";
say " $_" for .value.list;
}
.say for :$max-solutions, :$first-unsolvable, "$N largest sums:", n-largest-sums($N);</syntaxhighlight>
{{out}}
<pre>12 solutions for sum 100:
-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 + 45 - 67 + 8 - 9
123 - 4 - 5 - 6 - 7 + 8 - 9
123 - 45 - 67 + 89
max-solutions => 46 => [-9 9]
first-unsolvable => 211
10 largest sums:
123456789 => 123456789
23456790 => 1 + 23456789
23456788 => -1 + 23456789
12345687 => 12345678 + 9
12345669 => 12345678 - 9
3456801 => 12 + 3456789
3456792 => 1 + 2 + 3456789
3456790 => -1 + 2 + 3456789
3456788 => 1 - 2 + 3456789
3456786 => -1 - 2 + 3456789</pre>
=={{header|REXX}}==
<
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO=
if HI=='' | HI=="," then HI=
if LO==00 then HI=
ops= '+-'; L= length(ops) + 1
@.=;
mx= 0; mn=
mxL=; mnL=; do j=LO to HI until LO==00 & mn==0
z=
if z> mx then
if z>=mx then do; mxL=mxL j; mx=z; end
if z< mn then
if z<=mn then do; mnL=mnL j; mn=z; end
end /*j*/
if LO==HI then exit 0 /*don't display max
@@= 'number of solutions: '; say
_= words(mxL); say 'sum's(_) "of" mxL ' 's(_,"have",'has') 'the maximum'
_= words(mnL); say 'sum's(_) "of" mnL ' 's(_,"have",'has') 'the minimum'
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
s:
/*──────────────────────────────────────────────────────────────────────────────────────*/
do
do
do
do
do
do
do
end /*i*/
end /*h*/
end /*g*/
end /*f*/
end /*e*/
end /*d*/
end /*c*/
end /*b*/
end /*a*/
<pre>
solution: 100 ◄───► -1+2-3+4+5+6+78+9
Line 2,713 ⟶ 5,971:
12 solutions found for 100
</pre>
<pre>
sum of 9 has the maximum number of solutions: 46
Line 2,720 ⟶ 5,978:
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">digits = ("1".."9").to_a
ar = ["+", "-", ""].repeated_permutation(digits.size).filter_map do |op_perm|
str = op_perm.zip(digits).join
str unless str.start_with?("+")
end
res = ar.group_by{|str| eval(str)}
puts res[100] , ""
sum, solutions = res.max_by{|k,v| v.size}
puts "#{sum} has #{solutions.size} solutions.", ""
no_solution = (1..).find{|n| res[n] == nil}
puts "#{no_solution} is the lowest positive number without a solution.", ""
puts res.max(10).map{|pair| pair.join(": ")}
</syntaxhighlight>
{{out}}
<pre>
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
9 has 46 solutions.
211 is the lowest positive number without a solution.
123456789: 123456789
23456790: 1+23456789
23456788: -1+23456789
12345687: 12345678+9
12345669: 12345678-9
3456801: 12+3456789
3456792: 1+2+3456789
3456790: -1+2+3456789
3456788: 1-2+3456789
3456786: -1-2+3456789
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use std::collections::BTreeMap;
use std::fmt;
#[derive(Copy, Clone)]
enum Operator {
None,
Plus,
Minus,
}
#[derive(Clone)]
struct Expression {
ops: [Operator; 9],
}
impl Expression {
fn new() -> Expression {
Expression {
ops: [Operator::None; 9],
}
}
fn sum(&self) -> i32 {
let mut result: i32 = 0;
let mut n: i32 = 0;
let mut p: i32 = 1;
let mut i: usize = 9;
while i > 0 {
n += p * (i as i32);
i -= 1;
match self.ops[i] {
Operator::None => p *= 10,
Operator::Plus => {
p = 1;
result += n;
n = 0;
}
Operator::Minus => {
p = 1;
result -= n;
n = 0;
}
}
}
result += n;
result
}
fn next(&mut self) -> bool {
let mut i: usize = 9;
while i > 0 {
i -= 1;
match self.ops[i] {
Operator::None => {
self.ops[i] = if i == 0 {
Operator::Minus
} else {
Operator::Plus
};
return true;
}
Operator::Plus => {
self.ops[i] = Operator::Minus;
return true;
}
Operator::Minus => self.ops[i] = Operator::None,
}
}
false
}
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for i in 0..9 {
match self.ops[i] {
Operator::None => {}
Operator::Plus => write!(f, "+")?,
Operator::Minus => write!(f, "-")?,
}
write!(f, "{}", i + 1)?;
}
Ok(())
}
}
fn main() {
let mut exp = Expression::new();
let mut sums: BTreeMap<i32, Vec<Expression>> = BTreeMap::new();
loop {
sums.entry(exp.sum()).or_insert(Vec::new()).push(exp.clone());
if !exp.next() {
break;
}
}
println!("Solutions that sum to 100:");
if let Some(expressions) = sums.get(&100) {
for e in expressions {
println!("100 = {}", e);
}
}
let mut max_sum = 0;
let mut max_count = 0;
for (sum, expressions) in &sums {
let count = expressions.len();
if count > max_count {
max_count = count;
max_sum = *sum;
}
}
println!(
"\nThe sum with the greatest number of solutions is {} ({}).",
max_sum, max_count
);
let mut n = 1;
while sums.contains_key(&n) {
n += 1;
}
println!(
"\nThe smallest positive number that cannot be expressed is {}.",
n
);
println!("\nThe ten highest numbers that can be expressed are:");
for (sum, expressions) in sums.iter().rev().take(10) {
println!("{} = {}", sum, expressions[0]);
}
}</syntaxhighlight>
{{out}}
<pre>
Solutions that sum to 100:
100 = -1+2-3+4+5+6+78+9
The sum with the greatest number of solutions is 9 (46).
The smallest positive number that cannot be expressed is 211.
The ten highest numbers that can be expressed are:
123456789 = 123456789
23456790 = 1+23456789
23456788 = -1+23456789
12345687 = 12345678+9
12345669 = 12345678-9
3456801 = 12+3456789
3456792 = 1+2+3456789
3456790 = -1+2+3456789
3456788 = 1-2+3456789
3456786 = -1-2+3456789
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="scala">object SumTo100 {
def main(args: Array[String]): Unit = {
val exps = expressions(9).map(str => (str, eval(str)))
val sums = exps.map(_._2).sortWith(_>_)
val s1 = exps.filter(_._2 == 100)
val s2 = sums.distinct.map(s => (s, sums.count(_ == s))).maxBy(_._2)
val s3 = sums.distinct.reverse.filter(_>0).zipWithIndex.dropWhile{case (n, i) => n == i + 1}.head._2 + 1
val s4 = sums.distinct.take(10)
println(s"""All ${s1.size} solutions that sum to 100:
|${s1.sortBy(_._1.length).map(p => s"${p._2} = ${p._1.tail}").mkString("\n")}
|
|Most common sum: ${s2._1} (${s2._2})
|Lowest unreachable sum: $s3
|Highest 10 sums: ${s4.mkString(", ")}""".stripMargin)
}
def expressions(l: Int): LazyList[String] = configurations(l).map(p => p.zipWithIndex.map{case (op, n) => s"${opChar(op)}${n + 1}"}.mkString)
def configurations(l: Int): LazyList[Vector[Int]] = LazyList.range(0, math.pow(3, l).toInt).map(config(l)).filter(_.head != 0)
def config(l: Int)(num: Int): Vector[Int] = Iterator.iterate((num%3, num/3)){case (_, n) => (n%3, n/3)}.map(_._1 - 1).take(l).toVector
def eval(exp: String): Int = (exp.headOption, exp.tail.takeWhile(_.isDigit), exp.tail.dropWhile(_.isDigit)) match{
case (Some(op), n, str) => doOp(op, n.toInt) + eval(str)
case _ => 0
}
def doOp(sel: Char, n: Int): Int = if(sel == '-') -n else n
def opChar(sel: Int): String = sel match{
case -1 => "-"
case 1 => "+"
case _ => ""
}
}</syntaxhighlight>
{{out}}
<pre>All 12 solutions that sum to 100:
100 = 123-45-67+89
100 = 123+45-67+8-9
100 = 123+4-5+67-89
100 = 1+23-4+5+6+78-9
100 = 123-4-5-6-7+8-9
100 = 12+3+4+5-6-7+89
100 = 12-3-4+5-6+7+89
100 = 1+2+34-5+67-8+9
100 = 12+3-4+5+67+8+9
100 = 1+23-4+56+7+8+9
100 = 1+2+3-4+5+6+78+9
100 = 1+2-3+4+5+6+78+9
Most common sum: 9 (46)
Lowest unreachable sum: 211
Highest 10 sums: 123456789, 23456790, 23456788, 12345687, 12345669, 3456801, 3456792, 3456790, 3456788, 3456786</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">func gen_expr() is cached {
var x = ['-', '']
var y = ['+', '-', '']
gather {
cartesian([x,y,y,y,y,y,y,y,y], {|a,b,c,d,e,f,g,h,i|
take("#{a}1#{b}2#{c}3#{d}4#{e}5#{f}6#{g}7#{h}8#{i}9")
})
}
}
func eval_expr(expr) is cached {
expr.scan(/([-+]?\d+)/).sum_by { Num(_) }
}
func sum_to(val) {
gen_expr().grep { eval_expr(_) == val }
}
func max_solve() {
gen_expr().grep { eval_expr(_) >= 0 } \
.group_by { eval_expr(_) } \
.max_by {|_,v| v.len }
}
func min_solve() {
var h = gen_expr().group_by { eval_expr(_) }
for i in (0..Inf) { h.exists(i) || return i }
}
func highest_sums(n=10) {
gen_expr().map { eval_expr(_) }.uniq.sort.reverse.first(n)
}
sum_to(100).each { say "100 = #{_}" }
var (n, solutions) = max_solve()...
say "Sum of #{n} has the maximum number of solutions: #{solutions.len}"
say "Lowest positive sum that can't be expressed : #{min_solve()}"
say "Highest sums: #{highest_sums()}"</syntaxhighlight>
{{out}}
<pre>
100 = -1+2-3+4+5+6+78+9
100 = 1+2+3-4+5+6+78+9
100 = 1+2+34-5+67-8+9
100 = 1+23-4+5+6+78-9
100 = 1+23-4+56+7+8+9
100 = 12+3+4+5-6-7+89
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123+45-67+8-9
100 = 123-4-5-6-7+8-9
100 = 123-45-67+89
Sum of 9 has the maximum number of solutions: 46
Lowest positive sum that can't be expressed : 211
Highest sums: [123456789, 23456790, 23456788, 12345687, 12345669, 3456801, 3456792, 3456790, 3456788, 3456786]
</pre>
=={{header|Tcl}}==
<
for {set i 0} {$i <= 13121} {incr i} {
set i3 [format %09d [dec2base 3 $i]]
Line 2,814 ⟶ 6,343:
return $res
}
sum_to_100</
<pre>
~ $ ./sum_to_100.tcl
Line 2,834 ⟶ 6,363:
highest 10:
123456789 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786
</pre>
=={{header|UNIX Shell}}==
{{works with|Korn Shell|93+}}
{{works with|Bourne Again SHell|4.0+}}
{{works with|Z Shell|4.0+}}
<syntaxhighlight lang=bash>sumto100() {
typeset expr sum max_count=0 max_values i
typeset -A histogram
printf 'Strings that evaluate to 100:\n'
for expr in {,-}1{,+,-}2{,+,-}3{,+,-}4{,+,-}5{,+,-}6{,+,-}7{,+,-}8{,+,-}9
do
(( sum = expr ))
if (( sum == 100 )); then
printf '\t%s\n' "$expr"
fi
histogram[$sum]=$(( ${histogram[$sum]:-0}+1 ))
if (( histogram[$sum] > max_count )); then
(( max_count = histogram[$sum] ))
max_values=( $sum )
elif (( histogram[$sum] == max_count )); then
max_values+=( $sum )
fi
done
printf '\nMost solutions for any number is %d: ' "$max_count"
if [[ -n $ZSH_VERSION ]]; then
printf '%s\n\n' "${(j:, :)max_values}"
else
printf '%s' "${max_values[0]}"
printf ', %s' "${max_values[@]:1}"
printf '\n\n'
fi
for (( i=1; i<123456789; ++i )); do
if (( !histogram[$i] )); then
printf "Lowest positive sum that can't be expressed: %d\n\n" "$i"
break
fi
done
printf 'Ten highest reachable numbers:\n';
if [[ -n $ZSH_VERSION ]]; then
printf '\t%9d\n' "${(k@)histogram}"
else
printf '\t%9d\n' "${!histogram[@]}"
fi | sort -nr | head -n 10
}
sumto100
</syntaxhighlight>
{{Out}}
<pre>Strings that evaluate to 100:
123+45-67+8-9
123+4-5+67-89
123-45-67+89
123-4-5-6-7+8-9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9
Most solutions for any number is 46: 9, -9
Lowest positive sum that can't be expressed: 211
Ten highest reachable numbers:
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786
</pre>
Line 2,840 ⟶ 6,450:
Another interesting thing this program can do is solve for other sets of numbers easily, as neither the number of digits, nor the digit sequence itself, is hard-coded. You could solve for the digits 1 through 8, for example, or the digits starting at 9 and going down to 1. One can even override the target sum (of 100) parameter, if you happen to be interested in another number.
<
Function plusOne(iAry() As Integer, spot As Integer) As Integer
Dim spotLim As Integer = If(spot = 0, 1, 2) ' The first "digit" has a lower limit.
Line 2,942 ⟶ 6,552:
Sub Main()
Solve100() ' if interested, try this: Solve100("987654321")
End Sub</
{{out}}
<pre>List of solutions that evaluate to 100:
Line 2,962 ⟶ 6,572:
123456789 23456790 23456788 12345687 12345669
3456801 3456792 3456790 3456788 3456786</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
{{libheader|Wren-set}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./dynamic" for Enum
import "./fmt" for Fmt
import "./set" for Set
import "./math" for Nums
import "./sort" for Sort
var Op = Enum.create("Op", ["ADD", "SUB", "JOIN"])
var NUMBER_OF_DIGITS = 9
var THREE_POW_4 = 3 * 3 * 3 * 3
var NUMBER_OF_EXPRESSIONS = 2 * THREE_POW_4 * THREE_POW_4
class Expression {
static print(givenSum) {
var expr = Expression.new()
for (i in 0...NUMBER_OF_EXPRESSIONS) {
if (expr.toInt == givenSum) Fmt.print("$9d = $s", givenSum, expr)
expr.inc
}
}
construct new() {
_code = List.filled(NUMBER_OF_DIGITS, Op.ADD)
}
inc {
for (i in 0..._code.count) {
_code[i] = (_code[i] == Op.ADD) ? Op.SUB : (_code[i] == Op.SUB) ? Op.JOIN : Op.ADD
if (_code[i] != Op.ADD) break
}
return this
}
toInt {
var value = 0
var number = 0
var sign = 1
for (digit in 1..9) {
var c = _code[NUMBER_OF_DIGITS - digit]
if (c == Op.ADD) {
value = value + sign * number
number = digit
sign = 1
} else if (c == Op.SUB) {
value = value + sign * number
number = digit
sign = -1
} else {
number = 10 * number + digit
}
}
return value + sign * number
}
toString {
var sb = ""
for (digit in 1..NUMBER_OF_DIGITS) {
var c = _code[NUMBER_OF_DIGITS - digit]
if (c == Op.ADD) {
if (digit > 1) sb = sb + " + "
} else if (c == Op.SUB) {
sb = sb + " - "
}
sb = sb + digit.toString
}
return sb.trimStart()
}
}
class Stat {
construct new() {
_countSum = {}
_sumCount = {}
var expr = Expression.new()
for (i in 0...NUMBER_OF_EXPRESSIONS) {
var sum = expr.toInt
_countSum[sum] = _countSum[sum] ? 1 + _countSum[sum] : 1
expr.inc
}
for (me in _countSum) {
var set = _sumCount.containsKey(me.value) ? _sumCount[me.value] : Set.new()
set.add(me.key)
_sumCount[me.value] = set
}
}
countSum { _countSum }
sumCount { _sumCount }
}
System.print("100 has the following solutions:\n")
Expression.print(100)
var stat = Stat.new()
var maxCount = Nums.max(stat.sumCount.keys)
var maxSum = Nums.max(stat.sumCount[maxCount])
System.print("\n%(maxSum) has the maximum number of solutions, namely %(maxCount)")
var value = 0
while (stat.countSum.containsKey(value)) value = value + 1
System.print("\n%(value) is the lowest positive number with no solutions")
System.print("\nThe ten highest numbers that do have solutions are:\n")
var res = stat.countSum.keys.toList
Sort.quick(res)
res[-1..0].take(10).each { |e| Expression.print(e) }</syntaxhighlight>
{{out}}
<pre>
100 has the following solutions:
100 = 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
100 = 1 + 2 + 34 - 5 + 67 - 8 + 9
100 = 1 + 23 - 4 + 5 + 6 + 78 - 9
100 = 1 + 23 - 4 + 56 + 7 + 8 + 9
100 = 12 + 3 + 4 + 5 - 6 - 7 + 89
100 = 12 + 3 - 4 + 5 + 67 + 8 + 9
100 = 12 - 3 - 4 + 5 - 6 + 7 + 89
100 = 123 + 4 - 5 + 67 - 89
100 = 123 + 45 - 67 + 8 - 9
100 = 123 - 4 - 5 - 6 - 7 + 8 - 9
100 = 123 - 45 - 67 + 89
100 = - 1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
9 has the maximum number of solutions, namely 46
211 is the lowest positive number with no solutions
The ten highest numbers that do have solutions are:
123456789 = 123456789
23456790 = 1 + 23456789
23456788 = - 1 + 23456789
12345687 = 12345678 + 9
12345669 = 12345678 - 9
3456801 = 12 + 3456789
3456792 = 1 + 2 + 3456789
3456790 = - 1 + 2 + 3456789
3456788 = 1 - 2 + 3456789
3456786 = - 1 - 2 + 3456789
</pre>
=={{header|zkl}}==
Taking a big clue from Haskell and just calculate the world.
<
(9).pump(List,fcn(n){ split("123456789"[n,*]) }) // 45
.apply(fcn(ns){ ns.extend(ns.copy().apply('*(-1))) }); // 90
Line 2,979 ⟶ 6,738:
}
// "123" --> (1,12,123)
fcn split(nstr){ (1).pump(nstr.len(),List,nstr.get.fp(0),"toInt") }</
<
slns:=allSums.find(N,T);
if(printSolutions) println("%d solutions for N=%d".fmt(slns.len(),N));
Line 2,999 ⟶ 6,758:
'wrap([(k,v)]){ v=v.len(); ms.holds(v) and T(k.toInt(),v) or Void.Skip })
.sort(fcn(kv1,kv2){ kv1[1]>kv2[1] }) // and sort
.println();</
{{out}}
<pre>
| |||