TIDEMAN CS50-how can i check if the pair.winner is a winner elsewhere, i.e we have more than 1 edge going from some candidate

36 views Asked by At

this is my third day solving the imfamous Tideman pset3 from cs50, day 2 had me stuck on the logic (which i feel the descripition of the problems misguided me from), this git post helped my headbulb glow

i have implemented the logic explained in the link given above, how it works is as follows


Function lock_pair

The first pairs from the sorted pairs is locked into the locked[][] using a loop going througt pair index then it calls the iscycle function (defined by me) , and passes the index number (aka i) and winner of current pair (aka original_winner). It as also sets all values of visitedbycycle bool array as false before each call to iscycle

Function * iscycle*

The iscycle starts with a loop , in the loop it first checks for the base case where it compares the loser current pair( pair updates with recursion) we have with the orginal_winner. After the base case it checks if the current pair loser is marked winner somewhere in the locked[][] 2d array ,also also checks if the current pair loser is visited by set to false . Inside the second conditional statement there is a loop going till pair count, inside this loop it checks if the the second loser over whom the original loser won when checked in locked array is same as the original_winner, if yes then its updates the visitedbycycle to true and calls the function iscycle (recursion).

Global Declarations by me

bool visitedbycycle[MAX];
bool iscycle(int pair_index, int original_winner);

CODE

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    for (int i = 0; i < pair_count ; i++)
    {
        locked[pairs[i].winner][pairs[i].loser] = true;
        for(int j = 0; j < candidate_count; j++)
        {
            visitedbycycle[j] = false;
        }
        if (iscycle(i, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }
    return;
 }

bool iscycle(int pair_index, int original_winner)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (pairs[pair_index].loser == original_winner)
        {
            return true;
        }
        if(locked[pairs[pair_index].loser][i] == true && visitedbycycle[i] != true)
        {
             for (int j = 0; j < pair_count ; j++)
            {
                if (pairs[j].winner == i )
                {
                    visitedbycycle[i] = true;
                    return iscycle(j, original_winner);
                }
            }
        }
    }
    return false;
}

i have tried having another function which will handle the for loop inside this conditional stament in iscycle

        if(locked[pairs[pair_index].loser][i] == true && visitedbycycle[i] != true)
        {
             for (int j = 0; j < pair_count ; j++)
            {
                if (pairs[j].winner == i )
                {
                    visitedbycycle[i] = true;
                    return iscycle(j, original_winner);
                }
            }
        }

the for loop currently only checks for the a sigle win/edge of one candidate over other and doesnt consider the case where we will have more than 1 win over other eg A --> B , A --> C,in this case it would only check for A-->B , and this is where im getting the check50 error

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

the other two conditions are coming out correct

:) lock_pairs locks all pairs when no cycles
:) lock_pairs skips middle pair if it creates a cycle

my approach to solve this issue is to have another function called more_cycles which checks for more cycles and returns true or false , the for logic is added to it and and if statement now calls the more_cycles fucntion

CODE

bool iscycle(int pair_index, int original_winner)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (pairs[pair_index].loser == original_winner)
        {
            return true;
        }
        if(locked[pairs[pair_index].loser][i] == true && visitedbycycle[i] != true)
        {
            int temp = more_cycles(i, original_winner);

            if ( temp == -1)
            {
                return false;
            }
            else
            {
                return iscycle(temp, original_winner);
            }

        }
    }
    return false;
}

int more_cycles(int index, int original_winner)
{
    visitedbycycle[index] = true;
    for (int j = 0; j < pair_count ; j++)
            {
                if (pairs[j].winner == index )
                {
                    return j;
                }
            }
            return -1;
}

0

There are 0 answers