improve my code

[ineedastupidusername]

Ugh, this forum seems to have infrequent posts (even less than the python forum which surprised me) which will make learning c++ harder. I'm from python and downloaded mingw/codeblocks on win7 2 days ago. I might switch to plain ansi c since a simpler language might be preferable and maybe struct can be a good enough replacement for oop. I find things created further in the past are generally better since humanity is devolving (example: books) and c came before c++.

Ok, so in the lounge of this forum I saw a problem (described in code below, and commented pretty good in general so u know what's going on hopefully, and can see all my failed embarrassing thinking or whatever). This is my first c++ program (it produces correct output), but it's probably all dumbified because I'm new to c++, so, like, suggest better implementations and stuff/how to improve/simplify/do same with less lines or whatever if you want (but I hate recursion which the other guy used and I don't understand). I'm more interested in getting a better handle on the language in general than recursion now anyway.

#include <iostream>
#include <math.h>
#include <string>

//THE PROBLEM: Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100.
//For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
//(from http://www.shiftedup.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour)

//OUTPUT OF THIS PROGRAM (only prints lines that total 100):
//1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 a a a a a
//1 + 2 + 34 - 5 + 67 - 8 + 9 a a a a a a a
//(plus 9 more for 11 total... I would paste all but don't know how to copy paste from output window which is annoying)

//MY DESCRIBED SOLUTION (I'm new to c++ so show me what to do better)
//9 numbers: 1,2,3,4,5,6,7,8,9 have 8 gaps between them. Fill gaps with every possible permutation of either a minus sign, a plus sign or a "concatenate sign". Since those are 3 choices and 8 gaps, that means
//you need all possible 8 digit ternary (base 3) numbers... 00000000,00000001,00000002,00000010 etc.. to fill gaps every possible way. 0 will represent +, 1 will be -, and 3 will be concatenate (means fuse like 3,4 becomes 34 etc)
//calculate every total this way and only print ones that = 100

//this function adds 1 to the base-3 number, 00000012 becomes 00000020 etc. it was annoying that "tris" array in this function had a name conflict with external "tris" array, so named external "ttris"
//8 nested ifs is probably dumb but I'm new to c++
int triinc(int tris[8]){
  tris[7]++;
  if (tris[7]==3){
    tris[7]=0;
    tris[6]++;
    if (tris[6]==3){
      tris[6]=0;
      tris[5]++;
      if (tris[5]==3){
        tris[5]=0;
        tris[4]++;
        if (tris[4]==3){
          tris[4]=0;
          tris[3]++;
          if (tris[3]==3){
            tris[3]=0;
            tris[2]++;
            if (tris[2]==3){
              tris[2]=0;
              tris[1]++;
              if (tris[1]==3){
                tris[1]=0;
                tris[0]++;
                if (tris[0]==3){
                  tris[0]=0;
                }
              }
            }
          }
        }
      }
    }
  }
}

//again annoying to name parameters different to avoid name conflicts.
int process(int ops[8],int ns[9]){
  //ops will be the 8 long list of base 3 numbers (0=+, 1=-, 2=concatenate)
  //ns is {1,2,3,4,5,6,7,8,9}
  //nstrs stands for number strings (because you can concatenate strings easily by adding them). I "pack" it full of letter "a"s to represent emptiness, before I fill it with numbers like 1, 2 or concatenated 34, etc
  //addsubs is another a packed empty list that will be left packed with list of ordered + or - operations only
  std::string nstrs[10]={std::to_string(ns[0]),"a","a","a","a","a","a","a","a","a"};
  std::string addsubs[10]={"a","a","a","a","a","a","a","a","a","a"};
  //these are indexes of above arrays respectively
  int nstrsi=0;
  int addsubsi=0;
  int i;
  for (i=0;i<8;i++){
    //concatenate to previous number if 2
    if (ops[i]==2){
      nstrs[nstrsi]+=std::to_string(ns[i+1]);
    }
    //if 0 or 1 add appropriate + or - symbol to addsubs, and add string number to next index of nstrs
    else if (ops[i]==1){
      addsubs[addsubsi]='-';
      addsubsi++;
      nstrsi++;
      nstrs[nstrsi]=std::to_string(ns[i+1]);
    }
    else if (ops[i]==0){
      addsubs[addsubsi]='+';
      addsubsi++;
      nstrsi++;
      nstrs[nstrsi]=std::to_string(ns[i+1]);
    }
  }
  //now nstrs and addsubs lists are created, so see if they total 100
  int total=std::stoi(nstrs[0]);
  i=0;
  while (addsubs[i]!="a"){
    if(addsubs[i]=="+"){
      total+=std::stoi(nstrs[i+1]);
    }
    else if(addsubs[i]=="-"){
      total-=std::stoi(nstrs[i+1]);
    }
    i++;
  }
  //print out if total==100
  if (total==100){
    for(i=0;i<10;i++){
      std::cout<<nstrs[i]<<" "<<addsubs[i]<<" ";
    }
    std::cout<<"\n";
  }
}

int main(){
  int i;
  //8 digit ternary (base 3) numbers... 00000000,00000001,00000002,00000010 etc.. 0 will represent +, 1 will be -, and 3 will be concatenate (means fuse like 3,4 becomes 34 etc)
  int ttris[8]={0,0,0,0,0,0,0,0};
  int nums[9]={1,2,3,4,5,6,7,8,9};
  bool running=true;
  int ccount=0;
  while(running){
      process(ttris,nums);
      triinc(ttris);
      //was annoying I couldn't easily compare equality of 2 arrays in below line
      //if (tris=={2,2,2,2,2,2,2,2}){
      ccount++;
      if (ccount>=pow(3,8)-1){
        running=false;
      }
  }
}

[jonnin]

Structs can do OOP but function pointers are very ugly. However OOP is often over-rated for small programs. If your target projects are small, OOP C isn't too bad.

Its <cmath> for the math header. math.h is pre namespace / C version.

see if this is what you had, condensed. I think I did it right. dx >= 0 may be redundant.

int triinc(int tris[8])  //this is int but returns no value, should it be void?
{
    tris[7]++;
    int dx = 7;
   while(tris[dx]==3 && dx >= 0)
       {        
            tris[dx]=0;
            if(dx)
               tris[dx-1]++;
            --dx;
       }
   }
} 

you can compare equality of vectors. Use vectors instead of arrays. It won't change the code much.

int i in main appears to be unused.

pow(3,8) -1 is a constant. Just use the constant and if you feel compelled put a comment that its 3 to 8.

generally it looks great for a first try, and far more complex than most first programs. Apart from the huge "I didn't know how to loop it" function and the lack of vectors, its excellent.

[ineedastupidusername]

Thanks for the feedback. I had some brief practice in plain c before, and also this language for the game Doom that was very similar to c, and python, so I guess that's why it's not too horrible for a "first" c++ try (actually I did hello world first, plus tutorial stuff).
Good solution (verified works, except the extra }, and yeah the && dx >=0 tested to indeed be redundant which is confusing to think about. I think dx eventually gets to -1. In python mylist[-1] reaches the last element, but it seemingly produces a junk value in c++. So I guess that junk value very likely won't == 3 thus making the loop end (but better to have the && dx>=0 because the junk could potentially be 3 I guess.

In python you can have a list and append to it, changing length. [5,4] to [5,4,7] etc.. So I think to make your function work for any sized array, you'd have to use an overly large array like length 100, then dummy pack it with 'a's or something (like I did) or include a myarrayLength variable and only go up to that length (even though the real array is 100 long).

pow() and std::pow() both worked (didn't have to type "using" something like the tutorial mentioned) whether I used math.h or cmath (stackoverflow seemed to think math.h is better, dunno, https://stackoverflow.com/questions/10694255/c-cmath-vs-math-h-and-similar-c-prefixed-vs-h-extension-headers).

So if main has variable "tris" then "tris" can't also be a parameter name for an external function?

ha ha, I think I had int i in main for code I commented out then deleted. I'll look into vectors. Oh yeah, use a constant, because otherwise it does unnecessary calculation (4^8-1) every loop iteration=innefficient I assume?

I think my main languages should be javascript (for internet games) and c++ for fast code that can make exe files and easy access to byte related stuff like "long" or "char" in order to hopefully be able to manipulate file formats like .wav. Trying that sucked in python. In the windows sub-forum I mentioned how I'm trying to make/edit matroska files (since I suppose they're more open/easier than mp4 etc) in order to make an animation video match an mp3 song's tempo. I'd probably create individual images programmatically first, then turn the images into a video to match the mp3 song tempo.

[jonnin]

normal pointers and arrays and vectors are indexed from 0 to size-1. You *can* take a pointer to the middle of another valid block and use negative indexing, but it is usually a bad idea.

consider...
char blok[30];
char* magic = &blok[15];
magic[-3] = 'h'; //I think this is legal. C++ has gotten more grouchy about hackery though and the kind folks here keep correcting me on what is legal vs what works. If this isnt legal, it works on most compilers. But its really not a great idea to do it.

you can append to vectors and lists in c++. Arrays and home-rolled pointer code, no. Most programmers use vectors instead of arrays now.

math.h is identical to cmath except for a namespaceing change that was added to it. But you should use cmath in c++ code, even if it works both ways.

if main has a variable tris and you have a function called tris, you can't call the funciton from main (it keeps seeing the variable). You can get around this with namespaces, but I strongly advise against doing it as it makes code hard to follow even with the namespace qualifier.

right, there is no reason to keep doing the pow function on a constant result. Pow specifically is notoriously slow and most programmers do squares and cubes directly (x*x instead of pow(x,2) ). You can get better, faster answers by writing your own function for small integer powers. pow excels at decimal powers and more difficult problems, though. There are not many examples like this (where the built in function is slow), its an anomaly.

sounds like a fun project. Way way back I did all that in uncompressed AVI format which basically let you hack on each frame as if it were an RGB array. Then at the end I would apply a compression to the finished video. That made the code simple, but it was a little slow.

[lastchance]

Sorry, I split @Jonnin's replies. Moved to later.

[jonnin]

by the way you can actually define a sub-byte chunk. You could actually allocate an array of 3-bit values and set up the math on it and all the trimmings. I haven't needed it, used to be a weird : syntax for a 'bitfield' but now I think c++ has a bitset (?) type for this sort of thing.

Or you could just do all the math like normal (which is binary in the CPU and byte-wise in memory) and have a specialty print statement to convert to base 3. I think that is what the above is doing, but not 100% sure.

On recursion:
you should make peace with it. You don't have to use it often (only a tiny # of algorithms are extremely difficult to write without it and simple with it) but for those cases as well as understanding other people's code (some programmers are obsessed with it) you should get a good handle on the technique. Conceptually it is really simple ... you have a 'base case' that returns a simple computation and all other computations are expressed as a simpler form of the original problem. The factorial is the classic example... N! is the same as N*(N-1)! where N is bigger than 1, and 1 is a base case that returns 1 (1! = 1). so the function looks like ...

int fact(int n)
{
if(n == 1) return 1;
else return n*(fact(n-1);
}

naturally this is an overly simple example but all recursion follows that pattern of base case(s) and calling itself with a reduced problem.

[lastchance]

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int main()
{
   const int TARGET = 100;
   int i, total;
   vector<string> all = { "1" };                 // Will hold all 3^8 legitimate combinations as a string

   for ( i = 2; i <= 9; i++ )                    // Add each following digit with either -, + or nothing
   {
      char c = (char)( '0' + i );
      vector<string> temp;
      for ( string s : all )                     // For each previous string there will be three new ones
      {
         temp.push_back( s + '-' + c );
         temp.push_back( s + '+' + c );
         temp.push_back( s + c );
      }
      all = temp;
   }

   // Now evaluate results by stringstreaming +n or -n into integers
   vector<string> matches;
   for ( string s : all )  
   {
      stringstream ss( s );
      ss >> total;
      while ( ss >> i ) total += i;
      if ( total == TARGET ) matches.push_back( s );
   }

   // Write results
   cout << "There are " << matches.size() << " possibilities:\n";
   for ( string s : matches ) cout << s << '\n';
}

There are 11 possibilities:
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

Hmm, can't work out what the originator of the problem was doing though.
http://www.shiftedup.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions

I think my solution goes down as "brute force", compared with proper programming.

[ineedastupidusername]

lastchance, that's nice short code (and 2.5x faster than mine). I don't understand some stuff yet: It sure is weird how it appears to have few loops (the main loop is an i that goes from 2 to 9 just once, not even sure why it starts on 2) yet it still does all the work.
line 15: char c = (char)( '0' + i );
I'm currently unfamiliar with char twice, 2nd time in parenthesis? add int i to char '0'? It appears to overall convert int i to char i
line 17: for ( string s : all )
I'm currently unfamiliar with that type of for (I just know for(i;i<10;i++). Also it seems like vector all only has a single "1" in it at this time so you maybe loop s through a vector with just a single "1" in it?

jonnin, if you used avi to do it already, then you already talked me into using avi instead. I have very low hope for success. If I know someone else did it with avi, I should be on the right track at least.

[jonnin]

this is crucial. Char is an integer.
(char) is an older style cast that is simply easier to type than some_sort_of_excessively_long_named_other_cast<type> . This casts the target expression back to char (though from the looks of it, it already was a char, it may clear a warning)

chars use the ascii table (or other tables, that is the American one) or Unicode (a whole different set of aggravations) but you need to understand that the symbols you see on the screen are pixel representations of an integer. so 'A' + 1 is 'B' in Ascii. This is handy from time to time, esp since '0' + 1 is '1'.

AVI is just a simple video format that CAN be configured to be effectively an array of frames (instead of smarter compressed formats like mpeg based compression which only stores the changed pixels each frame for a while then gets a new frame and repeats that). It just removes the compression hassle from you code. But the files are HUGE, megabytes to the second of video.

[lastchance]

Regarding the (char) cast, yes, @jonnin is right, it was already a char, so unnecessary. '0'+i is a standard way of converting from integer to the corresponding character, since it is the ith character along from '0'.

"Range-based for loops" came in with c++11, so make sure that your textbook includes that (or, as I did, learn from this forum).

The definition of the problem says that all strings start from "1" ... so that is line 11. The remaining digits are 2 to 9, so that's the range of the second loop. There's nothing wrong with a loop over just one element the first time.

By some of the solutions I saw this probably wasn't very good programming - at the end of line 24 vector all contains all possible combinations of strings fulfilling the conditions and then I simply had to evaluate them. Brute force. However, I did at least check the numbers involved to see if this was practical and would fit in memory.