3
\$\begingroup\$

I was doing this exercise on codeabbey.

Andrew and Peter play the code-guessing game. Andrew chooses a secret number consisting of 3 digits. Peter tries to guess it, proposing several values, one by one.

For each guess Andrew should answer how many digits are correct - i.e. are the same in the proposed value and in his secret number - and are placed in the same position. For example, if secret number is 125 and Peter calls 523, then Andrew answers with 1

You are to write program which reads guesses given by Peter (except the last) and prints out the secret number choosen by Andrew. It is guaranteed that exactly one solution exists.

Input data will contain number of guesses in the first line. Then answers with attempts will follow - each contains the number told by Peter and the answer given by Andrew. In contrast with examples numbers will be of 4 digits. Answer should contain the secret number (also 4 digits).

There is also a better explanation of the requirements on the site itself.

Below is my code

main.cpp

#include <iostream>
#include <vector>
#include <set>

bool isgoodguess (bool flag[], int tempnum, std::set<int> &one, std::set<int> &two,   // good guesses are guesses that can show an answer, given the prior information.
                 std::set<int> &three, std::set<int> &four, int howmany) {

    int passnum;           // for ease of understanding. "howmany" is the number of correct digits.
    switch(howmany) {
        case 1:
            passnum = 3;   // but passnum is used to count if there are enough digits that were already removed so that
            break;         // we know if this is a good guess or not.
        case 2:
            passnum = 2;   // basically if the guess has 2 correct digits, we need to have 2 numbers that were already proven
            break;         // to be wrong, so that we know which two digits are correct.
    }
    int counter = 0;                                     // counter tracks how many digits can be proven to be wrong.

    if (one.find(tempnum/1000) == one.end()) {           // if this digit can not be found in the current set of possible values (i.e this digit is not correct)
        counter++;                                       // increase counter
        flag[0] = false;                                 // mark this particular digit as a false one.
    }
    else {
        flag[0] = true;                                  // else if this digit cannot be proven to be wrong yet, mark it as true.
    }
    if (two.find(tempnum%1000 / 100) == two.end()) {     // and so on.
        counter++;
        flag[1] = false;
    }
    else {
        flag[1] = true;
    }
    if (three.find(tempnum%100 / 10) == three.end()) {
        counter++;
        flag[2] = false;
    }
    else {
        flag[2] = true;
    }
    if (four.find(tempnum%10) == four.end()) {
        counter++;
        flag[3] = false;
    }
    else {
        flag[3] = true;
    }
    return (counter == passnum) ? true : false;         // if sufficient digits are proven false (a good guess since it helps to narrow down further), return true.
}

void check(std::vector<int> &tocheck, std::set<int> &one, std::set<int> &two,       // passing by reference the vectors and sets so that they can be changed from inside the function.
            std::set<int> &three, std::set<int> &four, int howmany) {               // howmany refers to how many digits are correct.

    std::vector<int>::iterator it = tocheck.begin();
    while(it != tocheck.end()) {                                                    // loop through the whole vector of guesses.
        bool flag[4];                                                               // required to check which digits out of the four are correct or wrong.

        if (isgoodguess(flag, *it, one, two, three, four, howmany)) {               // passing on values to a func which will determine if an answer can be found from that particular guess.
            if (flag[0] == true) {                      // if first digit is correct,
                one.clear();                            // remove the whole set of first digits
                one.insert(*it/1000);                   // insert the one correct value into the set.
            }
            if (flag[1] == true) {                      // repeat for other sets.
                two.clear();
                two.insert(*it%1000 / 100);
            }
            if (flag[2] == true) {
                three.clear();
                three.insert(*it%100 / 10);
            }
            if (flag[3] == true) {
                four.clear();
                four.insert(*it%10);
            }
            tocheck.erase(it);                          // remove this particular guess from the vector of guesses, not required anymore.
        }
        else {
            it++;
        }
    }
}


int main() {

    int cases;
    std::cin >> cases;
    int guess, correct;
    std::set<int> digit1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};              // create a set of possible values for first digit.
    std::set<int> digit2 = digit1, digit3 = digit1, digit4 = digit1;    // create 3 more sets of possible values for the other 3 digits.
    std::vector<int> guess1, guess2;                                    // for holding on to values with 1 correct digit and 2 correct digit respectively.

    for (int x = 0; x<cases; x++) {                                     // take in the number of guesses.
        std::cin >> guess >> correct;
        if (correct == 0) {                                             // if that guess has 0 answers, remove all the digits from their respective sets.
            digit1.erase(guess/1000);
            digit2.erase(guess%1000 / 100);
            digit3.erase(guess%100 / 10);
            digit4.erase(guess%10);
        }
        else if (correct == 1) {                                        // if that guess has 1 correct digit, add that value to vector guess1.
            guess1.push_back(guess);
        }
        else if (correct == 2) {                                        // if that guess has 2 correct digits, add that value to vector guess2.
            guess2.push_back(guess);
        }
    }

    while (digit1.size() > 1 || digit2.size() > 1 || digit3.size() > 1 || digit4.size() > 1) {   // while any position has not been narrowed down to one answer yet, repeat loop.
    check(guess1, digit1, digit2, digit3, digit4, 1);                   // passing vector 1, as well as all the set of possible digits, as well as "1" which means 1 correct.
    check(guess2, digit1, digit2, digit3, digit4, 2);
    }

    std::cout << *digit1.begin() << *digit2.begin() << *digit3.begin() << *digit4.begin();  // answer.
}

I am wondering if this is considered a good way to do it? What did I do wrongly or are there any other methods to do this?

Also, I have seen another person's code, and that person basically does it starting from number 1000 ( the first possible number ), and comparing if this number will produce the same answers. If it does not, the number increases by 1, until a correct answer is found. The code is below:

#include <bits/stdc++.h>
using namespace std;
vector <pair < int ,int> > code;
 pair <int,int> pp;
int codechecker(int no,int guess)
{
    int n[4],g[4],r1,r2,i=0;
    while(no>0)
    {
        r1 = no%10;
        n[i] = r1;
        no = no/10;
         r2 = guess%10;
        g[i] = r2;
        guess = guess/10;
        i++;
    }
    i=0;
    for(int j=0;j<4;j++)
    {
        if(n[j]==g[j])
        i++;
    }
    return i;
}
bool correct(int no)
{
    int size1 = code.size();
    for(int i=0;i<size1;i++)
    {
        pp = code[i];
        int m = codechecker(no,pp.first);
        if(m!=pp.second)
        return 0;
    }
    return 1;
}
int main()
{
    int N,a;
    cin>>N;
    
   
    for(int i=0;i<N;i++)
    {
        cin>>pp.first>>pp.second;
        code.push_back(pp);
    }
    for(int i=1000;i<=9999;i++)
    {
        if(correct(i))
        {
            a = i;
            break;
        }
    }
    cout<<"    "<<a;
    return 0;
}

My next question is: Is this person's code preferable to mine? It is much neater and shorter. It does not need many sets and vectors. However, having to test each number from 1000 - 9999 is not considered efficient right? Which method is actually better?

Thanks for taking the time to read through all these code. I am starting out so any feedback is valuable!

\$\endgroup\$
  • \$\begingroup\$ The limited scope of the windows of SE is a perfect reason why you should not use end-of-line commenting; just put the comment in front of the code. Modern practices may also include refactoring and variable renaming, which may make your statements even longer, moving the end-of-line comment to the right... \$\endgroup\$ – Maarten Bodewes Feb 11 at 15:11
  • \$\begingroup\$ I guess the first thing you should ask yourself is: is int really the best representation if you want to check individual digits? \$\endgroup\$ – Maarten Bodewes Feb 11 at 15:31
4
\$\begingroup\$

Hi and welcome to code review.

Your code is already ok, but there are several ways to improve both from the algorithm as well as the code style:

  1. Order includes lexicographically. This will ensure that you neither miss some nor forget some. Even better use clang-format so that it does it for you.

  2. Properly indent your code. Again this should be done via clang-format and will greatly improve readability of your code, regardless what codestyle you choose.

  3. Chose a readable naming convention A rather poor example is isgoodguess vs is_good_guess or isGoodGuess or any of the other naming conventions you choose. That said in most C++ codebases there is CamelCase for classes and camelCase for functions.

  4. Beware uninitialized variables. That code here is a ticking time bomb:

    int passnum;
    switch(howmany) {
        case 1:
            passnum = 3;
            break;         
        case 2:
            passnum = 2;   
            break;
    }
    

    Do you guarantee that howmany is eihter 1 or 2? what if it is 0? what if it is 3. You will use an uninitialized variable. Better write code that cannot fail.

    const int passnum = howmany == 1 ? 3 : 2;
    

    That code is much simpler. As a rule of thumb never leave a variable unitialized. There are very rare cases where it is actually valid, but that usually happens in library implementations.

  5. Use the correct data representation You are using int for representation. But that is actualy a poor choice. You want indvidual digits not an integer so I would suggest that you store the inputs in a std::string. You will still be able to compare the individual characters.

    Note that there is a std algorithm that you can use std::inner_product. Read it up and think about how you can use it on a range of two std::string

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the help, one thing I cannot figure out is how to use clang-format in codeblocks, the editor i am using. Should I be switching to visual studio or something to use clangformat? \$\endgroup\$ – Name Is HK Feb 12 at 13:44
4
\$\begingroup\$

This compiles with no warnings from a fairly pedantic compiler (g++ -std=c++2a -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) - well done!


Your program is closely tied to the number of digits in the secret number. If you wanted to adapt it to work with a five-digit number, you'd need to rework almost every part of it. A maintainable solution should have just one part that might need to change.


It's great that you have comments, but some are highly misleading:

int passnum;           // for ease of understanding. "howmany" is
                       // the number of correct digits.

(I wrapped this to a readable length - 70 columns is a well-established choice)

Looking at the code, it seems that howmany is nothing to do with the number of correct digits, but is always 0 or 1. It might be worth encoding that in an enum, and using values that directly correspond to the passnum value we want:

// values correspond to how many matches we're looking for
enum Pass {
           PASS_1 = 3;
           PASS_2 = 2;
};

// good guesses are guesses that can show an answer, given the prior information.
bool isgoodguess (bool flag[],
                  int tempnum,
                  std::set<int> &one, std::set<int> &two,
                  std::set<int> &three, std::set<int> &four,
                  Pass passnum)
{
    int counter = 0;
    ...
}
    while (...) {
        check(guess1, digit1, digit2, digit3, digit4, PASS_1);
        check(guess2, digit1, digit2, digit3, digit4, PASS_2);
    }

When reading from streams, always check that the stream is in a good state afterwards; if not, you can't rely on the streamed-into variables.

    int cases;
    if (!(std::cin >> cases)) {
        std::cerr << "Input format error!\n";
        return EXIT_FAILURE;    // needs <cstdlib>
    }

We have some long-winded boolean identities:

return (counter == passnum) ? true : false; 
        if (flag[0] == true) {

These can be simplified:

return counter == passnum; 
        if (flag[0]) {

With a little cleverness, we can simplify the if/else chains in isgoodguess(), e.g.:

if (four.find(tempnum%10) == four.end()) {
    counter++;
    flag[3] = false;
}
else {
    flag[3] = true;
}

We can say flag[3] = (four.find(tempnum%10) != four.end());, and then use the fact that booleans convert to integer 0 or 1 to increment counter only if false:

counter += !(flag[3] = four.find(tempnum%10) != four.end());

That's sufficiently non-obvious to be worth an explanatory comment, though.


We have an iterator invalidation problem here:

        tocheck.erase(it);

We subsequently use it (in the loop condition), but it's no longer valid. I think you meant to write:

        it = tocheck.erase(it);

In main(), it would be more natural to use a switch rather than an else if chain to choose between the different values of correct. Why do we ignore correct values of 3 or more?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the in depth reply. For the iterator, I was assuming that tocheck.erase(it) would remove that particular element in the vector, but since the iterator position didn't change, the iterator is now pointing to the next element in the vector, is that wrong? Also I wrote the code based on the question requirements, hence I didn't consider correct values of 3 or more, my mistake. Also, for the counter += !... example you gave, is there supposed to be another bracket? making it !( flag[3] = ( four.find( tempnum%10 ) != four.end() ) ); ?? \$\endgroup\$ – Name Is HK Feb 12 at 13:55
  • \$\begingroup\$ std::vector::erase() Invalidates iterators and references at or after the point of the erase, so yes, you were taking chances with the iterator. You could add the extra parentheses to the assignment of flag[3] if that makes it clearer to you, but they are not necessary because != is higher precedence than =. \$\endgroup\$ – Toby Speight Feb 12 at 14:25
3
\$\begingroup\$

I'll just do a code review and show you things that a beginning programmer should be aware of.

I won't go into the solution at all as the website already will show other attempts & solutions.

Generic remarks:

Don't use end of line comments, as they may become hard to read fast, especially if the line is expanded (for instance by a rename of a variable throughout the scope of the variable).

You are operating on digits. Then you need a sensible representation of a digit. You have chosen int (a character could also be a choice), but you're still doing integer arithmetic in your methods. That's just not necessary and will slow your solution down. What if tempnum - which really should be named guess - would be an int[], for instance? Would you have to perform all these calculations in the main loop?

What about a getDigit(int v, int off) if you want to convert between numbers and digits?

Walk-through

 bool isgoodguess (bool flag[], int tempnum, std::set<int> &one, std::set<int> &two,   // good guesses are guesses that can show an answer, given the prior information.
             std::set<int> &three, std::set<int> &four, int howmany) {

For this kind of method, you really need to write a method comment. It is unclear to the reader what flag means, and certainly what tempnum means.

The other thing here is that there are sets named one, two etc. A good application allows to test for 3 and 4 digits or even five. You you'd use a list or array of sets as input.

int passnum;           // for ease of understanding. "howmany" is the number of correct digits.

If you've already explained "howmany" in the method parameter description, this would be a good time to explain passnum instead.

switch(howmany) {
    cases...

A switch should be used sparingly, and if it is used on e.g. a number it should have a default (possibly throwing an exception).

int counter = 0;                                     // counter tracks how many digits can be proven to be wrong.

You mean a wrongDigitCounter? Prefer longer var names over comments. If that's hard during writing, simply rename after.

if (one.find(tempnum/1000) == one.end()) {           // if this digit can not be found in the current set of possible values (i.e this digit is not correct)
    counter++;                                       // increase counter
    flag[0] = false;                                 // mark this particular digit as a false one.
}
else {
    flag[0] = true;                                  // else if this digit cannot be proven to be wrong yet, mark it as true.
}
if (two.find(tempnum%1000 / 100) == two.end()) {     // and so on.
    counter++;
    flag[1] = false;
}
else {
    flag[1] = true;
}
if (three.find(tempnum%100 / 10) == three.end()) {
    counter++;
    flag[2] = false;
}
else {
    flag[2] = true;
}
if (four.find(tempnum%10) == four.end()) {
    counter++;
    flag[3] = false;
}
else {
    flag[3] = true;
}

Here the repetitiveness really jumps out. If you had an input array, I'm sure you could very easily do this in a loop, with just one piece of code in the middle. You can see this from the flag[1], flag[2] etc. If you are doing the counting then something is going wrong, basically.

std::set<int> digit1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};              // create a set of possible values for first digit.

A set of digit is called digits maybe. Again, repetition over 4. Where is the array?

std::set<int> digit2 = digit1, digit3 = digit1, digit4 = digit1;

Well, a C++ programmer probably would be sure that these are copied instead of referenced, as they are by-value, but don't do that in other languages.

Conclusion

In the end, it's a good attempt. But you would be surprised how few numbers would be in an attempt written by an experienced programmer. We may well have no number literals in there at all except maybe a zero 0 value now and then. There would not be any one named variables, or variables names ending with a number behind it either.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback. One thing though that I am still unsure, is it possible to create an array of sets? Like std::set<int> digits[4]; ? Regarding the repetitiveness though, i only did it that way because I wasn't sure how to make a loop that will change the set of digits it is iterating over each time. Because for the first round, it is find in set "one", but the second time it needs to look in set "two" \$\endgroup\$ – Name Is HK Feb 12 at 14:03
  • \$\begingroup\$ I'm not such a C++ programmer, but yeah, usually you can insert a collection in any other collection. For fun I wrote a different solution in Java using only 0, 1 and 9 as literal values and a variable number of digits. That's the problem with variables like one..four, you're in trouble if you count to three and ... five is right out. \$\endgroup\$ – Maarten Bodewes Feb 12 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.