Locking pairs in the Tideman problem

I've been going through the CS50x course. It was doable so far but now I'm just stuck on the Tideman problem from p-set 3.

Tideman is a voting method that picks the Condorcet winner of an election, i.e. the candidate who wins head-to-head against the max number of candidates.

Here's a link to the problem description page.

I am working more precisely on this test case:

lock_pairs skips middle pair if it creates a cycle

lock_pairs did not correctly lock all non-cyclical pairs

Not a 100% on this one, but it appears that I'm locking extra pair(s). Yet, I am unable to understand what exactly 'middle pair' means here.

I've documented the code as best as I can. However, I'm a total beginner here. Feel free to correct me wherever required.

Meanwhile I'll just include my 'lock_pairs' function hoping someone would be able to point the flaw out to me.

``````// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
//Traversing through all pairs
for (int i = 0; i < pair_count; i++)
{
//Initially assuming the pair creates a cycle
bool creates_cycle = true;

//Traversing through each candidate that is not ith pair's loser
for (int j = 0; j < candidate_count; j++)
{
if (j == pairs[i].loser)
{
continue;
}

//Initially assuming atleast one locked pair exists if and where candidate j is ever a loser
bool candidate_loser_locked = true;

//Initially assuming the candidate is never a loser
bool never_loser = true;

//Checking whether all pairs with candidate j as loser are unlocked
for (int k = 0; k < pair_count; k++)
{
//Skips if candidate j is not loser in kth pair
if (j != pairs[k].loser)
{
continue;
}
else
{
//Candidate j is a loser in atleast one pair
never_loser = false;
if (locked[pairs[k].winner][pairs[k].loser] == true)
{
//End pair loop if candidate j is found to be loser in a locked pair
candidate_loser_locked = true;
break;
}
else
{
//If pair with j as loser is unlocked
candidate_loser_locked = false;
}
}
}

//In case candidate j is never found to be a loser
if (never_loser == true)
{
candidate_loser_locked = false;
}

//If candidate j is not a loser in any locked pair
if (candidate_loser_locked == false)
{
//Then winners and losers of ith pair do not create a cycle
creates_cycle = false;
break;
}
}

//If ith pair does not create a cycle
if (creates_cycle == false)
{
//Locks the winner of ith pair in over the loser of ith pair
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
return;
}
``````
• Hi, I am having the same issue as you did. Did you figure out in the end? I wrote test cases to see if my program skips 'middle pair', and the program does skip but it just keeps failing check50 – Brian Wang Mar 27 at 21:20
• Yeah. I used a recursive function in the end. – Advitiay Anand Mar 28 at 18:07
• Here's my 2 cents. Draw a complicated test case on a piece of paper, and use it as a reference to write a recursive function. Also, you could ask the experts at CS50's Discussion Forum (us.edstem.org/courses/176/discussion). – Advitiay Anand Mar 28 at 18:18
• Middle pairs can create cycles. Check50 is telling you, is that you have not removed a pair that is creating a cycle in the middle – Andrew Burke May 15 at 15:26
• Also, its really just a trio of for loops and a few if statements that you need. If Charlie beat Alice 6-3 and Alice beat Bob 7-2 then charlie beat both alice and Bob. With cycles, all that matters is that charlie beat alice, and alice beat bob, and charlie beat alice by a higher number than bob beat charlie. – Andrew Burke May 15 at 15:33