Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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];
- bool circle;
- // 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);
- // check the graph making cycle
- bool iscircle();
- bool gointo(bool visited[], int to);
- 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;
- }
- // Update ranks given a new vote
- bool vote(int rank, string name, int ranks[])
- {
- for (int k = 0; k < candidate_count; k++)
- {
- if (!strcmp(name, candidates[k]))
- {
- ranks[rank] = k;
- return true;
- }
- }
- return false;
- }
- // Update preferences given one voter's ranks
- void record_preferences(int ranks[])
- {
- for (int m = 0; m < candidate_count; m++)
- {
- for (int n = 0; n < candidate_count; n++)
- {
- if (m < n)
- {
- ++preferences[ranks[m]][ranks[n]];
- }
- }
- }
- return;
- }
- // Record pairs of candidates where one is preferred over the other
- void add_pairs(void)
- {
- for (int i = 0; i < candidate_count; i++)
- {
- for (int j = 0; j < candidate_count; j++)
- {
- if (preferences[i][j] == 0)
- {
- continue;
- }
- if (preferences[i][j] > preferences[j][i])
- {
- pairs[pair_count].winner = i;
- pairs[pair_count].loser = j;
- pair_count++;
- }
- }
- }
- return;
- }
- // Sort pairs in decreasing order by strength of victory
- void sort_pairs(void)
- {
- for (int i = 0; i < pair_count; i++)
- {
- for (int j = 0; j < pair_count; j++)
- {
- if (pairs[i].winner < pairs[j].winner)
- {
- pair tmp = pairs[i];
- pairs[i] = pairs[j];
- pairs[j] = tmp;
- }
- }
- }
- return;
- }
- // Lock pairs into the candidate graph in order, without creating cycles
- void lock_pairs(void)
- {
- for (int k = 0; k < pair_count; k++)
- {
- for (int i = 0; i < candidate_count; i++)
- {
- //lock pairs strarting with pair have the biggest winner
- if (pairs[k].winner == i)
- {
- locked[pairs[k].winner][pairs[k].loser] = true;
- }
- //check if creates a cycle then unlock the pair
- if (check_cycle(pairs[k].winner,pairs[k].loser))
- {
- locked[pairs[k].winner][pairs[k].loser] = false;
- }
- }
- }
- return;
- }
- // Print the winner of the election
- void print_winner(void)
- {
- // TODO
- for (int i = 0, k = 0; i < candidate_count; i++)
- {
- if (k == candidate_count)
- {
- printf("%s\n", candidates[i]);
- }
- for (int j = 0; j < candidate_count; j++)
- {
- if (!locked[j][i])
- {
- ++k;
- }
- }
- }
- return;
- }
- bool iscircle()
- {
- bool visited[candidate_count];
- circle = false;
- return gointo(visited, 0);
- }
- bool gointo(bool visited[], int to)
- {
- // start trip form one node in the graph check if it have been visited ( Cycle )
- visited[to] = true;
- for (int n = 0; n < candidate_count; n++)
- {
- if (locked[to][n])
- {
- if (visited[n])
- {
- circle = true;
- }
- else
- {
- gointo(visited, n);
- }
- break;
- }
- }
- return circle;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement