-
-
Save Saarth-Jain/a8b16b0ea04d7c6b1dbb37cd7bb3b037 to your computer and use it in GitHub Desktop.
| #include <cs50.h> | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| // Max number of candidates | |
| #define MAX 9 | |
| // preferences[i][j] is number of voters who prefer i over j | |
| int preferences[MAX][MAX]; | |
| // locked[i][j] means i is locked in over j | |
| bool locked[MAX][MAX]; | |
| bool lock = true; | |
| // Each pair has a winner, loser | |
| typedef struct | |
| { | |
| int winner; | |
| int loser; | |
| } | |
| pair; | |
| // Array of candidates | |
| string candidates[MAX]; | |
| pair pairs[MAX * (MAX - 1) / 2]; | |
| int pair_count; | |
| int candidate_count; | |
| // Function prototypes | |
| bool vote(int rank, string name, int ranks[]); | |
| void record_preferences(int ranks[]); | |
| void add_pairs(void); | |
| void sort_pairs(void); | |
| int comparator(const void *a, const void *b); | |
| void lock_pairs(void); | |
| void print_winner(void); | |
| int main(int argc, string argv[]) | |
| { | |
| // Check for invalid usage | |
| if (argc < 2) | |
| { | |
| printf("Usage: tideman [candidate ...]\n"); | |
| return 1; | |
| } | |
| // Populate array of candidates | |
| candidate_count = argc - 1; | |
| if (candidate_count > MAX) | |
| { | |
| printf("Maximum number of candidates is %i\n", MAX); | |
| return 2; | |
| } | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| candidates[i] = argv[i + 1]; | |
| } | |
| // Clear graph of locked in pairs and the preferences array from garbage values | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| for (int j = 0; j < candidate_count; j++) | |
| { | |
| locked[i][j] = false; | |
| preferences[i][j] = 0; | |
| } | |
| } | |
| pair_count = 0; | |
| int voter_count = get_int("Number of voters: "); | |
| // Query for votes | |
| for (int i = 0; i < voter_count; i++) | |
| { | |
| // ranks[i] is voter's ith preference | |
| int ranks[candidate_count]; | |
| // Query for each rank | |
| for (int j = 0; j < candidate_count; j++) | |
| { | |
| string name = get_string("Rank %i: ", j + 1); | |
| if (!vote(j, name, ranks)) | |
| { | |
| printf("Invalid vote.\n"); | |
| return 3; | |
| } | |
| } | |
| record_preferences(ranks); | |
| printf("\n"); | |
| } | |
| add_pairs(); | |
| sort_pairs(); | |
| lock_pairs(); | |
| print_winner(); | |
| return 0; | |
| } | |
| // Update ranks given a new vote | |
| bool vote(int rank, string name, int ranks[]) | |
| { | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| if (strcmp(name, candidates[i]) == 0) | |
| { | |
| ranks[rank] = i; | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| // Update preferences given one voter's ranks | |
| void record_preferences(int ranks[]) | |
| { | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| for (int j = i + 1; j < candidate_count; j++) | |
| { | |
| preferences[ranks[i]][ranks[j]]++; | |
| } | |
| } | |
| } | |
| // Record pairs of candidates where one is preferred over the other | |
| void add_pairs(void) | |
| { | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| for (int j = i + 1; j < candidate_count; j++) | |
| { | |
| if (preferences[i][j] > preferences[j][i]) | |
| { | |
| pairs[pair_count].winner = i; | |
| pairs[pair_count].loser = j; | |
| pair_count++; | |
| } | |
| else if (preferences[i][j] < preferences[j][i]) | |
| { | |
| pairs[pair_count].winner = j; | |
| pairs[pair_count].loser = i; | |
| pair_count++; | |
| } | |
| } | |
| } | |
| } | |
| // function used for sort | |
| int comparator(const void *a, const void *b) | |
| { | |
| pair *ab = (pair *)a; | |
| pair *ba = (pair *)b; | |
| // uses pointers to access the preferences and check how much a candidate wins over another | |
| return (preferences[ba->winner][ba->loser] - preferences[ab->winner][ab->loser]); | |
| } | |
| // Sort pairs in decreasing order by strength of victory | |
| void sort_pairs(void) | |
| { | |
| qsort(pairs, pair_count, sizeof(pair), comparator); | |
| } | |
| bool has_cycle(int winner, int loser) | |
| { | |
| while (winner != -1 && winner != loser) | |
| { | |
| bool found = false; | |
| for (int i = 0; i < candidate_count; i++) | |
| { | |
| if (locked[i][winner]) | |
| { | |
| found = true; | |
| winner = i; | |
| } | |
| } | |
| if (!found) | |
| { | |
| winner = -1; | |
| } | |
| } | |
| if (winner == loser) | |
| { | |
| return true; | |
| } | |
| return false; | |
| } | |
| // Lock pairs into the candidate graph in order, without creating cycles | |
| void lock_pairs(void) | |
| { | |
| //TODO | |
| for (int i = 0; i < pair_count; i++) | |
| { | |
| if (!has_cycle(pairs[i].winner, pairs[i].loser)) | |
| { | |
| locked[pairs[i].winner][pairs[i].loser] = true; | |
| } | |
| } | |
| } | |
| // Print the winner of the election | |
| void print_winner(void) | |
| { | |
| //TODO | |
| for (int col = 0; col < MAX; col++) | |
| { | |
| bool found_source = true; | |
| for (int row = 0; row < MAX; row++) | |
| { | |
| if (locked[row][col] == true) | |
| { | |
| found_source = false; | |
| break; | |
| } | |
| } | |
| if (found_source) | |
| { | |
| printf("%s\n", candidates[col]); | |
| return; | |
| } | |
| } | |
| return; | |
| } |
Although this code passes all the checks made on CS50, it seems to me that the has_cycle function is incomplete. Meaning it misses some cases where there is a cycle. Let me show with an example:
Imagine there are 4 candidates: A, B, C and D (for simplicity). The ordered pairs are (represented as {winner, loser}):
- {A, D}
- {A, B}
- {C, B}
- {D, C}
- {B, D}
- {A, C}
If you draw this simple diagram, you'll see that the fifth pair, {B, D}, is a pair that cannot be drawn, because it would create the cycle B -> D -> C -> B.
Even though that is the case, the function has_cycle seems to miss this case, and incorrectly returns false (meaning there is no cycle formed by adding the pair {B, D}.
It seems to me that the proper way to write such a function would be by using recursion. Although I could not figure out how to write it yet.
Please let me know if I am missing something or if someone figured out how to write this function using recursion.
Could you send me your input, please? I mean, the ranks of each vote.
Could you explain this part:
bool has_cycle(int winner, int loser)
{
while (winner != -1 && winner != loser)
why is "winner != -1" part? i mean what role it plays?
Could you explain this part:
bool has_cycle(int winner, int loser) { while (winner != -1 && winner != loser)
why is "winner != -1" part? i mean what role it plays?
I am very sorry out there. I wrote these codes like 3 years ago and after that I didn't had practice and all. I was busy with stuff so now I don't recognise the code much. I am sure somebody will surely help you out.
Happy Learning!
@chu999 it just break the loop. Meaning that there is no cycle on locking that relation
Although this code passes all the checks made on CS50, it seems to me that the has_cycle function is incomplete. Meaning it misses some cases where there is a cycle. Let me show with an example:
Imagine there are 4 candidates: A, B, C and D (for simplicity). The ordered pairs are (represented as {winner, loser}):
- {A, D}
- {A, B}
- {C, B}
- {D, C}
- {B, D}
- {A, C}
If you draw this simple diagram, you'll see that the fifth pair, {B, D}, is a pair that cannot be drawn, because it would create the cycle B -> D -> C -> B.
Even though that is the case, the function has_cycle seems to miss this case, and incorrectly returns false (meaning there is no cycle formed by adding the pair {B, D}.
It seems to me that the proper way to write such a function would be by using recursion. Although I could not figure out how to write it yet.
Please let me know if I am missing something or if someone figured out how to write this function using recursion.
Hi,
I'm not sure about whether my answer would be suitable to solve your doubt regarding 6 votes for the 4 candidates thing, yet I have figured out the recursive version of has_cycle()...
bool has_cycle(int original_winner, int current_loser)
{
if (current_loser == original_winner)
return true;
for (int i = 0; i < pair_count; ++i)
{
if (pairs[i].winner == current_loser && locked[pairs[i].winner][pairs[i].loser])
{
if (has_cycle(original_winner, pairs[i].loser))
return true;
}
}
return false;
}We are given a winner and a loser, original_winner and current_loser respectively, I'd talk about the base case later.
We'll make a recursive call has_cycle(original_winner /* this doesn't change */, pair[i].loser) for each new pair in pairs, where the current_loser is the winner, if that pair already has a edge locked in.
Now in the recursive call to has_cycle, if the original_winner that we passed in while calling the function in lock_pairs() is the same as the current_loser in the recursive call, this means we have circled around, thus a cycle exists, and we return true.
If no cycle exists, it returns false.
Test for some randomized testcases at this website, where the graph has a red edge, and do a dry-run of the above recursive algorithm on that graph. That might help you understand it better.
Hope the answer helped :)
Thanks :)
Wow wow wow you actually made it XD
i see mass struggle in people including me