CODEWITHSUNDEEP
c++
Sandra
Sandra

Reputation: 11

My code won't print when submitted for codecheck even though it compiles without error

I've been assigned this question for my lab (and yes I understand there will be backlash because it's homework). I've been working on this question for a couple of days to no avail and I feel like I'm missing something glaringly obvious.

My code:

int processSuitors(vector<int>& currentSuitors, list<int>& rekt)
{
   int sizeSuitors = currentSuitors.size();
   int eliminated = 2;
   
   while(sizeSuitors != 1)
   {
      rekt.push_back(currentSuitors[eliminated]);
      currentSuitors.erase(currentSuitors.begin() + eliminated);
      sizeSuitors--;
      
      if(eliminated > sizeSuitors)
      {
         eliminated -= sizeSuitors;
      }
   }
   return currentSuitors[0];
}

Prompt: In an ancient land, the beautiful princess Eve had many suitors. She decided on the following procedure to determine which suitor she would marry. First, all of the suitors would be lined up one after the other and be assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at the first suitor she would then count three suitors down the line (because of the three letters in her name) and the third suitor would be eliminated from winning her hand and he would be removed from the line. Eve would then continue, counting three more suitors and eliminating every third suitor. When she reached the end of the line she would continue counting from the beginning.

Write a function named processSuitors that takes as arguments an STL vector of type int containing the suitors, and an STL list of type int that will collect all the suitors that are eliminated. The function returns an int storing the position a suitor should stand in to marry the princess if there are n suitors. The function that calls processSuitors will send the vector already filled with n suitors (1, 2, 3... n), and an empty list that needs to be filled with the position number of the suitors that were eliminated, in the order they were eliminated.

Restrictions: You may not create any containers (no arrays, no vectors, etc.); you need to use the vector and the list that are passed as parameters. Use ONLY the following STL functions:

vector::size
vector::erase
vector::begin
ist::push_back
vector::operator[ ]

The adjacent files are hidden since we are to rely on what is given. Any clean-up of my code would be extremely appreciated as well.

Upvotes: 0

Views: 97

Answers (1)

selbie
selbie

Reputation: 104569

What do you think of this solution.

Keep another vector that marks whether an index in your currentSuitors vector has been removed. Then have a helper function that will always find the next free index.

Instead of trying to reduce currentSuitors, you just keep marking elements in the taken list.

size_t findNextFreeSlot(const vector<bool>& taken, size_t pos)
{
    // increment to the next candidate position
    pos = (pos + 1) % taken.size();

    // search for the first free slot
    for (size_t i = 0; i < taken.size(); i++)
    {
        if (taken[pos] == false)
        {
            return next;
        }
        pos = (pos + 1) % taken.size();
    }

    // assert(false); // we should never get here as long as there's one free slot index in taken
    return -1;
}

int processSuitors(vector<int>& currentSuitors, list<int>& rekt)
{
    size_t len = currentSuitors.size();
    vector<bool> taken(len);   // keep a vector of eliminated indices from current
    size_t index = len;        // initialize one past the last valid element
    size_t eliminated = 0;

    if (len == 0)
    {
        return -1;
    }

    while (eliminated < (len-1))
    {
        // advance the index three times to the next "untaken" index
        index = findNextFreeSlot(taken, index); 
        index = findNextFreeSlot(taken, index); 
        index = findNextFreeSlot(taken, index); 
        
        taken[index] = true;  // claim this index as taken
        rekt.push_back(currentSuitors[index]);  // add the value at this index to the eliminated list
        eliminated++;
    }

    index = findNextFreeSlot(taken, index); // find the last free index

    return currentSuitors[index];
}

Upvotes: 1

Related Questions