Created
October 24, 2020 16:46
-
-
Save OvanRheenen/cd0b16d8517c58def26af2d3fafcc2cb to your computer and use it in GitHub Desktop.
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
#include <cs50.h> | |
#include <stdio.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]; | |
// 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); | |
void lock_pairs(void); | |
bool check_cycle(int l, int w); | |
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 | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
for (int j = 0; j < candidate_count; j++) | |
{ | |
locked[i][j] = false; | |
} | |
} | |
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); | |
// for (int k = 0; k < candidate_count; k++) | |
// { | |
// for (int j = 0; j < candidate_count; j++) | |
// { | |
// if (preferences[k][j] > 0) | |
// { | |
// printf("%s is preffered over %s by %i voters\n", candidates[k], candidates[j], preferences[k][j]); | |
// } | |
// } | |
// } | |
printf("\n"); | |
} | |
add_pairs(); | |
for (int i = 0; i < pair_count; i++) | |
{ | |
printf("%s was preferred over %s by %i voters\n", candidates[pairs[i].winner], candidates[pairs[i].loser], preferences[pairs[i].winner][pairs[i].loser]); | |
} | |
sort_pairs(); | |
for (int i = 0; i < pair_count; i++) | |
{ | |
printf("%s was preferred over %s by %i voters\n", candidates[pairs[i].winner], candidates[pairs[i].loser], preferences[pairs[i].winner][pairs[i].loser]); | |
} | |
lock_pairs(); | |
print_winner(); | |
return 0; | |
} | |
// Update ranks given a new vote | |
bool vote(int rank, string name, int ranks[]) | |
{ | |
// TODO | |
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[]) | |
{ | |
// TODO | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
for (int j = 0; j < candidate_count; j++) | |
{ | |
if (i != j && i < j) | |
{ | |
preferences[ranks[i]][ranks[j]] += 1; | |
} | |
} | |
} | |
return; | |
} | |
// Record pairs of candidates where one is preferred over the other | |
void add_pairs(void) | |
{ | |
// TODO | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
for (int j = 0; j < candidate_count; j++) | |
{ | |
if (i != j && preferences[i][j] > preferences[j][i]) | |
{ | |
pairs[pair_count].winner = i; | |
pairs[pair_count].loser = j; | |
pair_count++; | |
} | |
} | |
} | |
return; | |
} | |
// Sort pairs in decreasing order by strength of victory | |
void sort_pairs(void) | |
{ | |
pair temp; | |
for (int i = 1, j; i < pair_count; i++) | |
{ | |
temp = pairs[i]; | |
j = i - 1; | |
for (; j >= 0 && preferences[pairs[j].winner][pairs[j].loser] < preferences[temp.winner][temp.loser]; j--) | |
{ | |
pairs[j + 1] = pairs[j]; | |
} | |
pairs[j + 1] = temp; | |
} | |
} | |
// 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 (check_cycle(pairs[i].loser, pairs[i].winner)) | |
{ | |
break; | |
} | |
else // it doesnt make a cycle | |
locked[pairs[i].winner][pairs[i].loser] = true; | |
printf("edge from %i to %i is true\n", pairs[i].winner, pairs[i].loser); | |
} | |
return; | |
} | |
// Check wether edge from i to j creates a cycle | |
bool check_cycle(int l, int w) | |
{ | |
// base case 1: cycle created | |
if (l == w) | |
{ | |
return true; | |
} | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
// recursive case | |
if (locked[l][i] == true) | |
{ | |
check_cycle(i, w); | |
} | |
} | |
// base case 2: no cycle | |
return false; | |
} | |
// Print the winner of the election | |
void print_winner(void) | |
{ | |
// TODO | |
return; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment