BRIAN: Let's take a look at Tideman. In this problem, your task is going to be to implement the Tideman voting algorithm, which is an example of a ranked preference voting algorithm. In a ranked preference voting algorithm, every voter is going to be presented with the opportunity to rank their preferences in order of which candidates are their favorite to their least favorite. So a voter might indicate, for example, that Alice is their favorite candidate. Then comes Charlie, and last comes Bob. And you're going to use all of these ballots together to determine the winner of the election. 

How does the Tideman method of voting work? Well, the Tideman method of voting, also known as ranked pairs, is going to look at each pair of candidates and try and determine for that pair of two people who would win the election if we just looked at those two people. So let's look at some sample ballots. Here are five ballots in an election between Alice, Bob, and Charlie. And let's just look at one pair of candidates. Let's just look at Alice and Bob, ignoring Charlie from the election altogether. 

If we look at these five voters, we'll notice that three of the voters think Alice is better than Bob and prefer Alice over Bob. And two of the voters think Bob is better than Alice. So if this were just an election between Alice and Bob, Alice would beat Bob. We're going to represent that by writing Alice and Bob's names and drawing an arrow from Alice to Bob indicating that Alice would beat Bob in a head to head match up between the two of them. 

Now let's look at another pair of candidates-- Alice and Charlie, for example-- by ignoring Bob from the election altogether. In this case, you'll notice that three voters think Charlie is better than Alice, but only two voters think Alice is better than Charlie. So between Alice and Charlie, the voters tend to prefer Charlie. So we're going to draw an arrow from Charlie to Alice indicating that Charlie beats Alice in a head to head match up. 

Finally, we'll look at the last pair, Bob and Charlie. Between Bob and Charlie, once again, three people think Charlie is the preferred candidate. And two people think Bob is the preferred candidate. So Charlie would beat Bob in a head to head match up. And we'll draw an arrow from Charlie to Bob. 

Now, at this point, to determine the winner of the election, we don't actually need the voters anymore. We can just look at what we're going to call this graph where we have nodes in the graph representing each of the candidates-- Alice, Bob and Charlie-- and arrows in the graph-- also known as edges-- that are pointing from the winner of a pair to the loser of a pair. And by looking at this graph, we can conclude who the winner is. Charlie is the only candidate who has no arrow, no edge pointing towards him. Alice has Charlie pointing towards her, and Bob has Charlie pointing towards him. But Charlie has nobody pointing towards him, meaning there's no candidate that would be preferred over Charlie in a head to head match up. 

Because of that, just by looking at this graph, we can conclude that Charlie should be the winner of the election because Charlie is the so-called source of this graph. There is no edge that points at Charlie. This is effectively the Tideman method of voting, to add in these individual pairs and then figure out who the source of the graph is. But, of course, this was a relatively simple election. And things could be a little more complicated. In particular, it's possible that there is no source of the graph. Let's take a look at an example of that. 

Let's look at this election where, once again, Alice, Bob and Charlie are the candidates. But in this case, there are nine voters. Let's look first at the pair of Alice and Bob by ignoring Charlie from the election altogether. In this case, Alice beats Bob seven votes to two. Seven people think Alice is better than Bob, but only two people think Bob is better than Alice. So we can draw an arrow from Alice to Bob much as we did before. 

Now let's take a look at just Bob and Charlie. Between Bob and Charlie, five voters think Bob is better than Charlie, and four voters think Charlie is better than Bob. So Bob beats Charlie five to four. And we'll draw an arrow from Bob to Charlie. 

Let's now take a look at the last pair between Alice and Charlie. Between Alice and Charlie, you'll notice that there are six voters who think Charlie is better than Alice, but only three voters who think Alice is better than Charlie. So Charlie beats Alice six votes to three. So we can draw an arrow from Charlie to Alice that looks something like this. 

So this graph looks a little bit like rock paper, scissors. Alice beats Bob, Bob beats Charlie, and Charlie beats Alice, which means there is no source of the graph. There's nobody in the election that is undefeated, so to speak, against each of the other candidates, which means that it'd be difficult to determine who the actual winner of the election should be. The Tideman voting method deals with this by rather than adding all of the edges at the same time, adding in the edges one by one. By adding in the edges one by one, you can check for every edge, is it going to create a cycle, a rock, paper, scissors-like scenario? And if an edge would create a cycle, we shouldn't add it to this graph. 

What order should we add the edges in? Well, the Tideman method of voting says that the strongest margin of victory should be the first one that we consider, and we should go in decreasing order of strength to victory. So the first thing we might do is sort these pairs in order of strength of victory. Alice beating Bob is the strongest pair because Alice won with seven votes. Charlie beating Alice comes next because Charlie won with six votes. And Bob beating Charlie was a victory, but it was the weakest victory, a 5 to 4 victory compared to a 6 to 3 victory and a 7 to 2 victory. 

So now we have an ordering of the pairs that we can now add to this graph. Alice beating Bob gets locked into this graph first. Alice beating Bob was the strongest pair, so we'll draw an arrow from Alice to Bob. Charlie beating Alice comes next with a 6 to 3 victory. So we'll draw an arrow from Charley to Alice. Bob beating Charley would come next with a 5 to 4 victory. 

But notice that if we were to add an edge from Bob to Charlie, drawing an arrow pointing from Bob to Charlie, we would create a cycle. And the Tideman algorithm doesn't allow for cycles in this candidate graph, which means we're just going to skip over this edge. If there were more edges later, we'd move to those next, but this one so happens to be the last one. So we're done here. And at this point, we can look for who the source of this graph is. In this case, it's Charlie. So Charlie would be declared the winner of this election. 

In summary, here's how the Tideman voting algorithm works. We first start by tallying the votes. After each of the voters have indicated all of their preferences, we'll determine for each pair of candidates who the winner is. In other words, if you were to just look at that pair, who would be preferred over the other? Then we're going to sort those pairs in decreasing strength of victory where we define strength of victory to mean how many people voted for the winning candidate in the pair? If more people voted for the winning candidate in a pair, then that victory is going to be a stronger victory. 

And finally, we're going to lock in edges into the candidate graph. Starting with the strongest pair and moving in order of decreasing strength of victory, we're going to lock in each pair to the candidate graph as long as that edge wouldn't create a cycle. If the edge would create a cycle, we'll just skip over it. After we've locked in all of the candidates into the graph, the winner of the election is just whoever the source of the graph is, whoever in the graph has no arrows pointing towards them. 

So let's take a look at the data structures and the variables that you might have to deal with in this problem. First up is candidates. And candidates is just going to be an array of strings where each string represents one candidate's name. But they're going to be in an order. So candidate 0 will be the first candidate, candidate 1 is the second candidate, so on and so forth. 

Next up is preferences. Preferences is a two dimensional array where preferences[i][j] is the number of voters who prefer candidate i over candidate j. Let's take a look at an example to see what this actually looks like in practice. 

Here we have three candidates, Alice, Bob and Charlie, where Alice is at index 0, Bob is at index 1, and Charlie is at index 2. And if we fill in the preferences, it'll look a little something like this. The first row, preferences 0, represents preferences for Alice. And the first column means the number of people who prefer Alice over Alice, which in this case is 0. The next cell is 3 because three people prefer Alice over Bob. And the last value in this row is also 3 because three people prefer Alice over Charlie. 

The next row represents Bob. One person prefers Bob over Alice. Nobody prefers Bob over Bob. And one person prefers Bob over Charlie. 

And the final row represents Charlie. One person prefers Charlie over Alice. Three people prefer Charlie over Bob. And nobody prefers Charlie over Charlie because, as with the other two cases, nobody prefers one candidate over themselves. 

We've also defined for you a struct called pair. This struct has two fields; in integer called winner and an integer called loser, where winner is going to represent the candidate index of the winner of this pair, and loser is going to represent the candidate index of the loser of this pair. We can store all of these pairs in an array of pairs, which is going to store all of the pairs where one candidate is preferred above another. In particular, if there is a pair of candidates where technically they're tied and one of them is not preferred over the other, we're not going to add them to the pairs array at all because there's not going to be an edge from one candidate to the other. 

We'll also need to keep track of the candidate graph. And to do that, we'll have a two dimensional array called locked, which will be a two dimensional Boolean array representing this candidate graph. And if locked[i][j] is set to true, that means we've locked in the edge, pointing from candidate i to candidate j. So at first, all of the values in the locked two dimensional array will be set to false, meaning there are no arrows in the graph at all yet. But anytime you add an arrow from candidate i to candidate j, then you should set locked[i][j] equal to true to represent that in your computer's memory. 

So what are the functions you actually need to write in order to implement Tideman? You're going to implement a vote function, a record preferences function, and then a bunch of functions to deal with pairs-- add_pairs, sort_pairs, and lock_pairs-- and finally, a print_winner function to print out the winner of the election. Let's take a look at these one by one. First up is the vote function. The vote function takes in three arguments; an integer representing which rank is currently being voted for, a string representing the name of the candidate currently being voted for, and an array called ranks. And we'll see what that means in just a moment. 

So what is your vote function actually going to do? Well, it's going to first look for a candidate called name. And if we're able to find that candidate, then you should update the ranks array and return true. What does the ranks array actually represent? Well, ranks[i] is going to represent the voters ith preference. So rank 0 is going to be the voter's first preference, their top choice, ranks 1 is going to be their next choice, so on and so forth. If the candidate isn't found and isn't the name of one of the candidates, then you shouldn't update any ranks at all, and your vote function should just return false. 

What are you going to do with that ranks array? Well, it's going to be passed in as an argument to the next function you'll write, record_preferences. And the job of the record_preferences function is going to be to update the preferences two dimensional array based on the current voters ranks. 

So you'll be given a ranks array that looks a little something like this. And what does this actually mean? Well, remember that ranks 0 is the voter's top preference. So candidate 3 is this voter's top preference, which also means that candidate 3 is preferred over candidate 0, 4, 1, and 2. Candidate 0 meanwhile is preferred over candidates 4, 1, and 2. Candidate 4 is preferred over candidates 1 and 2. Candidate 1 is preferred over candidate 2. And candidate 2 was ranked last, so candidate 2 is not preferred over anyone. Using all of this information, your job in this function is going to be to update the preferences two dimensional array to make sure that it accurately represents how many people prefer any candidate over any other candidate in the election. 

The next function you'll write is the add_pairs function. And this is the function that's going to basically add all of the pairs to your pairs array. So how is it going to work? You're going to add each pair of candidates to the pairs array if one candidate is preferred over the other. Again, if two candidates are tied, you shouldn't add them to the pairs array. You'll also want to in this function update the global variable called pair_count to represent the total number of pairs that you currently have in the election. That way we have an accurate count of the number of pairs to use potentially later in this algorithm. 

What might this look like? Well, recall that your preferences two dimensional array might look a little something like this. And in this case, we might have a pair that looks like this, where the winner is candidate 0, and the loser is candidate 1. Why is that? Well, preferences 0, 1-- in other words, the number of people who prefer candidate 0 over candidate 1-- is 3. And preferences 1, 0-- the number of people who prefer candidate 1 over candidate 0-- is 1. So between 0 and 1, candidate 0 is the winner over candidate 1. 

And we could come up with a second pair as well where candidate 2 is the winner in a pair between candidate 2 and candidate 0 because three people prefer candidate 2, and only one person prefers candidate 0. Between candidates 1 and 2, though, it's a tie. They each have two votes each, so neither of them is going to be declared a winner. And we're not going to create a pair for them. 

After you've added the pairs to the pairs array, the next step is going to be to sort them. Recall that the Tideman algorithm is going to go through the pairs in order of decreasing strength to victory, starting with the strongest victory and then moving on in decreasing order. So your job in the sort_pairs function is going to be to take the pairs array and sort it by decreasing strength to victory, where we redefine strength to victory to mean how many people prefer the winner in that pair between the winner and the loser. You can use any sorting algorithm you wish, but try to be as efficient as you can. 

The next function your right is the lock_pairs function. After you've sorted them, the last thing we need to do with the pairs is actually lock them in to this candidate graph. How are you going to do that? Well, you're going to update the locked two dimensional array to create the locked graph by adding in all of the edges going in order of decreasing order of victory strength as long as there is no cycle. Remember that if you try and add an edge that would create a cycle in the graph, then you should skip it and move on to the next edge in the graph instead. 

What might the locked array actually look like? Well, take a look at this graph where Alice is pointing to Bob, Charlie is pointing to Alice, and Charlie is pointing to Bob. We could represent that in this locked two dimensional array. Notice that there are only three values in this two dimensional array that are set to true. Locked 0, 1 is true because Alice, candidate 0, is pointing to Bob, candidate 1. 

Meanwhile, locked 2, 0 is true as well as locked 2, 1, which represents Charlie pointing to Alice and Charlie pointing to Bob. This two dimensional array, also known as an adjacency matrix, will allow us to represent this candidate graph and keep track for every pair who is the winner and who is the loser. 

After you've done all of that with the pairs, the last step is the print_winner function, which is responsible for printing out the winner of the election. And recall that the winner of the election will be whoever the source of the graph is, where the source of the graph is the candidate who has no edges pointing towards them. You can assume for the purpose of this program that there will not be more than one source in a graph, even though theoretically a graph could have more than one source. Take a look at this locked graph, for example, the same one we were looking at before. In this case, candidate 2, Charlie, is the source of the graph because they have no edges pointing at them. And see if you can look for patterns in this locked graph that would allow you to determine conclusively for any particular candidate are they, in fact, the source of the graph? 

Once you've implemented these functions, you should be able to simulate a Tideman election, allowing for voters to rank all of their preferences and then concluding for each pair of candidates who the winner of that pair would be, then locking in those pairs in order into a candidate graph and determining who the winner of the election is by asking who the source of the graph actually is. My name is Brian. And this was Tideman.