dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: Beginner's question regarding arrays

  1. #1
    Join Date
    May 2006
    Posts
    102

    Beginner's question regarding arrays

    I'm making a "war" style card game. For the sake of explanation, assume that there are only 10 available cards valued 1 through 10. At the start of the game, 5 of the cards will be randomly given to Player 1 and the other 5 will be given to Player 2.

    So far, I have three int arrays. The first array represents the total available cards (i.e. int cards[10]...); the 2nd array is Player 1's cards and the 3rd array is Player 2's cards.

    My question is about the "deal" of the cards. Specifically, how can I take an element from the 1st array and place it into either the 2nd or 3rd array in such a way that the same element cannot later be randomly picked again? For example, is player 1 is given card #5, how can I ensure that either player 1 or player 2 doesn't end up with a second #5 card?

    Thanks.

  2. #2
    Join Date
    Mar 2002
    Location
    Kent, United Kingdom
    Posts
    399

    Re: Beginner's question regarding arrays

    There are going to be many ways to do this

    I would suggest you change your cards from an int to a class that has a member variable indicating which player owns it.
    You would then only need one array holding all cards, I would also suggest using a vector instead of an array.

    If you are intent on using three arrays, I would still make the cards a class, then just move them from one "array" to another using copy and delete it from the first list.

    Depending on what operations you will be performing, the first option requires no copying, allocating, deallocating, etc, and would be less likely to loose cards.
    your humble savant

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Beginner's question regarding arrays

    Yes, there are so many ways to do this it's not even funny (actually, it is).

    Anyways, to give you the most concise yet helpful answer, I will guide you to random_suffle. This algorithm can take any range (in this case, your array), and shuffle the contents randomly.

    Regardless of your solution, random_shuffle will probably end up as the core of your algorithm.

    My recommendation: Shuffle your array1. Have player 1 draw the cards [0;5[, and player 2 draw the cards [5;10[. There, easy-peasy (is that the spelling?).

    Of course, since it not clear if the players are "drawing by value" or "drawing by reference", or how they later use these cards in the future, it will be up to you to be the judge of the best solution.

    Alternative: If you do not want to shuffle your first array of cards, you can create an intermediary array of indexes ({0,1,...,9}), and shuffle that. Then, player 1 can draw: array1[intermediarry[0]], array1[intermediarry[1]] etc.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Beginner's question regarding arrays

    Quote Originally Posted by TheRogue View Post
    I would suggest you change your cards from an int to a class that has a member variable indicating which player owns it.
    While I agree that making a Card class makes sense, I don't think the owner should be an attribute of the card. I think that should be determined by which container is currently storing the card.

  5. #5
    Join Date
    May 2006
    Posts
    102

    Re: Beginner's question regarding arrays

    Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.

  6. #6
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Beginner's question regarding arrays

    Quote Originally Posted by Ulnarian View Post
    Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.
    std::vector is so easy to learn that that's no excuse.

    Have a look at one of these:
    http://www.codeguru.com/cpp/cpp/cpp_...icle.php/c4071
    http://www.codeguru.com/cpp/cpp/cpp_...icle.php/c4027
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  7. #7
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: Beginner's question regarding arrays

    Quote Originally Posted by Ulnarian View Post
    Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.

    vector is easier than C arrays:

    Code:
    class Deck
    {
         std::vector<int> deck;
    public:
         Deck() 
         {
             // add cards 1 to 10 to deck 
             for (int i = 0; i < 10; ++i) 
                  deck.push_back(i+1); 
         }    
         void deal(Hand & hand1, Hand & hand2)
         {
               // seed rand function with current time in seconds
               srand(time(NULL));
               for (i = 0; i < 10; ++i)
               {    // get random index from deck
                     int n = rand()%deck.size();
                     int c  = deck[n];
                     if ((i%2) == 0)
                          hand1.add(c);
                     else
                          hand2.add(c);
                     deck.erase(deck.begin()+n);
               }
         }
         // more functions
    };
    You would need class Hand which also has an internal vector and a function 'add'. Also a class Game with one Deck and two Hand objects.

  8. #8
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,767

    Re: Beginner's question regarding arrays

    With only 10 cards in the deck, itsmeandnobodyelse's example is fine, but in general you would take monarch_dodra's suggestion of a random shuffle instead. Because the erase function runs in linear time, itsmeandnobodyelse's implementation of the deal function has quadratic time complexity. Compare this to the linear time complexity that you can get with random shuffle.

    Also, it is not necessarily a good idea to seed the PRNG when deal is called. It would be better to allow the caller the option of seeding the PRNG, since this might be done just once in a run of the program (whereas the deal function might be called more than once), and the caller may want to seed with a known seed in order to redo a simulation.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  9. #9
    Join Date
    May 2007
    Location
    Scotland
    Posts
    1,164

    Re: Beginner's question regarding arrays

    Quote Originally Posted by itsmeandnobodyelse View Post
    vector is easier than C arrays:

    Code:
    class Deck
    {
         std::vector<int> deck;
    public:
         Deck() 
         {
             // add cards 1 to 10 to deck 
             for (int i = 0; i < 10; ++i) 
                  deck.push_back(i+1); 
         }    
         void deal(Hand & hand1, Hand & hand2)
         {
               // seed rand function with current time in seconds
               srand(time(NULL));
               for (i = 0; i < 10; ++i)
               {    // get random index from deck
                     int n = rand()&#37;deck.size();
                     int c  = deck[n];
                     if ((i%2) == 0)
                          hand1.add(c);
                     else
                          hand2.add(c);
                     deck.erase(deck.begin()+n);
               }
         }
         // more functions
    };
    You would need class Hand which also has an internal vector and a function 'add'. Also a class Game with one Deck and two Hand objects.
    Just for feedback, which you will hopefully find useful. I thought I'd point out that you have a few bugs.

    1) You should move
    Code:
     srand(time(NULL));
    into the constructor of Deck, otherwise you will re-seed rand everytime deal is called (and thus will not necessarily provide very random consecutive deals).

    2) Consecutive calls to deal will yeild undefined behaviour, because you are calling deck.erase(iter) in your deal function, but have no means of reconstituting the deck of 10 cards before the deal function is called again. Therefore further calls to deal will attempt to access elements in the vector that are now invalid.

    That aside, I agree with the others, monarch_dodra has suggested a better solution. However, I understand that you were probably more trying to point out the use of vector rather than provide a correct and efficient solution.

  10. #10
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Beginner's question regarding arrays

    vector does seem like a good choice here since you will typically take cards only from one end of the deck which would be the back of the vector container. I recommend using the reserve member function to set the capacity to the max number of cards. If you use push_back without reserve you'll probably end up allocating more memory than you need.

    Also I agree with the suggestions to move the cards from one container to another. This is actually really simple. vector has a pop_back member function that is easy to use. If you random_shuffle the deck then you deal by copying the last element from the deck using vector::back into the new container and then pop_back from the vector. That's another alternative to consider and it would probably be easier to write the code for that. You an also start at the end with an iterator and move it backwards and copy until you are finished dealing. At that point you would erase everything after the final position of the iterator. Since the OP is a beginner I recommend keeping it simple at first. This shouldn't be a difficult program to write if you learn to use the sequence containers.

  11. #11
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: Beginner's question regarding arrays

    Quote Originally Posted by PredicateNormative View Post
    Just for feedback, which you will hopefully find useful. I thought I'd point out that you have a few bugs.

    1) You should move
    Code:
     srand(time(NULL));
    into the constructor of Deck, otherwise you will re-seed rand everytime deal is called (and thus will not necessarily provide very random consecutive deals).

    2) Consecutive calls to deal will yeild undefined behaviour, because you are calling deck.erase(iter) in your deal function, but have no means of reconstituting the deck of 10 cards before the deal function is called again. Therefore further calls to deal will attempt to access elements in the vector that are now invalid.

    That aside, I agree with the others, monarch_dodra has suggested a better solution. However, I understand that you were probably more trying to point out the use of vector rather than provide a correct and efficient solution.
    Guys, it was only quick and dirty sample code to show advantage of std::vector. I didn't want to show the most efficient and fully way shuffling and dealing needs to be done.

    The seed of the srand could be done once but in a game program which asks for user input (probably) it makes not so much a difference. I added it in Deck:eal just to keep the sample code simple. I didn't assume consecutive calls to deal either (what makes little sense logically) and had no error handling but of course both should be considered for serious code.

    You easily could make the deal safer by

    Code:
         for (int i = 0; i < (int)deck.size(); ++i)
            ...
    but of course the deal should be called only once for a new deck.

    Shuffling before dealing of course is a valid alternative and has the advantage that it maps to a real life game better than the random dealing.

    Here is a simple way of randomly adding cards into the deck in the constructor. After that the deal would put all even indices to hand1 and all odd indices to hand2.

    Code:
    class Deck
    {
          ...
          Deck::Deck()
          {
               srand(time(NULL));
               shuffle();
           }
    
           void shuffle()
           {
               // fill a vector with 10 integers of value 1
               std::vector<int> deckinit(10, 1);
               // make deck empty
               deck.clear();
               // calculate randomly a position in deckinit,
               // assign next non-zero entry to deck and 
               // mark the moved entry position by a zero entry
               for (i = 0; i < 10; ++i)
               {    // get random index from deck
                     int n = rand()%10;
                     int c;
                     // if we find a zero in the deckinit, the card is already moved
                     while (deckinit[n]) == 0)
                           // step to next n in cycle
                           n = (++n)%10;  
                     deck.push_back(n+1);
                     deckinit[n] = 0;
               }
          }
          ....
    Again, the code is more to show up the advantages of std::vector over C arrays than to give an efficient shuffle algorithm.

  12. #12
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Beginner's question regarding arrays

    Quote Originally Posted by itsmeandnobodyelse View Post
    Guys, it was only quick and dirty sample code to show advantage of std::vector.
    Don't take comments on your code personally. A quote is a citation, not a direct reply to the original author.

    Even if PredicateNormative's words look like they are directed at you (which they were), they are especially meant to be seen by the OP, who, while learning about vector, is also learning about (s)rand. Most of us here, you included, know all this, but our posts are seen by hundreds of people of copy it by the letter, and it is important for us to cover each other's backs.

    Take it as a "further more about itsmeandnobodyelse's code, you can..." rather than a direct attack/correction at you.

    PS: Could you turn on private messaging to your account? I wanted to give you a personal welcome message to these boards.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)