Sum to 100: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 32:
<sup>*</sup> (where ''infinity'' would be a relatively small 123,456,789)
<br><br>
=={{header|Ada}}==
Line 824 ⟶ 825:
123-4-5-6-7+8-9
123-45-67+89</pre>
=={{header|AWK}}==
{{trans|Fortran IV}}
Line 1,246 ⟶ 1,248:
{{Out}}
<pre>Show all solutions that sum to 100
100 = 1+2+3-4+5+6+78+9
Line 1,596 ⟶ 1,444:
</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.
<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;
}</lang>
{{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}}==
Line 1,836 ⟶ 1,833:
3456788 = 1-2+3456789
3456786 = -1-2+3456789</pre>
=={{header|Elixir}}==
Line 1,907 ⟶ 1,903:
</pre>
=={{header|F_Sharp|F#}}==
<lang fsharp>
(*
Generate the data set
Nigel Galloway February 22nd., 2017
*)
type N = {n:string; g:int}
let N = seq {
let rec fn n i g e l = seq {
match i with
|9 -> yield {n=l + "-9"; g=g+e-9}
yield {n=l + "+9"; g=g+e+9}
yield {n=l + "9"; g=g+e*10+9*n}
|_ -> yield! fn -1 (i+1) (g+e) -i (l + string -i)
yield! fn 1 (i+1) (g+e) i (l + "+" + string i)
yield! fn n (i+1) g (e*10+i*n) (l + string i)
}
yield! fn 1 2 0 1 "1"
yield! fn -1 2 0 -1 "-1"
}
</lang>
{{out}}
<lang fsharp>
N |> Seq.filter(fun n->n.g=100) |> Seq.iter(fun n->printfn "%s" n.n)
</lang>
<pre>
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-6-7+8-9
123-45-67+89
123+4-5+67-89
123+45-67+8-9
-1+2-3+4+5+6+78+9
</pre>
<lang fsharp>
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
</lang>
<pre>
9 has 46 solutions
</pre>
<lang fsharp>
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"
</lang>
<pre>
least non-value is 211
</pre>
<lang fsharp>
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 )
</lang>
<pre>
123456789
23456790
23456788
12345687
12345669
3456801
3456792
3456790
3456788
3456786
</pre>
=={{header|Forth}}==
Line 2,503 ⟶ 2,568:
23456790
123456789
</pre>
Line 3,854 ⟶ 3,849:
{{out}}
[3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789]
=={{header|Julia}}==
Line 4,878 ⟶ 4,872:
3456786
</pre>
=={{header|Phix}}==
Line 5,260 ⟶ 5,204:
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}}
<lang perl6>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);</lang>
{{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}}==
| |||