Runoff

Log into cs50.dev, click on your terminal window, and execute cd by itself. You should find that your terminal window’s prompt resembles the below:

$

Next execute

wget https://cdn.cs50.net/2024/fall/psets/3/runoff.zip

in order to download a ZIP called runoff.zip into your codespace.

Then execute

unzip runoff.zip

to create a folder called runoff. You no longer need the ZIP file, so you can execute

rm runoff.zip

and respond with “y” followed by Enter at the prompt to remove the ZIP file you downloaded.

Now type

cd runoff

followed by Enter to move yourself into (i.e., open) that directory. Your prompt should now resemble the below.

runoff/ $

If all was successful, you should execute

ls

and see a file named runoff.c. Executing code runoff.c should open the file where you will type your code for this problem set. If not, retrace your steps and see if you can determine where you went wrong!

Whenever you’ll extend the functionality of existing code, it’s best to be sure you first understand it in its present state.

Look at the top of runoff.c first. Two constants are defined: MAX_CANDIDATES for the maximum number of candidates in the election, and MAX_VOTERS for the maximum number of voters in the election.

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

Notice that MAX_CANDIDATES is used to size an array, candidates.

// Array of candidates
candidate candidates[MAX_CANDIDATES];

candidates is an array of candidates. In runoff.c a candidate is a struct. Every candidate has a string field for their name, an int representing the number of votes they currently have, and a bool value called eliminated that indicates whether the candidate has been eliminated from the election. The array candidates will keep track of all of the candidates in the election.

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

Now you can better understand preferences, the two-dimensional array. The array preferences[i] will represent all of the preferences for voter number i. The integer, preferences[i][j], will store the index of the candidate, from the candidates array, who is the jth preference for voter i.

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

The program also has two global variables: voter_count and candidate_count.

// Numbers of voters and candidates
int voter_count;
int candidate_count;

Now onto main. Notice that after determining the number of candidates and the number of voters, the main voting loop begins, giving every voter a chance to vote. As the voter enters their preferences, the vote function is called to keep track of all of the preferences. If at any point, the ballot is deemed to be invalid, the program exits.

Once all of the votes are in, another loop begins: this one’s going to keep looping through the runoff process of checking for a winner and eliminating the last place candidate until there is a winner.

The first call here is to a function called tabulate, which should look at all of the voters’ preferences and compute the current vote totals, by looking at each voter’s top choice candidate who hasn’t yet been eliminated. Next, the print_winner function should print out the winner if there is one; if there is, the program is over. But otherwise, the program needs to determine the fewest number of votes anyone still in the election received (via a call to find_min). If it turns out that everyone in the election is tied with the same number of votes (as determined by the is_tie function), the election is declared a tie; otherwise, the last-place candidate (or candidates) is eliminated from the election via a call to the eliminate function.

If you look a bit further down in the file, you’ll see that the rest of the functions—vote, tabulate, print_winner, find_min, is_tie, and eliminate—are all left to up to you to complete! You should only modify these functions in runoff.c, though you may #include additional header files atop runoff.c if you’d like.

Complete the vote function.

• The function takes three arguments: voter, rank, and name.
• If name is a match for the name of a valid candidate, then you should update the global preferences array to indicate that the voter voter has that candidate as their rank preference. Keep in mind 0 is the first preference, 1 is the second preference, etc. You may assume that no two candidates will have the same name.
• If the preference is successfully recorded, the function should return true. The function should return false otherwise. Consider, for instance, when name is not the name of one of the candidates.

As you write your code, consider these hints:

• Recall that candidate_count stores the number of candidates in the election.
• Recall that you can use strcmp to compare two strings.
• Recall that preferences[i][j] stores the index of the candidate who is the jth ranked preference for the ith voter.

Complete the tabulate function.

• The function should update the number of votes each candidate has at this stage in the runoff.
• Recall that at each stage in the runoff, every voter effectively votes for their top-preferred candidate who has not already been eliminated.

As you write your code, consider these hints:

• Recall that voter_count stores the number of voters in the election and that, for each voter in our election, we want to count one ballot.
• Recall that for a voter i, their top choice candidate is represented by preferences[i][0], their second choice candidate by preferences[i][1], etc.
• Recall that the candidate struct has a field called eliminated, which will be true if the candidate has been eliminated from the election.
• Recall that the candidate struct has a field called votes, which you’ll likely want to update for each voter’s preferred candidate.
• Recall that once you’ve cast a vote for a voter’s first non-eliminated candidate, you’ll want to stop there, not continue down their ballot. You can break out of a loop early using break inside of a conditional.

Complete the print_winner function.

• If any candidate has more than half of the vote, their name should be printed and the function should return true.
• If nobody has won the election yet, the function should return false.

As you write your code, consider this hint:

• Recall that voter_count stores the number of voters in the election. Given that, how would you express the number of votes needed to win the election?

Complete the find_min function.

• The function should return the minimum vote total for any candidate who is still in the election.

As you write your code, consider this hint:

• You’ll likely want to loop through the candidates to find the one who is both still in the election and has the fewest number of votes. What information should you keep track of as you loop through the candidates?

Complete the is_tie function.

• The function takes an argument min, which will be the minimum number of votes that anyone in the election currently has.
• The function should return true if every candidate remaining in the election has the same number of votes, and should return false otherwise.

As you write your code, consider this hint:

• Recall that a tie happens if every candidate still in the election has the same number of votes. Note, too, that the is_tie function takes an argument min, which is the smallest number of votes any candidate currently has. How might you use min to determine if the election is a tie (or, conversely, not a tie)?

Complete the eliminate function.

• The function takes an argument min, which will be the minimum number of votes that anyone in the election currently has.
• The function should eliminate the candidate (or candidates) who have min number of votes.