# Can't determine the problem with my tideman program - check50 fails at lock_pairs function, says I didn't correctly lock all non-cyclical pairs

My program for the tideman problem in pset3 passes all check50 checks except for

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

Here are some test cases I have run. My program prints out all the pairs in order (highest margin of victory to lowest), then prints any pairs that were skipped due to creating a cycle, followed by the winner of the election on the final line.

Case A: 3 pairs, final pair creates cycle

``````Pairs:
Pair 0 - winner: B, loser: C
Pair 1 - winner: A, loser: B
Pair 2 - winner: C, loser: A
pairs[2] (winner: C, loser:A) rejected
A
``````

Case B: 3 pairs, no pair creates a cycle

``````Pairs:
Pair 0 - winner: A, loser: B
Pair 1 - winner: C, loser: A
Pair 2 - winner: C, loser: B
C
``````

Case C: 5 pairs, third pair creates a cycle

``````Pairs:
Pair 0 - winner: B, loser: C
Pair 1 - winner: C, loser: D
Pair 2 - winner: D, loser: B
Pair 3 - winner: A, loser: D
Pair 4 - winner: A, loser: B
pairs[2] (winner: D, loser:B) rejected
A
``````

Case D: 10 pairs, last pair creates a cycle (test case from the answer to this cs50 stackexchange post)

``````Pairs:
Pair 0 - winner: A, loser: B
Pair 1 - winner: B, loser: C
Pair 2 - winner: C, loser: D
Pair 3 - winner: D, loser: E
Pair 4 - winner: A, loser: F
Pair 5 - winner: F, loser: G
Pair 6 - winner: G, loser: H
Pair 7 - winner: H, loser: I
Pair 8 - winner: I, loser: C
Pair 9 - winner: E, loser: F
pairs[9] (winner: E, loser:F) rejected
A
``````

I thought that Case D would be the one to fail, given the check50 error message, but it seems like my program properly skipped the last pair, which would have created a cycle (see picture below), and correctly prints the winner as A. Here is my lock_pairs function:

``````void lock_pairs(void)
{
//Print unsorted pairs
printf("Pairs:\n");
for (int i = 0; i < pair_count; i++)
{
printf("Pair %i - winner: %s, loser: %s\n", i, candidates[pairs[i].winner], candidates[pairs[i].loser]);
}

//Loop over all of the unlocked pairs
for (int i = 0; i < pair_count; i++)
{
//Run custom recursive function to check whether a cycle is created, with the winner and loser of the current pair as inputs
if (cycleCheck(pairs[i].winner, pairs[i].loser) == true)
{
//If a cycle is created, print this message
printf("pairs[%i] (winner: %s, loser:%s) rejected\n", i, candidates[pairs[i].winner], candidates[pairs[i].loser]);
}
else
{
//If a cycle is not created, add the pair to locked
locked[pairs[i].winner][pairs[i].loser] = true;
}

}

return;
}
``````

And here is the recursive function called by lock_pairs, called cycleCheck:

``````bool cycleCheck (int uberwinner, int loser)
{
//'uberwinner' (referring to the winner of the pair to be checked) does not change; 'loser' is updated each time 'cycleCheck' is recursively called
if (uberwinner == loser)
{
printf("Hit first if statement\n");
return true;
}
//For each of the candidates, if the current loser being checked is the winner of a pair in 'locked' with a value of true AND the current loser is the winner of the original pair being checked, return true (pair creates cycle)
for (int i = 0; i < candidate_count; i++)
{
if (locked[loser][i] == true)
{
if (i == uberwinner)
{
return true;
}
//If the current loser being checked is the winner of a pair in locked with a value of true, but the loser is not the winner of the original pair being checked, continue checking for a cycle
return cycleCheck(uberwinner, i);
}
}
return false;
}
``````

And here is the post I made on the cs50 subreddit, which provides a little more background but which I don't think is necessary here. Edit: In case it would be helpful to look at my entire tideman.c code, I uploaded it to github here.

• I see you got an answer in your reddit post. You can post that here as an answer to your own question, and then accept it, to close this down in this system. : ) – Robert S. Pratt Feb 18 at 18:14
• Just added, thanks for reminding! – jonahsaltzman845 Feb 19 at 16:57

Thanks to u/yeahIProgram on reddit for this answer:

If you look at the second if statement in my cycleCheck function, it first asks whether the current loser passed to the function is the winner of any true pair already locked in to locked. If it is, and if the loser of that pair is the overall winner (uberwinner) passed to the function (`if (i == uberwinner)`), then the function returns true. This part is correct.

However, immediately after that nested if statement, my function then had `return cycleCheck(uberwinner, i);` which would always return whatever the value of that call to cycleCheck was. This is the mistake: if this call to cycleCheck returned false, false would be returned to main (or the next call of cycleCheck), implying that no cycle existed. However, even if that particular `uberwinner, i` pair returned false, a subsequent pair (as `i` continues to be incremented) could be true. So it is a mistake to return that value of cycleCheck whether it is true or false. Instead, I needed another if statement to check if that call to cycleCheck returned true. If it did return true, meaning it's found a cycle, then I can return that value, otherwise, I need to keep iterating along the for loop that contains this call to cycleCheck, to make sure no other pairs along the same "row" of the locked graph are true, and not return the value of the call until its value is true, or until I reach the end of the loop. Then I can return false, once all the pairs have been checked.

So to fix the code, I replaced this line

``````return cycleCheck(uberwinner, i);
``````

with this code

``````if (cycleCheck(uberwinner, i) == true)
{
return true;
}
``````

With that small change, my program passed all the check50 checks!

I could be off-base here. My last submit failed the same check. But feeding my input set to your program, I have a thought.
candidates: a b c d e f
vote 1: a b c d e f
vote 2: a c d e f b
vote 3: a d e f b c
vote 4: a e f b c d
vote 5: a f b c d e
Pairs:
Pair 0 - winner: a, loser: b
Pair 1 - winner: a, loser: c
Pair 2 - winner: a, loser: d
Pair 3 - winner: a, loser: e
Pair 4 - winner: a, loser: f
Pair 5 - winner: b, loser: c
Pair 6 - winner: c, loser: d
Pair 7 - winner: d, loser: e
Pair 8 - winner: e, loser: f
Pair 9 - winner: f, loser: b
Pair 10 - winner: b, loser: d
Pair 11 - winner: c, loser: e
Pair 12 - winner: d, loser: f
Pair 13 - winner: e, loser: b
Pair 14 - winner: f, loser: c
pairs[9] (winner: f, loser:b) rejected
pairs[13] (winner: e, loser:b) rejected
pairs[14] (winner: f, loser:c) rejected

I thought that pair[13] was actually ok, but now realize that was a mistake. If you find an example which highlights the problem, please share!

• Unfortunately I never actually found a set of inputs that would highlight the problem, but if you look at my accepted answer, someone on Reddit found the solution. Given the answer, I bet you could reverse-engineer a set of votes to highlight the problem however. – jonahsaltzman845 Feb 19 at 16:59