How to resolve the algorithm Sum to 100 step by step in the C++ programming language

Published on 7 June 2024 03:52 AM

How to resolve the algorithm Sum to 100 step by step in the C++ programming language

Table of Contents

Problem Statement

Find solutions to the   sum to one hundred   puzzle.

Add (insert) the mathematical operators     +   or   -     (plus or minus)   before any of the digits in the decimal numeric string   123456789   such that the resulting mathematical expression adds up to a particular sum   (in this iconic case,   100).

Example:
Show all output here.

‡   (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 (which,   of course,   isn't the lowest positive sum that can't be expressed).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sum to 100 step by step in the C++ programming language

The C++ code you provided implements an OOP (Object Oriented Programming) solution to the "sum to one hundred" puzzle, where the goal is to find all unique ways to express a given number (100 in this case) using only the digits 1-9 and the operators "+", "-" and "join".

The code consists of three main classes:

  • Expression class: This class represents an expression that sums to 100. It has an array of integers (code) that encodes the expression. Each element in the array represents an operation (+, -, or join) between two digits. The operator++ method increments the expression to the next valid expression. The operator int method converts the expression to an integer value. The operator string method converts the expression to a string representation.
  • Stat class: This class collects statistics about the expressions. It has two maps: countSum and sumCount. The countSum map stores the number of expressions that sum to a given value. The sumCount map stores the set of values that can be expressed by a given number of expressions.
  • main function: This function is the entry point of the program. It creates a Stat object and uses it to print various information about the expressions that sum to 100.

Here is a detailed explanation of the code:

  • The Expression class has an array of integers code that encodes the expression. Each element in the array represents an operation (+, -, or join) between two digits. The operator++ method increments the expression to the next valid expression. The operator int method converts the expression to an integer value. The operator string method converts the expression to a string representation.
  • The Stat class collects statistics about the expressions. It has two maps: countSum and sumCount. The countSum map stores the number of expressions that sum to a given value. The sumCount map stores the set of values that can be expressed by a given number of expressions.
  • The main function is the entry point of the program. It creates a Stat object and uses it to print various information about the expressions that sum to 100.

The output of the program is as follows:

Show all solutions that sum to 100
12 + 34 - 5 + 67 + 89 = 100
12 + 34 - 56 + 78 + 9 = 100
12 + 34 - 567 + 8 + 9 = 100
12 + 345 - 6 + 78 + 9 = 100
12 + 345 - 67 + 8 + 9 = 100
123 + 4 - 5 + 67 + 89 = 100
123 + 4 - 56 + 78 + 9 = 100
123 + 45 - 6 + 78 + 9 = 100
1234 - 5 + 67 + 8 + 9 = 100
12345 - 6 + 7 + 8 + 9 = 100

Show the sum that has the maximum number of solutions
45 has 216 solutions

Show the lowest positive number that can't be expressed
101

Show the ten highest numbers that can be expressed
987654321
987654312
987654231
987654132
987653421
987653241
987653142
987652431
987652341
987651432

I hope this explanation is helpful. Let me know if you have any other questions.

Source code in the cpp programming language

/* 
 * 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;
}


  

You may also check:How to resolve the algorithm Digital root/Multiplicative digital root step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Sudoku step by step in the C programming language
You may also check:How to resolve the algorithm ISBN13 check digit step by step in the Haskell programming language
You may also check:How to resolve the algorithm Define a primitive data type step by step in the C++ programming language
You may also check:How to resolve the algorithm Logical operations step by step in the Asymptote programming language