Created
March 26, 2020 04:11
-
-
Save TomDeBeauchamp/a62c3939a6b2561f8bc708a644001d45 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 voters and candidates | |
#define MAX_VOTERS 100 | |
#define MAX_CANDIDATES 9 | |
// preferences[i][j] is jth preference for voter i | |
int preferences[MAX_VOTERS][MAX_CANDIDATES]; | |
// Candidates have name, vote count, eliminated status | |
typedef struct | |
{ | |
string name; | |
int votes; | |
bool eliminated; | |
} | |
candidate; | |
// Array of candidates | |
candidate candidates[MAX_CANDIDATES]; | |
// Numbers of voters and candidates | |
int voter_count; | |
int candidate_count; | |
// Function prototypes | |
bool vote(int voter, int rank, string name); | |
void tabulate(void); | |
bool print_winner(void); | |
int find_min(void); | |
bool is_tie(int min); | |
void eliminate(int min); | |
int main(int argc, string argv[]) | |
{ | |
// Check for invalid usage | |
if (argc < 2) | |
{ | |
printf("Usage: runoff [candidate ...]\n"); | |
return 1; | |
} | |
// Populate array of candidates | |
candidate_count = argc - 1; | |
if (candidate_count > MAX_CANDIDATES) | |
{ | |
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES); | |
return 2; | |
} | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
candidates[i].name = argv[i + 1]; | |
candidates[i].votes = 0; | |
candidates[i].eliminated = false; | |
} | |
voter_count = get_int("Number of voters: "); | |
if (voter_count > MAX_VOTERS) | |
{ | |
printf("Maximum number of voters is %i\n", MAX_VOTERS); | |
return 3; | |
} | |
// Keep querying for votes | |
for (int i = 0; i < voter_count; i++) | |
{ | |
// Query for each rank | |
for (int j = 0; j < candidate_count; j++) | |
{ | |
string name = get_string("Rank %i: ", j + 1); | |
// Record vote, unless it's invalid | |
if (!vote(i, j, name)) | |
{ | |
printf("Invalid vote.\n"); | |
return 4; | |
} | |
} | |
printf("\n"); | |
} | |
// Keep holding runoffs until winner exists | |
while (true) | |
{ | |
// Calculate votes given remaining candidates | |
printf("here"); | |
tabulate(); | |
// Check if election has been won | |
bool won = print_winner(); | |
if (won) | |
{ | |
break; | |
} | |
// Eliminate last-place candidates | |
int min = find_min(); | |
bool tie = is_tie(min); | |
// If tie, everyone wins | |
if (tie) | |
{ | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
if (!candidates[i].eliminated) | |
{ | |
printf("%s\n", candidates[i].name); | |
} | |
} | |
break; | |
} | |
// Eliminate anyone with minimum number of votes | |
eliminate(min); | |
// Reset vote counts back to zero | |
for (int i = 0; i < candidate_count; i++) | |
{ | |
candidates[i].votes = 0; | |
} | |
} | |
return 0; | |
} | |
// Record preference if vote is valid | |
bool vote(int voter, int rank, string name) | |
{ | |
for (int i = 0, n = candidate_count; i < n; i++) | |
{ | |
if (strcmp(candidates[i].name, name) == 0) // compare the vote to the name in the array | |
{ | |
preferences[voter][rank] = i; // update the jth value with the candidate's name, if a real candidate | |
return true; | |
} | |
} | |
return false; | |
} | |
// Tabulate votes for non-eliminated candidates | |
void tabulate(void) | |
{ | |
for (int i = 0; i < voter_count; i++) //outer loop moves through voters. | |
{ | |
for (int j = 0, n = candidate_count; j < n; j++) //inner loop moves through preferences | |
{ | |
if (candidates[(preferences[i][j])].eliminated == false) //if voter i's jth choice is not eliminated... [i][j] = candidate index | |
{ | |
candidates[(preferences[i][j])].votes++; //increment votes | |
j = n; //break the loop. j loop only records one vote per voter. | |
} | |
} | |
} | |
return; | |
} | |
// Print the winner of the election, if there is one | |
bool print_winner(void) | |
{ | |
for (int i = 0, n = candidate_count; i < n; i++) | |
{ | |
if (candidates[i].votes > (voter_count / 2)) //if there's a candidate with a majority vote share. | |
{ | |
printf("%s", candidates[i].name); //is this standard out? | |
return true; | |
} | |
} | |
return false; | |
} | |
// Return the minimum number of votes any remaining candidate has | |
int find_min(void) | |
{ | |
// TODO | |
//loop through candidates. if not eliminated, record votes and candidate index in array | |
//for each iteration in the loop check if the current vote is less than the current. Overwrite the values if it is. | |
int low = 0; | |
for (int i = 0, n = candidate_count; i < n; i++) | |
{ | |
if (candidates[i].eliminated == false) | |
{ | |
if (candidates[i].votes < low) | |
{ | |
low = candidates[i].votes; | |
} | |
} | |
} | |
return low; | |
} | |
// Return true if the election is tied between all candidates, false otherwise | |
bool is_tie(int min) | |
{ | |
int tie = 0; | |
for (int i = 0, n = candidate_count; i < n; i++) | |
{ | |
if (candidates[i].eliminated == false) | |
{ | |
if (candidates[i].votes == min) | |
{ | |
tie = 1; | |
} | |
else | |
{ | |
tie = 0; //if any of the candidates checked does not have the min count, no tie | |
} | |
} | |
} | |
if (tie == 1) | |
{ | |
return true; | |
} | |
return false; | |
} | |
// Eliminate the candidate (or candidiates) in last place | |
void eliminate(int min) | |
{ | |
// TODO | |
for (int i = 0, n = candidate_count; i < n; i++) | |
{ | |
if (candidates[i].votes == min) | |
{ | |
candidates[i].eliminated = true; | |
} | |
} | |
return; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment