1

I have checked my code with a few example and all of them returned the right answer. But when using check50, it tells me that my sort_pairs does not work correctly. Please help me :)!

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

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
    int win;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

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

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

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // ranks[i] is voter's ith preference
        int ranks[candidate_count];

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

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

//sort pairs by their winning strength
void sort(int s, int e, pair num[], pair tmp[])
{
    if (e <= s)
    return;

        int mid =(s + e)/2;
        sort(s, mid, num, tmp);
        sort(mid + 1, e, num, tmp);

    int l = s, r = mid + 1;

    for (int i = s; i <= e; i++)
    {
        if (l == mid + 1)
        {
            tmp[i] = num[r];
            r ++;
        }
        else if (r == e + 1)
        {
            tmp[i] = num[l];
            l ++;
        }
        else if (num[l].win > num[r].win)
        {
            tmp[i] = num[l];
            l ++;
        }
        else
        {
            tmp[i] = num[r];
            r ++;
        }
    }

    for (int i = s; i < e; i ++)
    {
        num[i] = tmp[i];
        printf("%i %i\n", i, num[i].win);
    }
}

//checking will creating this edge make a cycle
bool loopcheck(int a, int b)
{
    if (locked[b][a] == true)
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[i][a] == true)
            return loopcheck(i, b);
    }
    return false;
}

//checking wether or not this candidate is a source
bool checkp(int i)
{
    for (int j = 0; j < candidate_count; j ++)
    {
        if (locked[j][i] != 0)
            return false;
    }
    return true;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
     for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for (int i = 0; i < candidate_count; i ++)
    {
        for (int j = i + 1; j < candidate_count; j ++)
        {
            preferences[ranks[i]][ranks[j]] ++;
        }
    }
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for (int i = 0; i < candidate_count - 1; i++)
    {
        for (int j = i + 1; j < candidate_count; j ++)
        {
            if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pairs[pair_count].win = preferences[j][i];
                win[pair_count] = pairs[pair_count].win;
                pair_count ++;
            }
            else if (preferences[j][i] < preferences[i][j])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pairs[pair_count].win = preferences[i][j];
                win[pair_count] = pairs[pair_count].win;
                pair_count ++;
            }
        }
    }
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    pair tmp[pair_count];
    sort(0, pair_count, pairs, tmp);
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
        for ( int j = 0; j < pair_count; j ++)
        {
            if (!loopcheck(pairs[j].winner, pairs[j].loser))
                locked[pairs[j].winner][pairs[j].loser] = true;
        }
}

// Print the winner of the election
void print_winner(void)
{
    for (int i = 0; i < candidate_count; i ++)
    {
        if (checkp(i))
        {
            printf("%s\n", candidates[i]);
        }
    }
}


1

As per the problem set directions (reproduced below), you are not supposed to modify anything in the code except for the functions you are completing. You have modified the pairs construct with a new variable called win. This isn't allowed and could possibly be the source of your issues.

You should not modify anything else in tideman.c other than the implementations of the vote, record_preferences, add_pairs, sort_pairs, lock_pairs, and print_winner functions (and the inclusion of additional header files, if you’d like). You are permitted to add additional functions to tideman.c, so long as you do not change the declarations of any of the existing functions.

You must log in to answer this question.

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