Instantly share code, notes, and snippets.

# simurq/locked_pairs.c

Last active February 10, 2021 19:56
Show Gist options
• Save simurq/9734710bb757b9b67ef5101d15a11ccb to your computer and use it in GitHub Desktop.
Function locked_pairs() for CS50
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 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 commented Feb 10, 2021 • edited Loading

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.

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