This is my solution to cs50 psets 3 runoff problem. In this problem set, we have to create a program that runs a program of the runoff election.
In the previous post, I brought you my solution to the CS50 psets 3 plurality problem. But that program follows a very simple algorithm to determine the winner of an election. It is simply every voter gets one vote and the candidate with the most votes wins.
But what if two candidates get the same amount of votes? the above program does not have a solution for that. In this runoff, the method gives a solution to that problem. So in this method, each voter gets 3 chances to vote and rank their favorite candidate.
When you read the full description of psets 3 you’ll understand what is runoff method and how it solve the voting problem. I’m not going to explain it here again.
Let’s see what is my solution to the cs50 psets 3 runoff problem. Here is my code,
#include <cs50.h> #include <stdio.h> #include <string.h> #include <math.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 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) { // TODO for (int i = 0; i < candidate_count; i++) { if (strcmp(name, candidates[i].name) == 0) { preferences[voter][rank] = i; return true; } } return false; } // Tabulate votes for non-eliminated candidates void tabulate(void) { // TODO for (int i = 0; i < voter_count; i++) { for (int j = 0; j < candidate_count; j++) { if (candidates[preferences[i][j]].eliminated == false) { candidates[preferences[i][j]].votes += 1; break; } } } return; } // Print the winner of the election, if there is one bool print_winner(void) { // TODO for (int i = 0; i < candidate_count; i++) { string most_votes = candidates[i].name; if (candidates[i].votes > voter_count / 2) { printf("%s\n", most_votes); return true; } } return false; } // Return the minimum number of votes any remaining candidate has int find_min(void) { // TODO int min_votes = voter_count; for (int i = 0; i < candidate_count; i++) { if (candidates[i].eliminated == false && candidates[i].votes < min_votes) { min_votes = candidates[i].votes; } } return min_votes; } // Return true if the election is tied between all candidates, false otherwise bool is_tie(int min) { // TODO for (int i = 0; i < candidate_count; i++) { if (candidates[i].eliminated == false && candidates[i].votes != min) { return false; } } return true; } // Eliminate the candidate (or candidates) in last place void eliminate(int min) { // TODO for (int i = 0; i < candidate_count; i++) { if (candidates[i].votes == min) { candidates[i].eliminated = true; } } return; }
Hope this helps you!
Leave a Reply