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:
- 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;
- 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
