CS50 PSet 3: Plurality

A guide to the ‘Plurality’ problem in CS50 Week 3.

Goal: To write functions to determine the winner of a plurality election and to print the name of the winner.

The vote function takes a single argument, a string called name, representing the name of the candidate who was voted for. This function must return either true or false, depending on whether or not the name given matches any of the candidates in the election. If it returns true, it must also increase by 1 the votes value for that candidate.

The print_winner function must print out the winner of the election (simply the candidate who has received the most votes), followed by a new line. In the result of a tie, it should print the name of each winning candidate on a separate line.

This problem is different to those that we have dealt with so far as the main function is already written for us, with the vote and print_winner functions left blank. This is an approach you will see more of in upcoming PSets as they become more complex.

The program takes as command line arguments the names of the candidates, of which there can be any number up to 9, before prompting for the number of voters. Each vote is then prompted for and the winner(s) printed out at the end.

$ ./plurality Alice Bob
Number of voters: 3
Vote: Alice
Vote: Bob
Vote: Alice
Alice

The first function we have to write is the vote function, which returns a boolean value based on whether or not a valid candidate was voted for. It is used in the main function as shown below, causing “Invalid vote.” to be printed if it returns false.

        // Check for invalid vote
if (!vote(name))
{
printf("Invalid vote.\n");
}

This is a fairly simple function, just looping through the candidates and checking if the name value of the candidate struct (defined at the start of the script) matches the name argument. This is done using strcmp(), meaning the <string.h> library must be included at the start of the file. This function is called once for every voter, so the name argument represents the candidate they attempted to vote for.

The candidate struct was defined with both a name and an integer vote count. If the name matches, we can increment the vote count for that candidate by 1 and return true, exiting the function. If the names do not match, the function returns false.

// Update vote totals given a new vote
bool vote(string name)
{
// Check name matches a candidate name
for (int i = 0; i < candidate_count; i++)
{
if (strcmp(candidates[i].name, name) == 0)
{
candidates[i].votes++;
return true;
}
}
return false;
}

The print_winner function takes no arguments. Its objective is to determine the candidate or candidates with the most votes and print their name(s).

This can be done by looping through all of the candidates twice. Before the first loop, we define a max_votes integer. Then loop through each of the candidates, updating the maximum amount of votes each time a new maximum is found.

The second time looping through the candidates will print the name of any candidate who has received the maximum amount of votes. This approach allows the name of all winners to be printed in the result of a tie.

While the use of two similar loops may seem inefficient, it must be done here as the max_votes value must be determined before the winners can begin to be printed.

// Print the winner (or winners) of the election
void print_winner(void)
{
// Get max votes
int max_votes = 0;
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes > max_votes)
{
max_votes = candidates[i].votes;
}
}

That was how I approached plurality, a gentle enough introduction to the use of structs and a warm up for the infamous tideman problem I had been reading horror stories about…