CODEWITHSUNDEEP
ccs50
Bayeroabdul
Bayeroabdul

Reputation: 37

CS50 TIDEMAN; lock_pairs skips final pair if it creates cycle

I'm working on tideman problem for the CS50x (https://cs50.harvard.edu/x/2020/psets/3/tideman/). When I run check50 all the tests is passed except one:

:( lock_pairs skips final pair if it creates cycle lock_pairs did not correctly lock all non-cyclical pairs

I have been looking for the bug but can't figure out what the issue is. i need help.

heres the code below:

// checking if a pair creates a circle
bool iscycle(int winner, int loser)
{
    if (winner == loser)
    {
        return true;
    }

    int k = 0;
    while (k < 3)
    {
        //checking if the current loser is a winner in any locked pair
        if (pairs[k].winner == loser && locked[pairs[k].winner][pairs[k].loser] == true)
        {
            //if the loser of the current pair is thesame as the winner return true
            if (pairs[k].loser == winner)
            {
                return true;
            }
            else
            {
                return iscycle(winner, pairs[k].loser);
            }
         }
         k++;
    }
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // locking the pairs that do not cause a cycle
    for (int i = 0; i < pair_count; i++)
    {
        // if "iscyle" returns false: if does'nt create a cycle else it does
        if (iscycle(pairs[i].winner, pairs[i].loser) == false)
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
        else
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }
}

Upvotes: 1

Views: 1253

Answers (1)

Armali
Armali

Reputation: 19395

There are two bugs.

  1. You forgot to generalize for any number of pairs other than the Alice Bob Charlie case:

        while (k < 3)

    has to be

        while (k < pair_count)

  2. If the recursive call of iscycle returns false, the function may not return immediately, but has to check possible other pair edges from the local loser:

                    return iscycle(winner, pairs[k].loser);

    has to be

                    if (iscycle(winner, pairs[k].loser)) return true;

Upvotes: 2

Related Questions