In this problem set, we have to write a code that runs the Tideman election as shown in below code snippet.
$ ./tideman Alice Bob Charlie Number of voters: 5 Rank 1: Alice Rank 2: Charlie Rank 3: Bob Rank 1: Alice Rank 2: Charlie Rank 3: Bob Rank 1: Bob Rank 2: Charlie Rank 3: Alice Rank 1: Bob Rank 2: Charlie Rank 3: Alice Rank 1: Charlie Rank 2: Alice Rank 3: Bob Charlie
In the previous posts, I gave you the solution to the cs50 psets 3 plurality problem, and cs50 psets 3 runoff problem.
So the plurality election system and runoff election system have their own advantages and disadvantages. Now, let’s see what is the Tideman election system.
Tideman Election System
Tideman method is also known as the Ranked pairs method. This system was developed in 1987 by Nicolaus Tideman. This system selects a single winner using votes that express preferences. This method can also be used to create a sorted list of winners.
So, let’s get back to the problem set, an initial code is given to us.
Solution
1. The vote function
// 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;
return true;
}
}
return false;
}
2. The record_preferences function
// 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]]++;
}
}
return;
}
3. The add_pairs function
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
for (int i = 0; i < candidate_count; 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++;
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[pair_count].winner = j;
pairs[pair_count].loser = i;
pair_count++;
}
}
}
return;
}
4. The sort_pairs function
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
int max = i;
for (int j = i; j < pair_count; j++)
{
if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[max].winner][pairs[max].loser])
{
max = j;
}
}
pair temp = pairs[i];
pairs[i] = pairs[max];
pairs[max] = temp;
}
return;
}
5. The cycle function
// Check for cycle by checking arrow coming into each candidate
bool cycle(int cycle_end, int cycle_start)
{
// Return true if there is a cycle
if (cycle_end == cycle_start)
{
return true;
}
// Loop through all the candidates
for (int i = 0; i < candidate_count; i++)
{
if (locked[cycle_end][i])
{
if (cycle(i, cycle_start))
{
return true;
}
}
}
return false;
}
6. The lock_pairs function
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
if (!cycle(pairs[i].loser, pairs[i].winner))
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
return;
}
7. The print_winner function
// Print the winner of the election
void print_winner(void)
{
// TODO
for (int i = 0; i < candidate_count; i++)
{
bool loser = false;
for (int j = 0; j < candidate_count; j++)
{
if (locked[j][i])
{
loser = true;
break;
}
}
if (loser)
{
continue;
}
if (!loser)
{
printf("%s\n", candidates[i]);
}
}
return;
}
Full Code
here is the full code that includes all the functions,
#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);
bool cycle(int cycle_end, int cycle_start);
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[])
{
// TODO
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[])
{
// TODO
for (int i = 0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
for (int i = 0; i < candidate_count; 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++;
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[pair_count].winner = j;
pairs[pair_count].loser = i;
pair_count++;
}
}
}
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
int max = i;
for (int j = i; j < pair_count; j++)
{
if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[max].winner][pairs[max].loser])
{
max = j;
}
}
pair temp = pairs[i];
pairs[i] = pairs[max];
pairs[max] = temp;
}
return;
}
// Check for cycle by checking arrow coming into each candidate
bool cycle(int cycle_end, int cycle_start)
{
// Return true if there is a cycle
if (cycle_end == cycle_start)
{
return true;
}
// Loop through all the candidates
for (int i = 0; i < candidate_count; i++)
{
if (locked[cycle_end][i])
{
if (cycle(i, cycle_start))
{
return true;
}
}
}
return false;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
if (!cycle(pairs[i].loser, pairs[i].winner))
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
return;
}
// Print the winner of the election
void print_winner(void)
{
// TODO
for (int i = 0; i < candidate_count; i++)
{
bool loser = false;
for (int j = 0; j < candidate_count; j++)
{
if (locked[j][i])
{
loser = true;
break;
}
}
if (loser)
{
continue;
}
if (!loser)
{
printf("%s\n", candidates[i]);
}
}
return;
}
Hope this helps you, Good luck!
1 thought on “The Solution to CS50 psets 3 Tideman Problem (2022)”
Leave a comment sharing your knowledge