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;
}