0

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

You must log in to answer this question.

Browse other questions tagged .