0

I am working on Tideman today, and I am stuck on the "sort_array" function. The output my function produces is the one I expect but he 'check50' send me this ":( sort_pairs sorts pairs of candidates by margin of victory - sort_pairs did not correctly sort pairs". I probably need someone else view on it.

Here is what I've done:

  1. I modified the struct 'pair' to include the element 'diff' inside, so it stores 'winner', 'loser' and 'diff' (which is the difference between the winner and the loser's number votes. ex: A got 4 votes, B got 1 vote, 'diff' = 4-1 = 3)
typedef struct
{
    int winner;
    int loser;
    int diff;
}
pair;
  1. Here is my 'sort_pairs' function:
void sort_pairs(void)
{   
    // temporary array of pairs
    pair temp[pair_count];

    // to store the max diff in the array 'pairs'
    int maxNumber = 0;

    // to store the position of the max diff in the array 'pairs'
    int maxPosition = 0;
    
    // point to the "temp" array position to add the next element
    int arrayPosCounter = 0; 


    for(int y = 0; y < pair_count; y++)
    {
        for(int i = 0; i < pair_count; i++)
        {
            if(pairs[i].diff > maxNumber)
            {
                maxNumber = pairs[i].diff;
                maxPosition = i;
            }
        }
        // stores the 'pair' array element with the max diff in my temporary array
        temp[arrayPosCounter] = pairs[maxPosition];

        // add 1 to store the next element in the next temp array slot
        arrayPosCounter ++;

        // set the added pair 'diff' to -1, so it won't be added a second time to the temp array 
        pairs[maxPosition].diff = - 1;

        //reset those two variables for the next round
        maxPosition = 0;
        maxNumber = 0;
    }
    
    // copy the elements of array 'temp' in array 'pairs'
    for (int i = 0; i < pair_count; i++)
    {
        pairs[i] = temp[i];
    }
    
    return ;
}

I did some test: Input:

Votes:

string vote1[5] = {"a","b","c","d","e"};
string vote2[5] = {"b","c","a","d","e"};
string vote3[5] = {"e","b","c","a","d"};
string vote4[5] = {"b","a","c","e","d"};
string vote5[5] = {"a","b","d","c","e"};

Preferences:

{0,2,3,5,4}
{3,0,5,5,4}
{2,0,0,4,4}
{0,0,1,0,3}
{1,1,1,2,0}

Element in my unsorted array:

winner;loser;diff
a;c;1
a;d;5
a;e;3
b;a;1
b;c;5
b;d;5
b;e;3
c;d;3
c;e;3
d;e;1

output of my 'sort_pairs' function (descending order):

winner;loser;diff
a;d;5
b;c;5
b;d;5
a;e;3
b;e;3
c;d;3
c;e;3
a;c;1
a;b;1
d;e;1

The result seems right to me, but I am probably missing something. Someone has an idea?

Using this thread: Tideman sort_pairs function , I thought it might be due to my modification of the "pair" struct; so I tried this messy but working solution, just as a test. It produces exactly the same output as above.

Explanation: I added a new struct "pair_diff" containing "winner, loser, diff" to keep the original "pair" struct as it was. It seems that even when the array "pairs[]" remain as an instance of struct "pair" "check50" doesn't accept it. That's why I am worry that the problem is the logic, not even a structure one.

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.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;
}
pair;

typedef struct
{
    int winner;
    int loser;
    int diff;
}
pair_diff;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];
pair_diff pairs_diff[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[])
{
    string vote1[5] = {"a","b","c","d","e"};
    string vote2[5] = {"b","c","a","d","e"};
    string vote3[5] = {"e","b","c","a","d"};
    string vote4[5] = {"b","a","c","e","d"};
    string vote5[5] = {"a","b","d","c","e"};
    
    int winsA[5] = {0,2,3,5,4};
    int winsB[5] = {3,0,5,5,4};
    int winsC[5] = {2,0,0,4,4};
    int winsD[5] = {0,0,1,0,3};
    int winsE[5] = {1,1,1,2,0};
    // 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;
    printf("Number of candidates: %i \n", candidate_count);
    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();
    
    //test
    for(int i = 0; i < pair_count; i++)
    {
        printf(" Pair order: %s wins over %s by %i victories, \n",  candidates[pairs[i].winner], candidates[pairs[i].loser], pairs_diff[i].diff);
    }
    
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{   
    // initialisation
    bool output = false;
    
    // for the number of participant
    for( int i = 0; i < candidate_count; i++)
    {   
        //printf("Is in the candidate list: %i \n", strcmp(candidates[i], name));
        // if the name is equal the the index of a candidate in the candidate list
        if(strcmp(candidates[i], name) == 0)
        {
            //the x element of the array "ranks" is equal to the candidate position in the candidates "array"
            ranks[rank] = i;
            output = true;
            break;
        }
    }
    
    return output;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // i equal the position in the ranking, rank[i] equal the candidate number
    for(int i = 0; i < candidate_count; i++)
    {
        for ( int y = i+1; y < candidate_count; y++)
        {
            preferences[ranks[i]][ranks[y]]++;
            //printf("Candidate nb %s wins over candidate %s: %i times, %i times \n", candidates[ranks[i]], candidates[ranks[y]], preferences[ranks[i]][ranks[y]], preferences[ranks[y]][ranks[i]] );
        }
    }
    
    // TODO
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    
    // first reset the pairs
    int counter = 0;
    for(int i = 0; i < candidate_count; i++)
    {
        for ( int y = 0; y < candidate_count; y++)
        {
            if(i != y )
            {
                if (preferences[i][y] - preferences[y][i] > 0)
                {
                    pairs[counter].winner = i;
                    pairs[counter].loser = y;
                    //pairs[counter].diff = abs(preferences[i][y] - preferences[y][i]);
                    pairs_diff[counter].winner = i;
                    pairs_diff[counter].loser = y;
                    pairs_diff[counter].diff = abs(preferences[i][y] - preferences[y][i]);
                    //printf("winner %i, ", pairs[counter].winner);
                    //printf("loser %i, ", pairs[counter].loser);
                    //printf("diff %i \n", pairs[counter].diff);
                    counter++;
                    
                }
            }
        }
    }
    pair_count = counter;
    printf("There are %i results in this the array 'pairs'\n", counter);
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    pair_diff temp[pair_count];
    int maxPosition = 0;
    int maxNumber = 0;
    int arrayPosCounter = 0; 
    for(int y = 0; y < pair_count; y++)
    {
        for(int i = 0; i < pair_count; i++)
        {
            if(pairs_diff[i].diff > maxNumber)
            {
                maxNumber = pairs_diff[i].diff;
                maxPosition = i;
            }
        }
        temp[arrayPosCounter] = pairs_diff[maxPosition];
        arrayPosCounter ++;
        pairs_diff[maxPosition].diff = - 1;
        maxPosition = 0;
        maxNumber = 0;
    }
    
    for (int i = 0; i < pair_count; i++)
    {
        pairs[i].winner = temp[i].winner;
        pairs[i].loser = temp[i].loser;
        pairs_diff[i] = temp[i];
    }
    
    return ;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // TODO
    return;
} 

Someone has an idea?

Thank you all, Cheers, Pierre

0

I'm not sure that you can mess with the pair struct, but I'm sure that you can find a way to do what you are doing without needing to add anything in the struct. You can do it with just 2 nested for-loops (and for habit sake use "i" and "j" in those variables as it's considered standard. And when you have done your operations in those variables (and you can declare the "diff" in a local variable if you just think a bit about it) - you check the result with an if statement! Hope it helps.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

0

I think I do have a similar problem. Did you find a solution?

Link to my problem in here: CS50 Tideman : Sort Pairs problem - check50 automatic test fails, but output seems correct

You must log in to answer this question.

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