CS50 tideman - :( lock_pairs skips final pair if it creates cycle

Question

I'm new to stackoverflow and pretty new to programming. I'm working on the tideman problem for the CS50 course. https://cs50.harvard.edu/x/2020/psets/3/tideman/ When I run check50 everything checks out except for one:

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

These two do pass the test: :) lock_pairs locks all pairs when no cycles :) lock_pairs skips middle pair if it creates a cycle

I can't find the problem. What am I missing here?

This is my code:

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

    // Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // for every pair we need to check for a circle
    for (int i = 0; i < pair_count; i++)
    {
        if (!circle_check(pairs[i].winner, pairs[i].loser))
        {
            //there's no circle: lock in pair
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}


// check pair for circles between winner and loser. Loser is first link
bool circle_check(int winner, int link)
{
    // check if the loser already has connections
    for (int n = 0; n < candidate_count; n++)
    {
        if (locked[link][n] == true)
        {
            // there's a link. if this ends in the winner, there's a circle
            if (n == winner)
            {
                return true;
            }
            else
            {
                // there may still be a circle, check next connection
                link = n;
                circle_check(winner, link);
            }
        }
    }
    return false;
}

Toogood

Answer 1

A few observations about your code/logic:

1. You are altering the value of your function argument in circle_check when you do link = n. It's good practice to not alter what's passed in as an argument in a function. Plus, on this specific case, you could do circle_check(winner, n) directly.

2. Your circle_check function, as it is presented, always returns false. That happens because when you call it from itself, you're not actually using it's return for anything. Let's say that recursive call returns true: On the 'first' function call, the line could be replaced by:

else
{
  link = n;
  true;
}

And, as you can imagine, that does nothing and the function continues it's execution normally, returning false.

If you, instead, add a return in front of the function call, you solve this problem.

But then there's also a 3rd point, that you need to consider:

3. Your function does not account for multiple checks for links on the same line of the locked[i][j] matrix. Allow me to demonstrate:

Imagine you have a 5x5 locked matrix, and on line 4 you currently have this disposition of true (T) and false (F):

[ F T T X F ]

When your function linear searches through the line, it's going to stop on locked[4][1], the first true, and do the recursive call to find a link. If it does find, it's going to return true and your lock_pairs is not going to add true to the locked matrix. But, what if it doesn't find? Then, instead of going to locked[4][2] to check for links there, it's just going to return false and the pair is going to be locked on lock_pairs.

You could solve this, for example, by adding a check after the recursive call, to see if it was returned true or false there. If true is returned, it means there's a link and you should NOT add the pair to locked. On the other hand, if you get false, it means there's no link and you can continue the linear search on the line.

The else statement could look something like:

else
{
  if (circle_check(winner,n)) // this way it only stops the search if a link was found
  {
    return true;
  }
}

Parr

The first two point I got straight away. The third was a bit more difficult to grasp, but I get is now. And it works. I spend many hours on this, so thank you for taking the time to help me out, and for explaining it so well. – Toogood

Glad it helped you :) – Honeyed