Runoff, votes program in C

By the end of my second week of learning programming, there was a problem to solve which admittedly took me some time to figure out as the level of complexity from the previous problem jumped quite significantly.

The problem description is pretty lengthy, so instead of writing it all here, let me just put a video walkthrough that explains what needs to be done. They also provided the distribution code that has the main function already pre-written. If you’d like to dive deeper into the problem or perhaps even try solving it yourself, definitely start with that video and the source code.

The task was to complete the six functions named vote, tabulate, print_winner, find_mind, is_tie, and eliminate.

As always, if you are an experienced programmer, your feedback would be appreciated. The whole point of this post is for me to get a better understanding of what I’ve learnt for the past week or so.

Vote

So, the first function, vote, should update the global preferences array to indicate that the voter has that candidate as their preference.

I’ll start with writing a pseudocode:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    // If candidate name is found and not eliminated, update the voter preference and return true
    // If candidate name not found or eliminated, return false
}

To check all votes, I need to iterate through all candidates using the global candidate_count variable:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
    // If candidate name is found and not eliminated, update the voter preference and return true
    }
    
    // If candidate name not found or eliminated, return false
}

To check whether the candidate’s name matches, I’ll use the strcmp function to compare the string name (which is the input parameter of the vote function) with the name field of the ith candidate struct. And I’ll check whether the candidate is eliminated in the same if statement, like so:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0 && !candidates[i].eliminated)
        {
            // Record the vote preference

            return true;
        }
    }

    // Candidate name not found or eliminated, vote is invalid
    return false;
}

The most challenging part for me was to figure out how to record the vote preference, the actual action inside this loop and the sole purpose of this function.

Let me share my thought process. What does ‘record (or update) the vote preference’ actually mean? Well, preferences is a two-dimensional array used to store the voting preferences of each voter. It represents a grid where each row corresponds to a voter, and each column corresponds to a rank of preference for a candidate. The vote function also takes two inputs: voter, which represents the index of the current voter in the array of voters, and ranks, which represents the index of the preference rank for the current candidate.

Putting it all together, it means that for the current voter at index voter, at the given preference rank rank, the candidate at index i in the array of candidates is chosen as the preference. So the final code of this function is the following:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0 && !candidates[i].eliminated)
        {
            // Record the vote preference
            preferences[voter][rank] = i;
            return true;
        }
    }

    // Candidate name not found or eliminated, vote is invalid
    return false;
}

I still wrap my head around this line preferences[voter][rank] = i;, so let me provide additional explanation for future me reading this blog.

Let’s say, we have three candidates named Alice, Bob, and Charlie, indexed as 0, 1, and 2 in the candidates’ array respectively. We also have three voters indexed as 0, 1, and 2 too. And, as an example, let’s say the first voter ranked their candidate preferences in the ballot in the following order: Charlie, Alice, Bob.

Now if we look back at that line of code again, it effectively stores the index of the chosen candidate in the preferences array, like so:

I hope it explains!

Tabulate

The next function, tabulate, 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.

I’ll start with a pseudocode again to outline the general logic of this function:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
        // Iterate through each rank until a valid vote is cast
            // Get the index of the preferred candidate for this rank

            // Check if the preferred candidate is not eliminated
                // Update the vote count for the preferred candidate and break out of the loop
}

So the function iterates through each voter, considering their ranked preferences. For each voter, it iterates through each rank until it finds a valid vote for a non-eliminated candidate. For that purpose, I’ll a basic loop-within-the-loop construction:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
    for (int i = 0; i < voter_count; i++)
    {
        // Iterate through each rank until a valid vote is cast
        for (int j = 0; j < candidate_count; j++)
        {
            // Get the index of the preferred candidate for this rank

            // Check if the preferred candidate is not eliminated
        }
    }
}

It seems I’m going to need a new integer variable to store the index of the candidate preferred by the current voter at the given rank, which I could later use to incrementally update the vote count.

And here is the final code for this function:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
    for (int i = 0; i < voter_count; i++)
    {
        // Iterate through each rank until a valid vote is cast
        for (int j = 0; j < candidate_count; j++)
        {
            // Get the index of the preferred candidate for this rank
            int preferred_candidate_index = preferences[i][j];

            // Check if the preferred candidate is not eliminated
            if (!candidates[preferred_candidate_index].eliminated)
            {
                // Update the vote count for the preferred candidate and break
                // out of the loop
                candidates[preferred_candidate_index].votes++;
                break;
            }
        }
    }
}

Just to clarify, preferences[i][j] retrieves the index of the candidate preferred by the voter at index i for the current rank j. This index is then stored in the preferred_candidate_index variable.

This line candidates[preferred_candidate_index].votes+ increments the votes field for the candidate with the index preferred_candidate_index. It means that the voter’s vote at the current rank has been cast for this candidate, and we update the candidate’s vote count accordingly.

Print winner

The print_winner should print the winner’s name If any candidate has more than half of the vote, and don’t print anything if nobody has won the election:

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // Check each candidate's votes
    
        // If a candidate has more than half of the votes, they are the winner


    // No winner found, return false
}

So I’ll iterate through each candidate again and check if their votes exceed half of the total votes. To see whether the candidate has the majority of votes, I’ll check if their votes are greater than the half of total voters:

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // Check each candidate's votes
    for (int i = 0; i < candidate_count; i++)
    {
        // If a candidate has more than half of the votes, they are the winner
        if (candidates[i].votes > voter_count / 2)
        {
            printf("%s\n", candidates[i].name);
            return true;
        }
    }

    // No winner found
    return false;
}

Find min

The function should return the minimum vote total for any candidate who is still in the election. For that, I’ll loop through the candidates to find the one who is both still in the election and has the fewest number of votes.

And my first instinct was to write this:

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = 0;

    // Loop through each candidate to find the one with the fewest votes and is
    // still in the election
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated &&
            (candidates[i].votes < min || min == 0))
        {
            min = candidates[i].votes;
        }
    }

    return min;
}

It’s only later I realised that this code has a potential flaw that might lead to a wrong outcome in certain cases. Can you guess what it is?

The potential issue in that version is related to the initialisation of the min variable with a value of 0. In some scenarios, the condition //(candidates[i].votes < min || min == 0)// will always be true for the first candidate in the loop, and //min// will be updated to the candidate's votes. This would result in the function returning 0, even though it's not the minimum number of votes any remaining candidate has.

This is pretty obvious now – the min variable should be initialised with a voter_count + 1:

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = voter_count + 1;

    // Loop through each candidate to find the one with the fewest votes and is
    // still in the election
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated && candidates[i].votes < min)
        {
            min = candidates[i].votes;
        }
    }

    return min;
}

Here’s an example to compare both versions of the function:

Suppose we have three candidates, and initially, they have the following votes: Candidate A (2 votes), Candidate B (3 votes), Candidate C (1 vote). After some eliminations, only Candidate A and Candidate B remain in the election.

• In version 1, min is initialised to 0, and the condition (candidates[i].votes < min || min == 0) will be true for the first candidate (Candidate A) with 2 votes, updating min to 2. Therefore, the function would incorrectly return 2 as the minimum number of votes.
• In version 2, min is initialised to a value greater than the maximum possible votes (voter_count + 1), and the correct minimum number of votes (1 in this case) will be returned. A pretty subtle, but important difference!

The rest of the functions are pretty straightforward, so I’ll just put my final code for each function:

Is tie

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    // Loop through each candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // Check if the candidate is still in the election and has a different
        // number of votes than the minimum
        if (!candidates[i].eliminated && candidates[i].votes != min)
        {
            // Not a tie as at least one candidate has a different number of
            // votes
            return false;
        }
    }

    // All remaining candidates have the same number of votes, it's a tie
    return true;
}

Eliminate

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated && candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }
}