CS50x Runoff
From problem set 3
Runoff is a ranked choice voting system. It has the benefit to provide a winner that better reflect the voters’ preference. To make that work, each voter rank the candidates in a preference list. If any candidate has a majority of the first vote preference, that candidate is declared the winner. If no candidate has more than 50% of the votes, an instant runoff takes place. The candidate that received the least amount of votes is eliminated from the election, anyone that had previously selected that candidate as their first preference now has their second preference considered. The process repeats until one candidate has the majority or the election comes to a tie.
Talking about code, this is how the program should run given 3 candidates and 5 voters:
./runoff Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Bob
Rank 3: Charlie
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob
Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice
Rank 1: Bob
Rank 2: Alice
Rank 3: Charlie
Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob
AliceDistribution Code
Following the method of the last problem, here we receive a distribution code with the everything but the functions already working. I’ve cut it in some parts to take a closer look.
Here we have our global stuff: libraries (I think I did include string.h if not mistaken), two constants for max number of voter and candidates, an empty 2d array called preferences, a structure named candidate with name, votes and a bool value to flag if the candidate is eliminated, the candidates array, two variables for the actual number of voters and candidates and finally our function prototypes.
#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);
Jumping a few lines, inside the main function we have the loop that fills the candidates array with our candidate type data defined in the structure. For each name passed through the command line it initializes a candidate inside the array. Note that name changes with our index for each candidate, but votes and the bool should be the same for everyone at this moment.
./runoff Alice Bob Charlie
...
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
candidates[i].eliminated = false;
}Below that we have a loop that checks if the votes being cast are valid. Using nested loops, with the first representing each voter, and the second asking the voters for their ranks preference and checking the names against our candidates array — Using the vote function that we’re still to develop.
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");
}
Once all voters have their preferences registered, the program proceeds to the actual runoffs. A while loop takes care of keeping the runoff working until some candidate has won. Here’s where the majority of our functions are called. The code is well commented, and doing more than that here would spoil our functions explanation, take a look and see if you can understand it.
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;
}
To see the full distribution code look for the gist at the end of the page.
Functions
Approaching the functions at the order their appear, first we have vote. This function is responsible to record voters’ preferences. Main function is running the loops through each voter and preference, inside vote we need only to check the candidates array for a name match and then add that candidate index (inside the candidates array) to the preferences array, returning true if a match was found, or false when no match. Think that this check runs after each name prompted by the voter, and not after all the votes are done.
e.g. voter 0(1st voter) votes for Bob as his preferred candidate. Bob is at index 1(2nd place) in our candidates array. So vote will add to the array preferences[0][0] = 1; then return true, which makes the main function ask the voter for his second preference. Suppose now the voter enters Alice, she is at index 0 in our candidates array. Our vote function now will add preferences[0][1] = 0; and so on.
bool vote(int voter, int rank, string name)
{
for (int c = 0; c < candidate_count; c++)
{
if (strcmp(name, candidates[c].name) == 0)
{
preferences[voter][rank] = c;
return true;
}
}
return false;
}The next step is the tabulate functions, which counts the votes for the runoff taking place. This function loops through each voter in our preferences array, it also loops through each rank because as runoffs go a candidate may be eliminated. To make sure we’re taking the preferences correctly as candidates are eliminated a simple if checks for the bool value that candidate has (remember each candidate is a structure with name, votes and a bool), being false, i.e. candidate still runs for election, our check adds 1 to that candidate vote count and breaks the nested loop, jumping to the next voter. Being true means the candidate is eliminated, in that case the nested loop proceeds to check the second ranked preference for that voter, and so on until it finds a candidate able to receive a vote.
void tabulate(void)
{
for (int v = 0; v < voter_count; v++)
{
for (int r = 0; r < candidate_count; r++)
{
int c = preferences[v][r];
if (candidates[c].eliminated == false)
{
candidates[c].votes++;
break;
}
}
}
}To check if we have a winner, main calls for print_winner function. The math is simple and a candidate must have more than half the votes to win. We check that by comparing each candidate’s vote count against the voter_count divided by 2. If any of the candidates has a vote count higher than that, the function prints the candidate name and returns true, ending the program.
bool print_winner(void)
{
for (int c = 0; c < candidate_count; c++)
{
if (candidates[c].votes > (voter_count / 2))
{
printf("%s\n", candidates[c].name);
return true;
}
}
return false;
}From here we know that the election has no winner. In this case main will call for find_min to check between all candidates what’s the least number of votes. To find it, we start a variable with the maximum number of votes (or any other number higher than that). For each running candidate we check if his votes are less than our variable value, if so we refresh our variable to that candidate’s number of votes. That way we always end the looping with the minimum number of votes stored in our variable, which is then returned to main.
int find_min(void)
{
int voteCount = voter_count;
for (int c = 0; c < candidate_count; c++)
{
if (candidates[c].votes < voteCount && candidates[c].eliminated == false)
{
voteCount = candidates[c].votes;
}
}
return voteCount;
}Now we got to check if the election has come to a tie. There are some way to do that, as mostly you do in coding, my solution was to start two variables, one to hold the number of candidates still on the run, and other to hold how many candidates have the minimum amount of votes. A loop feeds this two variables with the information needed, adding 1 to both of them if a candidate is on the run and have the minimum votes, or adding just to on run if the candidate has more than the minimum votes. At the end, if we have the same number of candidates running and with the minimum amount of votes, we have a tie, and the function returns true, making main print all tied candidates’ names. Else, the function returns false and main proceeds to the next step.
bool is_tie(int min)
{
int tieCount = 0;
int onRun = 0;for (int c = 0; c < candidate_count; c++)
{
if (candidates[c].eliminated == false && candidates[c].votes == min)
{
tieCount++;
onRun++;
}
else if (candidates[c].eliminated == false)
{
onRun++;
}
}
if (tieCount == onRun)
{
return true;
}
return false;
}
The last step is the eliminate function. Fairly simple, it changes the bool value from false to true for each candidate that has the minimum amount of votes.
void eliminate(int min)
{
for (int c = 0; c < candidate_count; c++)
{
if (candidates[c].eliminated == false && candidates[c].votes == min)
{
candidates[c].eliminated = true;
}
}
}After the eliminated function runs, the last part of the while loop in main is to set all candidates’ votes back to 0, so as it calls tabulate again it keeps working properly. That’s all!
Thank you for reading. Staff tests and full code with comments bellow.
Results generated by style50 v2.7.4
Looks good!
Results for cs50/problems/2020/x/runoff generated by check50 v3.1.2
:) runoff.c exists
:) runoff compiles
:) vote returns true when given name of candidate
:) vote returns false when given name of invalid candidate
:) vote correctly sets first preference for first voter
:) vote correctly sets third preference for second voter
:) vote correctly sets all preferences for voter
:) tabulate counts votes when all candidates remain in election
:) tabulate counts votes when one candidate is eliminated
:) tabulate counts votes when multiple candidates are eliminated
:) tabulate handles multiple rounds of preferences
:) print_winner prints name when someone has a majority
:) print_winner returns true when someone has a majority
:) print_winner returns false when nobody has a majority
:) print_winner returns false when leader has exactly 50% of vote
:) find_min returns minimum number of votes for candidate
:) find_min returns minimum when all candidates are tied
:) find_min ignores eliminated candidates
:) is_tie returns true when election is tied
:) is_tie returns false when election is not tied
:) is_tie returns false when only some of the candidates are tied
:) is_tie detects tie after some candidates have been eliminated
:) eliminate eliminates candidate in last place
:) eliminate eliminates multiple candidates in tie for last
:) eliminate eliminates candidates after some already eliminated
