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.
