BRIAN: Let's now dive into runoff. In runoff, we're going to take advantage of ranked preference voting, whereas in plurality, each voter only got to vote for one candidate. In runoff, a voter might be able to rank all of their candidates in sequence, so the ballot might look a little something like this, where they have a space to fill in their first preference, second preference, and third preference, for example. 

One voter, for instance, might want Alice as their first preference vote. But if Alice can't win, their next choice would be Charlie. And if Charlie can't win, their next choice would be Bob. So this is what a ranked preference ballot might look like. How then does the runoff vote actually work? 

Well, the runoff vote is first going to say that every voter should rank all of their preferences, first, second, third, up to as many candidates as there are in the election. If any candidate has a majority of the vote, meaning more than half of the votes, then that candidate is going to be declared the winner of the election. But if nobody has a majority, we're going to eliminate the candidate with the fewest number of votes and rerun the election without them, and we're going to keep repeating that process until someone has won a majority of the votes. 

So let's take a look at a simple example. In this election, we have seven votes, which means that a candidate needs four votes, a majority of the seven in order to win the election. The candidates here are Alice, Bob, and Charlie. And so we'll look at the ballots one at a time. For this first ballot, Alice is this voter's top preferred candidate. So Alice is going to get this ballot. This next ballot is also going to go to Alice. This ballot has Bob as their top choice, so Bob gets this ballot as well as the next one. The next ballot goes to Alice. The next ballot goes to Bob. And the final ballot has Charlie as the top preferred candidate. 

At this point, Alice has three votes, Bob has three votes, and Charlie has one vote. But remember, with seven votes in this election, a candidate needs four votes in order to win. So at this point, we need to hold a runoff. Charlie has the fewest number of votes in this election so far, so Charlie is going to be eliminated from the race. 

What happens to the voter who originally voted for Charlie? Well, that voter had a second preference. And their second preference was Alice. So Alice at this point is going to get this last ballot. Alice now has four votes compared to Bob's three votes, and four is a majority. So Alice is going to be declared the winner of this election. 

That, in short, is how a runoff election works. But it could be a little more complicated. So let's take a look at a more sophisticated example, this time with 10 ballots and four different candidates, Alice, Bob, Charlie, and Dave. The first step happens, and we give each candidate, all of the voters who chose that candidate as their first preference. And at this point, Alice has three votes, Bob has four votes, Charlie has one vote, and Dave has two votes. 

In a plurality election, or a first past the post election, Bob would win this election now, because Bob has more votes than anyone else. But with 10 ballots in the election, in a runoff election, a candidate needs a majority, or six out of the 10 votes in order to be declared the winner. Since nobody has six votes yet, we need to hold a runoff. Charlie, again, is in last place in this election, so we're going to eliminate Charlie from the election, and their voter is going to now vote for Alice, the second preference. 

Alice now has four votes. Bob has four votes. And Dave has two votes. Still, nobody has a majority of six votes, so we need to hold yet another runoff. Dave has the fewest number of votes in this election at this point. So Dave is going to be eliminated. What happens to the people who voted for Dave? Well, the first person who voted for Dave chose Alice as their next preference, and the second voter who voted for Dave chose Charlie as their second preference. 

But Charlie has already been eliminated, so the vote can't go to Charlie either. So we now look to that voter's third preference, which in this case, is also Alice. This means that Alice gets each of the two remaining votes, and Alice now has six votes compared to Bob's four. Alice has a majority of the votes in the election, so Alice is declared the winner of this election. 

Your task in runoff is going to be to write a program that simulates this style of runoff election. So how are you going to do that? Well, one thing to think about is how you're going to represent this data. And one piece of data you're going to need to represent are all of the candidates and the information associated with them. In this case, in addition to storing the candidate's name and the number of votes they currently have, you'll also want to store a Boolean flag, true or false, representing whether that candidate has been eliminated from the race yet or not. 

At first, all of these values will be false, because nobody will have been eliminated, but as candidates are eliminated in this runoff process, you might switch those values from false to true. You can represent each of these candidates using a struct that we'll give you, where this struct representing a candidate has three fields, a string field called name, and int field, called votes, and a Bool field, called eliminated, representing whether or not that candidate has been eliminated from the election or not. 

We can store a sequence of these candidates inside an array of candidates, where each individual element in that array is one of these candidate's structs. But the candidates aren't the only piece of information that we need to keep track of in order to run the runoff election. We also need to keep track of information about the voters, in particular about who their preferences are. And to do that, we're going to represent preferences using a two dimensional array called preferences. 

How do you interpret this two dimensional array? Well, preferences IJ, meaning row I and column J, is going to be a cell that store is the index of the candidate who is voter I's preference number J. So what does that actually mean? Let's take a look at an example. 

