Cs50 Problem set 3 Runoff Solution 2020: my step by step explanation

Having completed plurality, here comes its friend Runoff, where we are told to write 6 functions that mimic voting in a more advanced way.

it wasn’t easy for me at first, I had to take a little break before I resumed back to the pset when I eventually complete it.

if you are being told that programming is easy, then it’s a big lie. you need to think out of the box.

enough of the story and let me go into the real stuff.

Pset 3 Runoff Solution

we need to execute the wget command to download the distribution code, which contain various functions that are emptied for us to complete.

Vote function

We are to update the vote function such that it keeps track of all the preference, if at any point, the ballot is deemed to be invalid, the program should exist.

The vote function takes in three-argument name, rank, and voters, this function takes the name of the voter’s choice and compares it with the candidate name, if both are similar then we should update the candidate name as the first preference of the voter.

Vote function pseudocode

• Iterate through the candidate_count
• then check if the name of the candidate is similar to the voter’s choice candidate
• if the same, update preferences so that they are the voter’s rank preference, and return true.
• else if no candidate found, don’t update any preferences and return false.

code here

for (int i = 0; i < candidate_count; i++)
{
        if (strcmp(name, candidates[i].name)==0)
        {
            preferences[voter][rank] = i;
            return true;
        }
    }
    
    return false;

Tabulate Function

in this function, we are to update the vote count for each of the candidates to represent how many votes they currently have. this function updates the vote total for the candidate who has not been eliminated

Tabulate pseudocode

• Iterate through voter_count and candidate_count
• then check if candidate preference at the index has been eliminated.
• if not, update the total vote of the candidate preference at that index and return true.

for (int i = 0; i < voter_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
           int candidate_index = preferences[i][j];
           if (candidates[candidate_index].eliminated == false)
           {
               candidates[candidate_index].votes++;
               break; 
           }
        }
    }
    return;

explanation..

• we iterate through the voter_count and candidate_count because they are the one that represents the preference index of the candidate.
• then i create a new variable candidate_index to represent preference[i][j] for simplicity, where [i][j] means first voter’s [i] and which preference [j] it belong to.
• then we check if candidates[candidate_index].eliminated is equal to false, (this means that if the candidate is not yet eliminated), we should update the votes of the candidate at that preference. then add break.

Print_winner function

This function prints the winner if there’s one. The logic here is that the winner must have more than half the votes.

pseudocode

• Iterate through the voter_count
• then check if any candidate in the index has more than half of the vote
• if so, then print out the name of the candidate at that index and return true
• else, return false

for (int i = 0; i < voter_count; i++)
    {  
        int half_vote = voter_count/2;
        if (candidates[i].votes > half_vote)
            {
               printf("%s\n", candidates[i].name);
               return true; 
            }
    }
    return false;

find_min explanation

This function returns the minimum number of votes of anyone still in the election, which we can then use to figure out who we will need to be eliminated.

pseudocode

• Iterate through the candidate_count
• then check if the candidate has been eliminated and less than MAX_VOTERS,
• if so assign MAX_VOTER to hold the candidate’s votes.
• return mini_vote

int find_min(void)
{
    int mini_vote = MAX_VOTERS; 
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false && candidates[i].votes < mini_vote)
        {
            mini_vote = candidates[i].votes;
        }
    }
    return mini_vote; 
}

Is_tie function

The main purpose of is_tie function is to decide whether or not the election is a tie between all of the remaining candidate, if there is, it should return true and return false if not.

pseudocode

• Iterate through candidatte_count
• then check if the candidate has been eliminated and candidates are not equal to min.
• if so, return false
• else return true.

bool is_tie(int min)
{
    for (int i = 0; i < candidate_count; i++) 
    {
        if (candidates[i].eliminated == false && candidates[i].votes != min )
        {
           return false; 
        }
    } 
 
  return true;

eleminated function

• This function eliminates the candidate, which is the last person in the election, such that the election can be run again.

pseudocode

• iterate through the candidate_count
• then check if candidate at index votes is equal to min,
• if so, then set candidate at that index, eliminated to true.

for (int i = 0; i < candidate_count; i++)
  {
        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true; 
        }
    }
    // TODO
    return;

Runoff Code here

That’s all, I hope you are able to walk through all functions step by step as discussed in this post. Don’t forget to always understand every line of your code.

Also do ask questions, if you have any in the comments box…

Pls comment and share, Thanks🤝.