Sum to 100: Difference between revisions
m
Minor edit to Rust code
(add FreeBASIC) |
m (Minor edit to Rust code) |
||
(11 intermediate revisions by 7 users not shown) | |||
Line 36:
{{trans|Kotlin}}
<
NUMBER_OF_DIGITS = 9
THREE_POW_4 = 3 * 3 * 3 * 3
Line 112:
print("\nThe ten highest numbers that do have solutions are:\n")
L(i) sorted(stat.countSum.keys(), reverse' 1B)[0.<10]
printe(i)</
{{out}}
Line 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 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 209:
end Print;
end Sum_To;</
===The First Subtask===
Line 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 224:
begin
Eval_100;
end Sum_To_100;</
{{out}}
Line 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 310:
end loop;
New_Line;
end Three_others;</
{{out}}
Line 322:
=={{header|Aime}}==
<
index r, w;
Line 383:
break;
}
}</
{{Out}}
<pre>123-45-67+89
Line 411:
=={{header|ALGOL 68}}==
<
# find the numbers the string 123456789 ( with "+/-" optionally inserted #
# before each digit ) can generate #
Line 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 523 ⟶ 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 541 ⟶ 540:
print( ( newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
Line 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 879:
end script
end if
end mReturn</
{{Out}}
<pre>Sums to 100:
Line 897:
=={{header|AutoHotkey}}==
<
for k, v in (sum2num(100))
output .= k "`n"
Line 952:
DllCall("msvcrt.dll\" v, "Int64", value, "Str", s, "UInt", OutputBase, "CDECL")
return s
}</
{{out}}
<pre>
Line 978:
{{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.
#
Line 1,084:
limit = best
}
}</
{{Out}}
<pre>Show all solutions that sum to 100
Line 1,127:
{{Works with|Microsoft Visual Studio|2015}}
Warning: '''this version requires at least four byte integers.'''
<
* RossetaCode: Sum to 100, C99, an algorithm using ternary numbers.
*
Line 1,262:
return 0;
}</
{{Out}}
<pre>
Line 1,309:
{{Works with|GCC|5.1}}
Warning: '''this program needs at least four byte integers'''.
<
* RossetaCode: Sum to 100, C11, MCU friendly.
*
Line 1,394:
return 0;
}</
{{Out}}
<pre>Show all solutions that sum to 100
Line 1,434:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
using System.Linq;
Line 1,560:
return left;
}
}</
{{out}}
<pre>
Line 1,597:
{{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.).
Line 1,707:
return 0;
}</
{{Out}}
<pre>
Line 1,748:
=={{header|Common Lisp}}==
<
"Takes a list of digits as argument"
(if (null lst)
Line 1,769:
(parse-integer (format nil "~{~d~}" lst)) ))
</syntaxhighlight>
{{out}}
<pre>
Line 1,792:
=={{header|D}}==
{{Trans|Java}}
<
void main() {
Line 1,944:
}
}
}</
{{out}}
Line 1,985:
=={{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 2,032 ⟶ 2,177:
Sum.max_solve
Sum.min_solve
Sum.highest_sums</
{{out}}
Line 2,054 ⟶ 2,199:
3456788, 3456786]
</pre>
=={{header|F_Sharp|F#}}==
<
(*
Generate the data set
Line 2,077 ⟶ 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 2,096 ⟶ 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 2,130 ⟶ 2,273:
{{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.
<
CREATE 0OPS CHAR - C, CHAR # C,
CREATE BUFF 43 C, 43 CHARS ALLOT
Line 2,181 ⟶ 2,324:
: .SOLUTIONS cr ." Solutions that sum to 100:"
BEGIN SYNTH EVALUATE REPORT INDX+ UNTIL ;
: SUM100 .SOLUTIONS .MOST .CANT .BEST cr ;</
{{Out}}
Note: must start Gforth with a larger-than-default dictionary size:
Line 2,340 ⟶ 2,483:
=== Fortran 95 ===
{{works with|gfortran|5.1}}
<
!
! Find solutions to the 'sum to one hundred' puzzle.
Line 2,470 ⟶ 2,613:
ivalue = ievaluate(icode)
print *, ivalue, ' = ', s
end</
{{Out}}
<pre>
Line 2,511 ⟶ 2,654:
===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. <
PARAMETER (NDIGITS = 9, TARGET = 100)
INTEGER*1 OP(NDIGITS) !A set of operation codes, associated with each digit.
Line 2,617 ⟶ 2,760:
WRITE (MSG,322) VALUE(LOOP - 9:LOOP) !Surely LOOP > 9.
322 FORMAT ("The ten highest sums: ",10(I0:","))
END !That was fun!</
Results:
Line 2,643 ⟶ 2,786:
=={{header|FreeBASIC}}==
<
#define PERM 13122
Line 2,734 ⟶ 2,877:
print eqn
sum(champ) = -9999 'overwrite to stop this being found a second time
next i</
{{out}}<pre>
-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9 = 100
Line 2,764 ⟶ 2,907:
=={{header|Frink}}==
<
digits = array[1 to 9]
opList = makeArray[[8], ["", " + ", " - "]]
Line 2,813 ⟶ 2,956:
for i = size-10 to size-1
println[freq@i@0]
</syntaxhighlight>
{{out}}
<pre>
Line 2,847 ⟶ 2,990:
=={{header|Go}}==
{{trans|C}}
<
import (
Line 2,996 ⟶ 3,139:
fmt.Println(e)
}
}</
{{out}}
<pre>
Line 3,033 ⟶ 3,176:
=={{header|Haskell}}==
<
import Data.Char (intToDigit)
import Data.List
Line 3,150 ⟶ 3,293:
String
maybeReport (Just (x, _)) = show x
maybeReport _ = "No gaps found"</
{{Out}}
(Run in Atom editor, through Script package)
Line 3,181 ⟶ 3,324:
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
Line 3,192 ⟶ 3,335:
'Ten largest:';,.(->:i.10){ss
'First not expressible:';>:pos{~ 1 i.~ 1<|2-/\pos
</syntaxhighlight>
{{out}}
<pre>
Line 3,234 ⟶ 3,377:
{{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 3,401 ⟶ 3,544:
}
}
}</
{{Out}}
<pre>Show all solutions that sum to 100
Line 3,442 ⟶ 3,585:
===ES5===
{{Trans|Haskell}}
<
'use strict';
Line 3,668 ⟶ 3,811:
show(take(10, uniqueNonNegativeSums.sort(flip(compare))))
].join('\n') + '\n';
})();</
{{Out}}
Line 3,705 ⟶ 3,848:
===ES6===
{{Trans|Haskell}}
<
'use strict';
Line 3,888 ⟶ 4,031:
show(take(10, uniqueNonNegativeSums.sort(flip(compare))))
].join('\n') + '\n';
})();</
{{Out}}
Line 3,926 ⟶ 4,069:
{{Works with|Microsoft Windows Script Host}}
{{Trans|AWK}}
<
function SumTo100()
Line 4,048 ⟶ 4,191:
}
</syntaxhighlight>
{{Out}}
<pre>Show all solutions that sum to 100
Line 4,090 ⟶ 4,233:
'''All possible sums'''
<
def generate(n):
def pm: ["+"], ["-"], [""];
Line 4,110 ⟶ 4,253:
# 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'''
<
{{out}}
<pre>
Line 4,132 ⟶ 4,275:
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.
<
# Emit an array of [ value, frequency ] pairs
Line 4,140 ⟶ 4,283:
| sort_by(.[1])
| .[(length-n):]
| reverse ; </
'''Maximum number of solutions'''
<
{{out}}
<pre>[["9",46]]</pre>
'''Ten most frequent sums'''
<
{{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'''
<
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[])</
{{out}}
211
'''Ten largest sums'''
<
{{out}}
[3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789]
=={{header|Julia}}==
<
expr(p::String...)::String = @sprintf("%s1%s2%s3%s4%s5%s6%s7%s8%s9", p...)
Line 4,226 ⟶ 4,369:
println("\nHighest sums representable:")
foreach(println, hsums)
</
<pre>100 =
1+23-4+56+7+8+9
Line 4,261 ⟶ 4,404:
=={{header|Kotlin}}==
{{trans|C++}}
<
class Expression {
Line 4,361 ⟶ 4,504:
println("\nThe ten highest numbers that do have solutions are:\n")
stat.countSum.keys.toIntArray().sorted().reversed().take(10).forEach { Expression.print(it) }
}</
{{out}}
Line 4,400 ⟶ 4,543:
=={{header|Lua}}==
{{trans|C}}
<
function compareExpressionBySum(a, b)
return a.sum - b.sum
Line 4,522 ⟶ 4,665:
end
limit = best
end</
{{out}}
<pre>Show all solutions that sum to 100
Line 4,558 ⟶ 4,701:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Defining all possible sums:
<
sums = Map[StringJoin[Riffle[#, CharacterRange["1", "9"]]] &, operations];</
Sums to 100:
<
{{out}}
<pre>-1+2-3+4+5+6+78+9
Line 4,577 ⟶ 4,720:
Maximum number of solutions:
<
{{out}}
<pre> <|9 -> 46, -9 -> 46|> </pre>
First unsolvable:
<
n = 1; While[MemberQ[pos, n], ++n]; </
{{out}}
<pre>211</pre>
Ten largest sums:
<
{{out}}
<pre> 123456789 123456789
Line 4,603 ⟶ 4,746:
=={{header|Modula-2}}==
{{trans|C}}
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 4,740 ⟶ 4,883:
ReadChar
END SumTo100.</
{{out}}
<pre>Show all solutions that sum to 100
Line 4,777 ⟶ 4,920:
Recursive solution.
<
type Expression = string
Line 4,818 ⟶ 4,961:
echo "\nThe ten highest numbers than can be expressed are:"
let numbers = sorted(toSeq(counts.keys), Descending)
echo numbers[0..9].join(", ")</
{{out}}
Line 4,844 ⟶ 4,987:
Iterative previous solution written in French (updated).
<
var
Line 4,919 ⟶ 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 4,955 ⟶ 5,098:
{{works with|Lazarus}}
{{trans|C}}
<
Find solutions to the "sum to one hundred" puzzle.
Line 5,080 ⟶ 5,223:
limit := best;
end
end.</
{{Out}}
<pre>Show all solutions that sum to 100
Line 5,121 ⟶ 5,264:
=={{header|Perl}}==
{{works with|Perl|5.10}}
<
use warnings;
use strict;
Line 5,182 ⟶ 5,325:
say 'Show the ten highest numbers that can be expressed';
say for (sort { $b <=> $a } keys %count)[0 .. 9];</
{{Out}}
<pre>Show all solutions that sum to 100
Line 5,216 ⟶ 5,359:
===oneliner version===
The first task posed can be solved simply with (pay attention to doublequotes around the program: adjust for you OS):
<
perl -E "say for grep{eval $_ == 100} glob '{-,}'.join '{+,-,}',1..9"
</syntaxhighlight>
While the whole task can be solved by:
<
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>
Line 5,257 ⟶ 5,400:
Admittedly, categorising them into 3429 bins is slightly more effort, but otherwise I am somewhat bemused by all the applescript/javascript/Haskell shenanegins.<br>
<!--<
<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>
Line 5,342 ⟶ 5,485:
<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>
<!--</
{{Out}}
Line 5,364 ⟶ 5,507:
The 10 highest sums: {123456789,23456790,23456788,12345687,12345669,3456801,3456792,3456790,3456788,3456786}
</pre>
=={{header|Picat}}==
<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}}==
<
#STOPP=19682
#SUMME=100
Line 5,438 ⟶ 5,595:
EndIf
Input()
EndIf</
{{out}}
<pre>Show all solutions that sum to 100:
Line 5,472 ⟶ 5,629:
=={{header|Python}}==
<
Line 5,522 ⟶ 5,679:
max_solve()
min_solve()
highest_sums()</
{{out}}
Line 5,544 ⟶ 5,701:
Mostly the same algorithm, but both shorter and faster.
<
from collections import defaultdict, Counter
Line 5,572 ⟶ 5,729:
print("Ten highest sums")
for k in reversed(v[-10:]):
print(k)</
{{out}}
Line 5,605 ⟶ 5,762:
=={{header|Racket}}==
<
(define list-partitions
Line 5,671 ⟶ 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 5,699 ⟶ 5,856:
{{works with|Rakudo|2017.03}}
<syntaxhighlight lang="raku"
my $N = 10;
my @ops = ['-', ''], |( [' + ', ' - ', ''] xx 8 );
Line 5,717 ⟶ 5,874:
}
.say for :$max-solutions, :$first-unsolvable, "$N largest sums:", n-largest-sums($N);</
{{out}}
<pre>12 solutions for sum 100:
Line 5,747 ⟶ 5,904:
=={{header|REXX}}==
<
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 100 /*Not specified? Then use the default.*/
Line 5,797 ⟶ 5,954:
if LO\==00 then say right(y, 9) 'solution's(#, , " ") 'found for' ,
right(j, length(HI) ) left('', #, "─")
return # /*return the number of solutions found.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 5,821 ⟶ 5,978:
=={{header|Ruby}}==
<
ar = ["+", "-", ""].repeated_permutation(digits.size).filter_map do |op_perm|
Line 5,838 ⟶ 5,995:
puts res.max(10).map{|pair| pair.join(": ")}
</syntaxhighlight>
{{out}}
<pre>
Line 5,868 ⟶ 6,025:
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 = 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 = -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}}==
<
def main(args: Array[String]): Unit = {
val exps = expressions(9).map(str => (str, eval(str)))
Line 5,904 ⟶ 6,225:
case _ => ""
}
}</
{{out}}
<pre>All 12 solutions that sum to 100:
Line 5,926 ⟶ 6,247:
=={{header|Sidef}}==
{{trans|Ruby}}
<
var x = ['-', '']
var y = ['+', '-', '']
Line 5,965 ⟶ 6,286:
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()}"</
{{out}}
<pre>
Line 5,986 ⟶ 6,307:
=={{header|Tcl}}==
<
for {set i 0} {$i <= 13121} {incr i} {
set i3 [format %09d [dec2base 3 $i]]
Line 6,022 ⟶ 6,343:
return $res
}
sum_to_100</
<pre>
~ $ ./sum_to_100.tcl
Line 6,042 ⟶ 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 6,048 ⟶ 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 6,150 ⟶ 6,552:
Sub Main()
Solve100() ' if interested, try this: Solve100("987654321")
End Sub</
{{out}}
<pre>List of solutions that evaluate to 100:
Line 6,178 ⟶ 6,580:
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<
import "./fmt" for Fmt
import "./set" for Set
import "./math" for Nums
import "./sort" for Sort
var Op = Enum.create("Op", ["ADD", "SUB", "JOIN"])
Line 6,283 ⟶ 6,685:
var res = stat.countSum.keys.toList
Sort.quick(res)
res[-1..0].take(10).each { |e| Expression.print(e) }</
{{out}}
Line 6,322 ⟶ 6,724:
=={{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 6,336 ⟶ 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 6,356 ⟶ 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>
|