Sum to 100: Difference between revisions

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++}}==

{{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

</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

=={{header|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>