0

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. graph of the pairs from Case D 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.

2
  • 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
0

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!

-2

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.
Input: 6 candidates, 5 votes.
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
your output:
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!

1
  • 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .