Skip to content

Instantly share code, notes, and snippets.

@HasanMukit
Created October 19, 2020 09:46
Show Gist options
  • Save HasanMukit/8dc6c869bdd797c6822ce28e9632b174 to your computer and use it in GitHub Desktop.
Save HasanMukit/8dc6c869bdd797c6822ce28e9632b174 to your computer and use it in GitHub Desktop.
#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;
}
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);
void checkPair(int testW, int testL, int l);
int main()
{
// Check for invalid usage
// if (argc < 2)
// {
// printf("Usage: tideman [candidate ...]\n");
// return 1;
// }
// Populate array of candidates
string inputCandidate[] = { "Alice", "Bob", "Charlie"}; //new line
candidate_count = 3; //code changed
// 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] = inputCandidate[i]; //code changed
printf("%s ", candidates[i]);
}
printf("\n");
// 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;
preferences[i][j] = 0;
}
}
pair_count = 0;
int voter_count = 5; // code changed
string voteInput[5][3] = { { "Alice", "Charlie", "Bob"},
{ "Alice", "Bob", "Charlie"},
{ "Bob", "Charlie", "Alice"},
{ "Bob", "Charlie", "Alice"},
{ "Charlie", "Alice", "Bob"}};
// 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 = voteInput[i][j];
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;
}
// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
// TODO
for (int i = 0; i < candidate_count; i++)
{
if(strcmp(name, candidates[i]) == 0)
{
ranks[rank] = i;
printf("Rank %i: %s\n", rank, name);
return true;
}
}
return false;
}
// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
// TODO
for (int i =0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++ )
{
preferences[ranks[i]][ranks[j]]++;
}
}
for (int i =0; i < candidate_count; i++)
{
for (int j = 0; j < candidate_count; j++ )
{
printf("%i ",preferences[i][j]);
}
printf("\n");
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
pair_count = 0;
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 = i;
pairs[pair_count].loser = j;
pair_count++;
printf("winner: %s\n", candidates[i]);
printf("loser: %s\n", candidates[j]);
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[pair_count].winner = j;
pairs[pair_count].loser = i;
pair_count++;
printf("winner: %s\n", candidates[j]);
printf("loser: %s\n", candidates[i]);
}
}
}
printf("%i\n", pair_count);
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
pair temp;
for (int i = 0; i < pair_count; i++)
{
int flag = 0;
for (int j = 0; j < pair_count - i -1; j++)
{
int marginCurr = preferences[pairs[j].winner][pairs[j].loser];
int marginNext = preferences[pairs[j + 1].winner][pairs[j + 1].loser];
if ( marginCurr < marginNext )
{
temp = pairs[j];
pairs[j] = pairs[j + 1];
pairs[j + 1] = temp;
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
for (int i = 0; i < pair_count; i++)
{
printf("Rank %i:\n", i);
printf("W: %s L: %s\n", candidates[pairs[i].winner],candidates[pairs[i].loser]);
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
int winner = pairs[i].winner;
int loser = pairs[i].loser;
checkPair(winner, loser, loser);
}
for (int i = 0; i < candidate_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
if(locked[i][j])
{
printf("1 ");
}
else
{
printf("0 ");
}
}
printf("\n");
}
return;
}
// Print the winner of the election
void print_winner(void)
{
// TODO
for (int i = 0; i < candidate_count; i++)
{
bool flag = true;
for (int j = 0; j < candidate_count; j++)
{
if(locked[j][i])
{
flag = false;
}
}
if(flag)
{
printf("%s\n", candidates[i]);
}
}
return;
}
void checkPair(int testW, int testL, int l)
{
int w = l;
bool flag = true;
for (int newL = 0; newL < candidate_count; newL++)
{
if(locked[w][newL])
{
if(testW == newL)
{
return;
}
else if (newL != testL)
{
checkPair(testW, testL, newL);
}
}
if(w == testL)
{
locked[testW][testL] = true;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment