CS50 pset3 Check50 is working but when I test my code there is something wrong

Question

Writing this code I'have always checked my program with check50 and these are my results:

:) runoff.c exists
:) runoff compiles
:) vote returns true when given name of candidate
:) vote returns false when given name of invalid candidate
:) vote correctly sets first preference for first voter
:) vote correctly sets third preference for second voter
:) vote correctly sets all preferences for voter
:) tabulate counts votes when all candidates remain in election
:) tabulate counts votes when one candidate is eliminated
:) tabulate counts votes when multiple candidates are eliminated
:) tabulate handles multiple rounds of preferences
:) print_winner prints name when someone has a majority
:) print_winner returns true when someone has a majority
:) print_winner returns false when nobody has a majority
:) print_winner returns false when leader has exactly 50% of vote
:) find_min returns minimum number of votes for candidate
:) find_min returns minimum when all candidates are tied
:) find_min ignores eliminated candidates
:) is_tie returns true when election is tied
:) is_tie returns false when election is not tied
:) is_tie returns false when only some of the candidates are tied
:) is_tie detects tie after some candidates have been eliminated
:) eliminate eliminates candidate in last place
:) eliminate eliminates multiple candidates in tie for last
:) eliminate eliminates candidates after some already eliminated

It seems to work, but when I test it with the cs50 examples, the outputs are different. What should I do?

#include <cs50.h>
#include <stdio.h>
#include <string.h>

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

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

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

// Array of candidates
candidate candidates[MAX_CANDIDATES];

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

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES)
    {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS)
    {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++)
    {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            // Record vote, unless it's invalid
            if (!vote(i, j, name))
            {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
        {
            break;
        }

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie)
        {
            for (int i = 0; i < candidate_count; i++)
            {
                if (!candidates[i].eliminated)
                {
                    printf("%s\n", candidates[i].name);
                }
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
        {
            candidates[i].votes = 0;
        }
    }
    return 0;
}

// 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)
        {
            preferences[voter][rank] = i;
            return true;
        }
        
     }
    
    return false;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    for (int i = 0; i < voter_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            if (! candidates[preferences[i][j]].eliminated)
            {
                candidates[preferences[i][j]].votes++;
                break;
            }
        }
    }
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > voter_count / 2)
        {
            printf("%s\n", candidates[i].name);
            return true;
        }
    }
    
    return false;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = 0;
    int x;
    int y;
    for (int i = 0; i < candidate_count - 1; i++) 
    {
        for (int j = i + 1; j < candidate_count; j++) 
        {
            if (candidates[j].votes < candidates[i].votes) 
            {
                // swapping elements
                x = candidates[i].eliminated;
                candidates[i].eliminated = candidates[j].eliminated;
                candidates[j].eliminated = x;
                
                y = candidates[i].votes;
                candidates[i].votes = candidates[j].votes;
                candidates[j].votes = y;
            }
        }
    }
    
   for (int k = 0; k < candidate_count; k++)
   {
       if (!candidates[k].eliminated)
       {
           min = candidates[k].votes;
           break;
       }
   }
   
   return min;
}


// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int ties = 0;
    int elim = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated)
        {
            if (candidates[i].votes == min)
            {
                ties++;
            }
        }
    }
    
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated)
        {
            elim++;
        }
    }
    
    if (ties == candidate_count - elim)
    {
        return true;
    }
   
    return false;
}

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

for example by using these inputs :

./runoff Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Bob
Rank 3: Charlie

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Alice
Rank 3: Charlie

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

the program should returns Alice, but instead it returns Bob, what's wrong with my code?

Answer 1

The bit swapping candidates in find_min doesn't swap names.

It's a problem:

with your example input, before find_min() in the first runoff candidates[] are in the following state: Alice,2;Bob,2;Charlie,1 (there is false everywhere too at this point, I omitted it here) and find_min() changes it to Alice,1;Bob2;Charlie,2 – see what's wrong here? Charlie committed election fraud and gets to next runoff.

The program goes on to eliminate Alice and counts votes again, getting 3 votes for Bob and 2 for Charlie (it works pretty much as expected from there).

The bug occurs during swapping when sorting.

EDIT:

When you swap the candidates[i] with candidates[j] (btw, you can do it with tmp candidate in 1 step instead of 3), it messes with the preferences of the voters.

For example: the first voter is voting on A,B,C, so his preferences are nr0,nr1,nr2 (using indexes from candidates[]). However, after you swap A and C/nr 0 and nr 2 (as mentioned in my original answer), the preferences of the first voter didn't change, the are still: nr0, nr1,nr2, but now nr0 is Charlie, not Annie. So it's like the first voter voted C,B,A not A,B,C.

Charlie doesn't count, as he is eliminated by now so it's nr1 (Bob) that gets the vote of the first voter. Two good solutions are to change preferences accordingly during swap, or don't swap at all (which I like more).

First solution:

int find_min(void)
{
    int min = 0;
    candidate tmp;
    for (int i = 0; i < candidate_count - 1; i++) 
    {
        for (int j = i + 1; j < candidate_count; j++) 
        {
            if (candidates[j].votes < candidates[i].votes) 
            {
                // swapping candidates
                tmp = candidates[i];
                candidates[i] = candidates[j];
                candidates[j] = tmp;
                
                //adjusting preferences
                for(int a = 0; a < voter_count; a++) {
                    for(int b = 0; b < candidate_count; b++) {
                        if(preferences[a][b] == i) {
                            prefereences[a][b] = j;
                        }
                        else if (preferences[a][b] == j) {
                            prefereences[a][b] = i;
                        }
                    }
                }
                
            }
        }
    }
    
   for (int k = 0; k < candidate_count; k++)
   {
       if (!candidates[k].eliminated)
       {
           min = candidates[k].votes;
           break;
       }
   }
   
   return min;
}

Second solution (in my opinion more elegant, and faster):

int find_min(void)
{
    int min = voter_count;//the max poss value
    for (int i = 0; i < candidate_count - 1; i++) 
    {
        if (!candidates[i].eliminated) {
            if (candidates[i].votes < min) {
                min = candidates[i].votes;
            }
        }
    }
    return min;
}