In this case, we have three candidates, Alice, Bob, and Charlie, where Alice is stored at index 0 in the candidate's array, Bob is stored at index 1, and Charlie is stored at index 2. What happens if we say something like preference of 0, 0 equals 2. Well, that means we're going to fill into row 0 and column 0 of this array, the number 2. 

And the way to interpret that is that row 0 is talking about the first voter , and column 0 is talking about the first preference for that voter. And the 2 means candidate at index 2, which in this case is Charlie. So preference 0, 0 equals true means the first voter's top preferred candidate is, in fact, Charlie. 

What if we then said preferences 0, 1 equals 0? Well, that would mean we would fill in the number 0 into this slot in the two dimensional array. We're still on preference is 0, this first row talking about the first voter. But now we're on column 1, which is here going to represent the voter's second preference. 

Their second preference is zero, and candidate 0 is Alice. So preference is 0, 1 equals 0 means the first voter's second preferred candidate is Alice. And we can fill in this entire preference's two dimensional array to keep track of every single voter and every single preference that that voter has. 

So what do you actually need to do to implement the runoff program? Well inside of runoff.c, you're going to implement six functions that will perform the algorithm of implementing this runoff election. First, you'll implement vote, then tabulate, then print winner, then find min, then is tie, and then finally, eliminate. And we'll go through each of these functions one by one. 

Let's start with the vote function. The vote function takes three arguments, an integer called voter, representing which number voter is currently voting. It also takes an integer called rank, representing which rank the voter is currently trying to indicate a preference for, rank 0 meaning their top preference rank 1, meaning their next preference, so on and so forth. 

And finally, the function takes in a string called name, indicating which candidate they're currently trying to vote for. So what is vote going to do? Well, your vote function should look for a candidate called name. If you find that candidate, you should update the two dimensional array of preferences, so that they are that voter's rank preference. And then you should return true to indicate that you were successfully able to record this preference. But if no candidate was found, you shouldn't update any preferences at all, and your function should just return false. 

Let's take a look at it example. Here again, we have Alice, Bob, and Charlie. And here again, we have a two dimensional array of preferences, which is going to be stored as a global variable in your program. Let's imagine that this ballot comes along, where the first preference is Alice, then comes Charlie, then comes Bob. 

Well, Alice is the candidate at index 0 in the candidate's array, which means we're going to fill in 0 in to row 0 and column 0 of this array, representing the first voter's top preference. This voter's next preference is Charlie, who's at index 2 in the array. So 2 gets filled in to the next spot in this preferences row. 

And finally, Bob is the third preference. Bob, again, is at index 1 in the array. So 1 gets filled in next. And we're going to do this for each of the votes that comes our way. If the next voter votes for Charlie as their top preference, and Charlie is at index 2 in the candidate's array, then we're going to fill in 2 as the first preference for this voter. Bob is the second preference, who's at index 1, and Alice is the third preference, who is the candidate at index 0. And we're going to do the same thing for each remaining voter who votes in the election until by the end of it, we filled in the entire preferences array for each of the voters and for each of their preferences. 

Next up is the tabulate function, and the job of the tabulate function is going to be the update the vote counts for each of the candidates to represent how many votes they currently have. How are you going to do that? Well, recall that every voter is going to ideally vote for their highest preference candidate, but a voter can't vote for a candidate who's already been eliminated. So each voter is going to vote for their highest preferred candidate who has not yet been eliminated from the race. 

So what might this tabulate function actually do on some sample data? Well, let's take a look at these preferences and these candidates. None of the candidates have been eliminated yet. Alice's eliminated status is set to false, and so is Bob's, and so is Charlie's, which means that since nobody has been eliminated, every voter gets to vote for their top preferred candidate. This first voter, for example, is voting for candidate 0, who's Alice. So our tabulate function would update Alice's vote total, changing it from 0 to 1. 

Next up, this voter's voting for Charlie. The next voter is voting for Bob. The next voter is voting for Charlie again. And the final voter is voting for Alice. So at the end of our tabulate function, we should have recorded in our candidates array that Alice has two votes, Bob has one vote, and Charlie has two votes. 

But what happens in a more complex scenario, where, for example, Bob may have been already eliminated from this election, and we want to tabulate these votes again. Well, we'd go through the array, much as we did before and see that the first voter was voting for Alice, and the second voter is voting for Charlie, the candidate at index 2, and the third voter is trying to vote for the candidate at index 1, who in this case is Bob. 

But Bob's already been eliminated, so the vote can't actually go to Bob. So instead, this voter is going to look at their next preference, candidate number 2, who in this case, is Charlie. Charlie's still in the race, and so Charlie gets this vote, and his vote total gets updated from 1 to 2. 

The next voter votes for Charlie, no problem, and the final voter votes for Alice, so by the end of it, Alice has two votes, and Charlie has three. So that's what you're tabulate function is going to do, go through each of the voters and update the vote counts, making sure to only update vote counts for candidates who are still in the race. 

The next function you're going to write is print winner. The print winner function is going to be a function that's ultimately going to be tasked with printing out who the winner of the election is if there is a winner yet. What does that mean? Well, if any candidate has more than half of the vote, in other words, a majority of the vote, you should print out their name and return true from this function. But it's possible that no candidate has yet won the election because nobody has more than half the vote. In that case, you shouldn't print out anything, and your function should just return false. 

So let's take a look at an example. In this case, there are five total votes in this election, and because there are five votes, you would need three votes, a majority, in order to win. Since nobody has three votes, that means there is no winner yet. So your print winner function shouldn't print out any names and should just return false. 

But now, let's take a look at these votes, for example. Still, there are five total votes, which means you need three votes in order to win, but here, Charlie has three votes. So Charlie would be the winner of this election. Your print winner function, in this case, should print out Charlie's name and then return true to indicate that Charlie is, in fact, the winner of this election. 

The next function you'll implement in runoff.c is called find min. In find min, what you'll do is you'll return the minimum number of votes of anyone still in the election. And we'll use this to figure out, for example, who we need to eliminate in this runoff process. So let's take a look at an example. 

Here's a sample election with five candidates, Alice, Bob, Charlie, Dave, and Emma, and their vote totals. And notice, that based on the fact that all of their eliminated flags are all set to false, all five candidates are still in the election. Here, your algorithm should return the number one from this find min function because Bob is the candidate that has the fewest votes out of anyone in the current election. 

Of course, you may run into a situation where some candidates have already been eliminated. Let's take a look at an example of that. Here, for example, Bob has already been eliminated. For Bob's candidate struct, his eliminated status is set to true. So in this case, we wouldn't want to return 0 as the minimum, even though 0 is the smallest vote total of any candidate inside of this array, because Bob's already been eliminated. And we only want to consider candidates that are still in the election. 

So in this case, the candidates that have the fewest number of votes are Alice and Emma, who both have two votes each, and so 2 is the number that we would return from find min in this case. The next function you'll implement is called is tied, and the job of is tied is to decide whether or not this election is tied between all of the remaining candidates. So how does this function work? 

Well, the function will take as input in integer called min, which is that minimum number of votes that you calculated inside of the find min function. And is tied should return true if the election is tied between all of the remaining candidates. If it's not tied between all of the remaining candidates, then your function should return false. 

So for example, if all of the candidates are still in the election, and every candidate has two votes, then this election is a tie, and your function should return true. Of course, this election is also tied. Even though candidates have different vote totals, Bob and Dave have already been eliminated from the election, so I'm only looking at the three other people that are still in the election. They each have two votes, and so because it's a tie between all of the remaining candidates in the election, then this function should return true. 

Finally, the last function that you'll write in runoff.c is called eliminate, and this is the function that's going to take care of the process of actually eliminating the candidate who's in last place in the election, such that the election can run again, as if that person had not been in the election in the first place. 

So your eliminate function should eliminate anyone still in the race, who has the min number of votes. Recall that min is going to be the input to this function, and it's going to be that value that you computed in the find min function. So anyone who has the fewest number of votes in the election, which might be one candidate, or it might be more than one, they should all be eliminated from the election. 

Let's take a look at an example. Here, for example, none of the candidates have yet been eliminated, but we can see that Bob is the candidate who has the minimum number of votes. He has one vote, and everyone else has more than that. So your eliminate function should update Bob's candidate struct, changing eliminated from false to true to indicate the fact that Bob has now been eliminated from this election. 

Of course, when we run the runoff the next time around and recompute the vote totals, we might get something a little like this, where Bob has now been eliminated, and now we've decided the minimum number of votes that anyone still in the election has is 2. What should your function do in this case? 

Well, your function should look through the candidates and identify that both Alice and Emma each have two votes, the minimum number of votes of anyone in the election. And your function should eliminate both of them, taking each of their candidate structs and changing eliminated from false to true for each of them. 

Once you've done that, you'll have completed all that you need to implement a runoff election by implementing the vote, tabulate, print winner, find min, is tied, and eliminate functions, you'll be able to simulate this runoff election you can test for yourself by running ./runoff and then passing in as command line arguments the names of the candidates in the election, and then typing in each voter's ranked preferences, and then seeing whether your program computes the correct winner of this runoff election. 

My name is Brian, and this was runoff.