CS50x Plurality
From problem set 3
Plurality is a fairly simple introduction exercise to the next on the problem set, either you choose the less comfortable route with Runoff or the more comfortable with Tideman.
In Plurality we need to organize a simple election. The main function and headers are given by the course as a distribution code. We can’t change the distribution code or else we fail the staff tests. Our task is to implement the function that updates the voting count for each candidate and the function that print out the winner, or winners, as this simple model of election allows for frequent ties. Here’s and example of how the program should work.
$ ./plurality Alice Bob Charlie
Number of voters: 4
Vote: Alice
Vote: John
Invalid Vote.
Vote: Charlie
Vote: Alice
AliceOur candidates are prompted as command line arguments when we start the program. The distribution code takes care of asking for the number of voters and then for each of their votes. Let’s take a look at how it looks.
#include <cs50.h>
#include <stdio.h>
#include <string.h>// Max number of candidates
#define MAX 9// Candidates have name and vote count
typedef struct
{
string name;
int votes;
}
candidate;// Array of candidates
candidate candidates[MAX];// Number of candidates
int candidate_count;// Function prototypes
bool vote(string name);
void print_winner(void);int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: plurality [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].name = argv[i + 1];
candidates[i].votes = 0;
}int voter_count = get_int("Number of voters: ");// Loop over all voters
for (int i = 0; i < voter_count; i++)
{
string name = get_string("Vote: ");// Check for invalid vote
if (!vote(name))
{
printf("Invalid vote.\n");
}
}// Display winner of election
print_winner();
}
Pretty self explanatory with its comments, just some points I’d like to write about. We have a new tool in this code called structure. It’s syntax is shown at line 9 typedef struct. Structures are a way of storing several variables that are related to the same thing in a new type created by ourselves, like int or char, but whatever we want to call it. In this case they relate to the candidates. Each candidate will be saved as a type “candidate” with name and a vote count inside an array initialized just bellow our struct definition.
The first loop we see inside main is the one that populates that array. It gets our argv[1], and so on, and saves it inside the array. Being argv[1] = Alice, we would have: candidates[0].name = Alice, candidates[0].votes = 0; Both Alice and 0 are part of the same index inside the array, and now we can access a string and an int using the same index! That’s invaluable for building our functions vote and print_winner.
For vote, main iterates through each voter asking for his vote and then check if it’s a valid vote, i.e. matches a candidate name. Our first job is to code that check. The function takes a single argument called name, that is the name of the candidate that the voter wants to support. It should add a vote to that candidate vote count if the vote is valid, or return an error statement if the code is invalid. Both options will keep the program running afterwards. We can accomplish that with a simple loop.
bool vote(string name)
{
for (int n = 0; n < candidate_count; n++)
{
if (strcmp(name, candidates[n].name) == 0)
{
candidates[n].votes++;
return true;
}
}
return false;
}The loop iterates through each candidate checking if the name matches. Here we use a function from string library called strcmp. It’s the simplest way to compare two strings, and returns 0 if both are equal. Passed the check, the loop adds 1(++) to that candidate’s vote count, saved in candidates[index].votes. Else, if the loop finds no match for name, it returns false and main takes care of printing the error message.
We can run some tests here and see if the function is returning the error message for invalid votes.
Next, for the print winner function. We need a counter where we’ll set the highest vote count, and we need to make sure that if there’s a tie both, or more, candidates are printed.
void print_winner(void)
{
// TODO
int winner = 0;
for (int v = 0; v < candidate_count; v++)
{
if (candidates[v].votes > winner)
{
winner = candidates[v].votes;
}
}We take care of the first problem with a loop that check each candidate’s votes and update an integer called winner every time it finds a higher count. Now we know how many votes the winner has, but we don’t know which candidates have that vote count.
for (int w = 0; w < candidate_count; w++)
{
if (candidates[w].votes == winner)
{
printf("%s\n", candidates[w].name);
}
}
}A second loop (a brother loop, not nested) solves that by checking each candidate for that same vote count and printing it every time the counts match. That ends our print_winner function. It’s also the end of our code.
We can make sure it’s working by running small tests with two to four candidates.
Bellow you can find the staff tests for this problem and the full code with comments.
Results generated by style50 v2.7.4
Looks good!
Results for cs50/problems/2020/x/plurality generated by check50 v3.1.2
:) plurality.c exists
:) plurality compiles
:) vote returns true when given name of first candidate
:) vote returns true when given name of middle candidate
:) vote returns true when given name of last candidate
:) vote returns false when given name of invalid candidate
:) vote produces correct counts when all votes are zero
:) vote produces correct counts after some have already voted
:) vote leaves vote counts unchanged when voting for invalid candidate
:) print_winner identifies Alice as winner of election
:) print_winner identifies Bob as winner of election
:) print_winner identifies Charlie as winner of election
:) print_winner prints multiple winners in case of tie
:) print_winner prints all names when all candidates are tied