0

So as seems to be the case with many people, I'm struggling a bit with tideman.

My code scores full marks up until the point where the pairs become "locked."

The code for my lock_pairs function is below:

void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        if (is_cycle(pairs[i].loser, pairs[i].winner) == false)
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}

and the code for my is_cycle function referenced in the above is here:

bool is_cycle(int i, int me)
{
    if (i == me)
    {
        return true;
    }

    for(int j = 0; j < candidate_count; j++)
    {
        if(locked[i][j])
        {
            is_cycle(j, me);
        }
    }

    return false;
}

Here is my train of thought.

  1. We input the loser and winner of the pair as arguments to the is_cycle function
  2. The is_cycle function checks whether the two arguments are the same, and if not, continues (this might seem useless at the moment but just bear with me).
  3. The function then loops through all possible candidates and checks whether the loser of the original pair wins against anyone. If they don't, then a cycle will not be created and the function will return false.
  4. If they do win against someone (we'll just call this person "candidate j"), we call the function recursively while checking whether candidate j beat anyone. Again, if they didn't, then no cycle will be created. However, if they did beat someone who also happens to be the winner of the original pair, then this will be fed into the "i" argument for is_cycle when it is recursively called, thus making "i" equivalent to "me" (remember, "me" is the index of the winning candidate of the original pair) and will cause the function to return true because a cycle has now been identified.

My code successfully locks all pairs when there are no cycles but fails when there is a cycle at the end or middle of the pairs array. I'm guessing I've made some glaringly obvious stupid mistake... would someone be able to point me in the right direction?

EDIT:

Managed to figure it out. Now have full marks on tideman, woohoo! My is_cycle function was slightly incorrect. The correct code is below. I've added an extra if statement under the for loop.

bool is_cycle(int i, int me)
{
    
    if (i == me)
    {
        return true;
    }

    for (int j = 0; j < candidate_count; j++)
    {
        if(locked[i][j])
        {
            if (is_cycle(j, me))
            {
                return true;
            }
            else
            {
                is_cycle(j, me);
            }

        }
    }

    return false;
    
}

You must log in to answer this question.

Browse other questions tagged .