Skip to content

Instantly share code, notes, and snippets.

@simurq
Last active February 10, 2021 19:56
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save simurq/9734710bb757b9b67ef5101d15a11ccb to your computer and use it in GitHub Desktop.
Function locked_pairs() for CS50
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
int i, j, row, win, los, cycle;
for (i = 0; i < pair_count; i++)
{
win = pairs[i].winner;
los = row = pairs[i].loser;
cycle = 0;
for (j = 0; j < candidate_count; j++)
{
if (cycle == 1) // exit the loop if the candidate creates a cycle
{
break;
}
if (locked[row][j] == true) // 'row' instead of 'los' because the latter's used further below
{
row = j; // check for new candidate each time until it matches (or doesn't match) the winner
j = -1; // to restart the loop each time row = j until cycle == 1
if (row == win)
{
cycle = 1;
}
}
}
if (cycle == 0)
{
locked[win][los] = true; // lock the pair
}
}
return;
}
@nicknapoli82
Copy link

nicknapoli82 commented Feb 10, 2021

I can see what your thought process is to an extent.
For simplicity I'm going to focus on your j and row variables.

When you find locked[row][j] to be true, you set row to j and that makes sense, but you set j to only be -1. So what happens if j is 5 in this case, and it becomes 4. You won't end up checking all the possible combinations for [row][j] to find the next link in the chain. So that is issue one that I see.

The second issue derives from the fact that your j loop is finite. So when you exhaust all the options for the current [row][j], you never go back one link in the chain and completing all of those possibilities.

As example consider having 4 candidates [a, b, c, d], and we will use a hypothetical scenario
Lets say a wins d, but the chain that would need to be built to find that cycle is a->c->d->a
You end up finding [c][d] and set row to d, but you end up setting j back only to c... [d][a] will never be found.

Second example using the exact same thing but I'm going to add come complexity

a->b->d // in this case d does not win against a
   |>c->d->a` // This is a fork, where b wins against both c, and d

In this example you find d loses and set row to that candidate, and check all those possibilities, but your code never checks all the possibilities for candidate b.

So using a non recursive solution. Your code needs some way of tracking where it is in every link of the chain, and needs to pick up where it left off checking all possible paths.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment