0

I completed Runoff with 100% pass in check50 but when i do my own tests i get wrong winners. I checked everything to the best of my abilities but i just can't find the problem and it's driving me insane. What am i missing here?

Disclaimer: Sorry i'm dropping the whole thing in here and please if you did not complete the problem try to do it on your own and don't just copy from others so you can really learn.

My test:

./runoff 1 2 3

Number of voters: 5

1 2 3 - 1 3 2 - 2 1 3 - 3 2 1 - 3 1 2 > winner should be "1" but i'm getting "1 2 3"

I`m not saying their tests are wrong but how can this be?

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <math.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++)
    {
        int j = 0;
        while (candidates[preferences[i][j]].eliminated == true)
        {
            j++;
        }

        candidates[preferences[i][j]].votes++;
    }

    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{

    int majority = round((voter_count / 2) + 1);

    for (int i = 0; i < voter_count; i++)
    {

        if (candidates[i].votes >= majority)
        {
            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 few = 0;

    for (int i = 0; i < candidate_count; i++)
    {

        if (candidates[i].eliminated == false)
        {

            for (int j = 1; j < candidate_count; j++)
            {

                if (candidates[i].votes < candidates[j].votes)
                {
                    candidates[j].votes = candidates[i].votes;
                }
            }

        few = candidates[i].votes;

        }
    }

    return few;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{

    bool check;

    for (int i = 0; i < candidate_count; i++)
    {

        if (candidates[i].eliminated == false)
        {

            if (candidates[i].votes == min)
            {
                check = true;
            }

            else
            {
                check = false;
            }
        }
    }

    return check;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{

    for (int i = 0; i < candidate_count; i++)
    {

        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }

    return;
}
2

Interesting that check50 doesn't pick that up!

There is a problem in find_min. That function should have no side-effects, ie should not change any data, only report a result. This line candidates[j].votes = candidates[i].votes; has the potential to change a candidates vote count; that would be bad.

There may be other problems in the code, but this jumps off the page.

  • Oh yes, exactly. My biggest worry wasn't my mistake but the fact that some of their tests give false positives. Thank you for your time, great help. I bow! – VanG Oct 13 '20 at 13:36
0

You have a problem with is_tie, your check value gets overwritten each time the loop goes. You should just return false when you know it isn't a tie and at the end return true if it it didn't end all ready .

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .