In the third week of the Computer Science CS50 (Harvard) course, it is proposed to do homework in Problem Set 3 called runoff.c – you need to write a program code that does not just calculate which candidate received the most votes, like last time, in the runoff program you need to implement voting until more than 50% of the votes of all voters are collected.
The winner will be announced only when one of the candidates receives more than half of the votes. To do this, each voter ranks all candidates from highest preference (rank 1) to least preference (last rank). Next, the sum of votes in the first round (rank 1) is calculated. If one of the candidates receives more than 50% of the votes at this stage, he is declared the winner.
If there is no winner in the first round, then you need to find the candidate who received the least number of votes and remove him from the list of candidates so that only the remaining candidates participate in the counting of votes in the next round. And so on until there is a winner. If it turns out that everyone in the election has the same number of votes, then a draw is declared and they are all winners.
Igroglaz’s first solution. The initial tests passed, but cs50 showed a lot of jambs:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9
// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES]; // предпочтения
// Candidates have name, vote count, eliminated status
typedef struct
{
char name[1000];
int votes;
bool eliminated;
}
candidate;
// Array of candidates
candidate candidates[MAX_CANDIDATES];
// Numbers of voters and candidates
int voter_count;
int candidate_count;
// Function prototypes
bool vote(int voter, int rank, char *name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);
int main(int argc, char *argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
strcpy (candidates[i].name, argv[i + 1]);
candidates[i].votes = 0;
candidates[i].eliminated = false;
}
printf("Number of voters: ");
scanf("%d", &voter_count);
while (getchar() != '\n') ; // clear buffer
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters is %i\n", MAX_VOTERS);
return 3;
}
// Keep querying for votes
for (int i = 0; i < voter_count; i++)
{
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
char name[1000]; // there user enters name of candidate when voting
printf("Rank %i: ", j + 1);
scanf("%s", name);
// Record vote, unless it's invalid
if (!vote(i, j, name))
{
printf("Invalid vote.\n");
return 4;
}
}
printf("\n");
}
// Keep holding runoffs until winner exists
while (true)
{
// Calculate votes given remaining candidates
tabulate();
// Check if election has been won
bool won = print_winner();
if (won)
{
break;
}
// Eliminate last-place candidates
int min = find_min();
bool tie = is_tie(min);
// If tie, everyone wins
if (tie)
{
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
printf("%s\n", candidates[i].name);
}
}
break;
}
// Eliminate anyone with minimum number of votes
eliminate(min);
// Reset vote counts back to zero
for (int i = 0; i < candidate_count; i++)
{
candidates[i].votes = 0;
}
}
getchar();
getchar();
return 0;
}
// Record preference if vote is valid
bool vote(int voter, int rank, char *name)
{
for (int i = 0; i < candidate_count; i++)
{
if (!strcmp(name, candidates[i].name))
{
preferences[voter][rank] = i;
//debug printf("%c - voter:%d rank:%d pref:%d\n", *name, voter, rank, preferences[voter][rank]);
return true;
}
}
return false;
}
// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
// go through all voters and check whom they give highest preference
// 1) take voter
// 2) find this voter 'rank 0' preffered candidate
// 3) increase votes number of this candidate
for (int i = 0; i < voter_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
if (preferences[i][0] == j && !candidates[j].eliminated)
{
candidates[j].votes++;
break;
}
}
}
}
//dubug printf("%c - votes:%d\n", *candidates[j].name, candidates[j].votes);
// Print the winner of the election, if there is one
bool print_winner(void)
{
// 1) go through candidates array and check who got highest vote
// 2) if there is a candidate who > 1/2 votes - he wins
int top = 0; // candidate who has most votes
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes > top)
top = i;
}
if (candidates[top].votes > (voter_count / 2))
{
printf("Winner: %s", candidates[top].name);
return true;
}
else
return false;
}
// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
// go through all candidates and find out who has least votes
// 1) take 1st candidate and store it's number of votes
// 2) compare 1st candidate with further candidates to find min
int first = 0; // flag which indicate first possible 'min' candidate
int min;
for (int i = 1; i < candidate_count; i++)
{
if (!first && !candidates[i].eliminated)
{
first = 1; // 1st min candidate found, so check flag
min = candidates[i].votes;
}
if (first && !candidates[i].eliminated && candidates[i].votes < min)
{
min = candidates[i].votes;
return min;
}
}
return 0;
}
// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
// find out is there candidates with the same vote number
// 1) go through candidates
// 2) if candidate eliminated or got 'min' votes - ignore it
// 3) if all 'active' candidates got same number of votes - tie
// a) compare votes numbers with == between each other.
// b) if even one isn't the same - false
int cmpvote = 0;
for (int i = 1; i < candidate_count; i++)
{
if (!cmpvote && !candidates[i].eliminated && (candidates[i].votes != min))
cmpvote = candidates[i].votes; // 1st valid candidate found
if (cmpvote && !(candidates[i].votes == cmpvote))
return false;
}
return true;
}
// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
// check which candidate got 'min' and eliminate him
for (int i = 1; i < candidate_count; i++)
{
if (candidates[i].votes == min)
candidates[i].eliminated = true;
}
return;
}
The second solution from Igroglaz, corrected:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// I prefer to write code with vanilla C libraries,
// but this time I had to include cs50.h cause without it this program fails to compile for 'check50'
#include <cs50.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9
// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES]; // предпочтения
// Candidates have name, vote count, eliminated status
typedef struct
{
string name; // had to change it from 'char name[1000]' to 'string' to make 'check50' work...
int votes;
bool eliminated;
}
candidate;
// Array of candidates
candidate candidates[MAX_CANDIDATES];
// Numbers of voters and candidates
int voter_count;
int candidate_count;
// Function prototypes
bool vote(int voter, int rank, char *name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);
int main(int argc, char *argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
strcpy (candidates[i].name, argv[i + 1]);
candidates[i].votes = 0;
candidates[i].eliminated = false;
}
printf("Number of voters: ");
scanf("%d", &voter_count);
while (getchar() != '\n') ; // clear buffer
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters is %i\n", MAX_VOTERS);
return 3;
}
// Keep querying for votes
for (int i = 0; i < voter_count; i++)
{
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
char name[1000]; // there user enters name of candidate when voting
printf("Rank %i: ", j + 1);
scanf("%s", name);
// Record vote, unless it's invalid
if (!vote(i, j, name))
{
printf("Invalid vote.\n");
return 4;
}
}
printf("\n");
}
// Keep holding runoffs until winner exists
while (true)
{
// Calculate votes given remaining candidates
tabulate();
// Check if election has been won
bool won = print_winner();
if (won)
{
break;
}
// Eliminate last-place candidates
int min = find_min();
bool tie = is_tie(min);
// If tie, everyone wins
if (tie)
{
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
printf("%s\n", candidates[i].name);
}
}
break;
}
// Eliminate anyone with minimum number of votes
eliminate(min);
// Reset vote counts back to zero
for (int i = 0; i < candidate_count; i++)
{
candidates[i].votes = 0;
}
}
return 0;
}
// Record preference if vote is valid
bool vote(int voter, int rank, char *name)
{
for (int i = 0; i < candidate_count; i++)
{
if (!strcmp(name, candidates[i].name))
{
preferences[voter][rank] = i;
//debug printf("%c - voter:%d rank:%d pref:%d\n", *name, voter, rank, preferences[voter][rank]);
return true;
}
}
return false;
}
// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
// go through all voters and check whom they give highest preference
// 1) take voter
// 2) find this voter 'rank 0' preffered candidate
// 3) increase votes number of this candidate
for (int voter = 0; voter < voter_count; voter++)
{
// 'flag' - to show that next valid candidate after elimineted one is found
// and it's time to break cycle
for (int r = 0, flag = 0; r < candidate_count; r++) // cycle through ranks
{
for (int c = 0; c < candidate_count; c++) // cycle through possible candidates
{
if (preferences[voter][r] == c && !candidates[c].eliminated)
{
candidates[c].votes++;
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
}
}
}
//dubug printf("%c - votes:%d\n", *candidates[j].name, candidates[j].votes);
// Print the winner of the election, if there is one
bool print_winner(void)
{
// 1) go through candidates array and check who got highest vote
// 2) if there is a candidate who > 1/2 votes - he wins
int top_votes = 0; // biggest number of votes for particular candidate at election
int c; // id of candidate with biggest number of votes
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes > top_votes)
{
top_votes = candidates[i].votes;
c = i;
}
}
if (candidates[c].votes > (voter_count / 2))
{
printf("%s\n", candidates[c].name);
return true;
}
else
return false;
}
// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
// go through all candidates and find out who has least votes
// 1) take 1st candidate and store it's number of votes
// 2) compare 1st candidate with further candidates to find min
int first = 0; // flag which indicate first possible 'min' candidate
int min = 0;
for (int i = 0; i < candidate_count; i++)
{
if (!first && !candidates[i].eliminated)
{
first = 1; // 1st min candidate found, so check flag
min = candidates[i].votes;
}
if (first && !candidates[i].eliminated && candidates[i].votes < min)
{
min = candidates[i].votes;
}
}
return min;
}
// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
// find out is there candidates with the same vote number
// 1) go through candidates
// 2) if candidate eliminated - ignore it
// 3) if all 'active' candidates got same number of votes - tie
// a) compare votes numbers with == between each other.
// b) if even one isn't the same - false
int cmpvote = 0; // flag; to find 1st valid candidate for comparing
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
if (!cmpvote)
cmpvote = candidates[i].votes; // 1st valid candidate for comparison is found
else
{
if (candidates[i].votes != cmpvote && candidates[i].votes != min)
return false;
}
}
}
return true;
}
// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
// check which candidate got 'min' and eliminate him
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes == min)
candidates[i].eliminated = true;
}
return;
}
Solution (by Shtukentsia)
For me, this task turned out to be one of the most difficult at the moment. I spent several hours trying to figure out exactly what needs to be done. I did not think to watch the video with explanations, and as a result, I spent the whole day delving into the essence of the task. The diagrams on paper helped me with this:
If I had watched the video, I could have saved a few hours of torment. As soon as I roughly understood the task, the second problem arose: to understand the individual functions. I managed to make the first bool vote(int voter, int rank, string name) function more or less quickly.
But with the second I was at a dead end. I spent the whole day trying to come up with an algorithm for void tabulate(void), and ended up writing a terribly long code with a lot of nested loops. I think that this is a completely suboptimal solution, but it didn’t work out differently.
Another important point about the option when the vote turns out to be a “draw”, if you enter two candidates A and B, and vote first A B, and then B A, then my program gave a strange error floating point exception (core dumped), this is due to arithmetic except when dividing by zero, or if there is a signed integer overflow.
While I was debugging the program, it turned out that the problem was in the void eliminate(int min) function, which should remove the candidates with the fewest votes. After all, if we have two candidates A and B, and two people vote for them (the first: A B; the second B A), then it turns out that at the first step everyone has 1 vote, and 1 is the least number of votes.
The result is the following program code:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9
// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];
// Candidates have name, vote count, eliminated status
typedef struct
{
string name;
int votes;
bool eliminated;
}
candidate;
// Array of candidates
candidate candidates[MAX_CANDIDATES];
// Numbers of voters and candidates
int voter_count;
int candidate_count;
// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);
int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
candidates[i].eliminated = false;
}
voter_count = get_int("Number of voters: ");
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters is %i\n", MAX_VOTERS);
return 3;
}
// Keep querying for votes
for (int i = 0; i < voter_count; i++)
{
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
string name = get_string("Rank %i: ", j + 1);
// Record vote, unless it's invalid
if (!vote(i, j, name))
{
printf("Invalid vote.\n");
return 4;
}
}
printf("\n");
}
// Keep holding runoffs until winner exists
while (true)
{
// Calculate votes given remaining candidates
tabulate();
// Check if election has been won
bool won = print_winner();
if (won)
{
break;
}
// Eliminate last-place candidates
int min = find_min();
bool tie = is_tie(min);
// If tie, everyone wins
if (tie)
{
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
printf("%s\n", candidates[i].name);
}
}
printf("Tie!\n");
break;
}
// Eliminate anyone with minimum number of votes
eliminate(min);
// Reset vote counts back to zero
for (int i = 0; i < candidate_count; i++)
{
candidates[i].votes = 0;
}
}
return 0;
}
// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
for (int i = 0; i < candidate_count; i++)
{
if (!strcmp(name,candidates[i].name))
{
preferences[voter][rank]=i;
return true;
}
}
return false;
}
// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
for (int j=0; j<candidate_count; j++)
{
for (int i=0; i<candidate_count; i++)
{
for (int z=0; z<voter_count; z++)
{
int prefer_name_index = preferences[z][j];
if (!candidates[prefer_name_index].eliminated)
{
candidates[prefer_name_index].votes+=1;
}
if (candidates[prefer_name_index].eliminated)
{
for (int runoff_j = 1; runoff_j<candidate_count;runoff_j++)
{
prefer_name_index = preferences[z][runoff_j];
if (!candidates[prefer_name_index].eliminated)
{
candidates[prefer_name_index].votes+=1;
}
}
}
}
break;
}
break;
}
return;
}
// Print the winner of the election, if there is one
bool print_winner(void)
{
float half_votes = (voter_count*0.5);
string winner;
for (int i = 0; i < candidate_count; i++)
{
if(candidates[i].votes>half_votes)
{
printf("Winner: %s\n", candidates[i].name);
return true;
}
}
return false;
}
// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
int find_min = voter_count;
for (int i = 0; i<candidate_count; i++)
{
if(candidates[i].votes < find_min && !candidates[i].eliminated)
{
find_min = candidates[i].votes;
}
}
return find_min;
}
// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
int sum_votes = voter_count-min;
int still_in = 1;
int still_in_cand[candidate_count];
for (int i = 0; i<candidate_count; i++)
{
if(!candidates[i].eliminated)
{
still_in_cand[i]=i;
still_in+=1;
}
}
int tie_vote=sum_votes/still_in;
for (int j = 0; j<still_in; j++)
{
if(still_in_cand[j]!=tie_vote)
return false;
}
return true;
}
// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
for (int i=0; i<candidate_count; i++)
{
if (candidates[i].votes==min)
candidates[i].eliminated=true;
}
return;
}
We test the program when voting is a draw:
I thought the program worked well until I tested it with 5 voters:
The result is strange.
Therefore, I decided to check the code through a debugger, and found a lot of bugs. It turned out that two functions did not work correctly for me – the calculation of the votes of the current round and the check for a draw. I had to rewrite them completely. Here’s what I got:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9
// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];
// Candidates have name, vote count, eliminated status
typedef struct
{
string name;
int votes;
bool eliminated;
}
candidate;
// Array of candidates
candidate candidates[MAX_CANDIDATES];
// Numbers of voters and candidates
int voter_count;
int candidate_count;
// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);
int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
candidates[i].eliminated = false;
}
voter_count = get_int("Number of voters: ");
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters is %i\n", MAX_VOTERS);
return 3;
}
// Keep querying for votes
for (int i = 0; i < voter_count; i++)
{
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
string name = get_string("Rank %i: ", j + 1);
// Record vote, unless it's invalid
if (!vote(i, j, name))
{
printf("Invalid vote.\n");
return 4;
}
}
printf("\n");
}
// Keep holding runoffs until winner exists
while (true)
{
// Calculate votes given remaining candidates
tabulate();
// Check if election has been won
bool won = print_winner();
if (won)
{
break;
}
// Eliminate last-place candidates
int min = find_min();
bool tie = is_tie(min);
// If tie, everyone wins
if (tie)
{
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
printf("%s\n", candidates[i].name);
}
}
printf("Tie!\n");
break;
}
// Eliminate anyone with minimum number of votes
eliminate(min);
// Reset vote counts back to zero
for (int i = 0; i < candidate_count; i++)
{
candidates[i].votes = 0;
}
}
return 0;
}
// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
for (int i = 0; i < candidate_count; i++)
{
if (!strcmp(name, candidates[i].name))
{
preferences[voter][rank] = i;
return true;
}
}
return false;
}
// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
for (int i = 0; i < voter_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
int id = preferences[i][j];
if (!candidates[id].eliminated)
{
candidates[id].votes += 1;
break;
}
else
{
for (int z = 1; z < candidate_count; z++)
{
int id_elim = preferences[i][z];
if (!candidates[id_elim].eliminated)
{
candidates[id_elim].votes += 1;
break;
}
}
break;
}
}
}
return;
}
// Print the winner of the election, if there is one
bool print_winner(void)
{
float half_votes = voter_count * 0.5;
string winner;
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes > half_votes)
{
printf("Winner: %s\n", candidates[i].name);
return true;
}
}
return false;
}
// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
int find_min = voter_count;
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes < find_min && !candidates[i].eliminated)
{
find_min = candidates[i].votes;
}
}
return find_min;
}
// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes != min && !candidates[i].eliminated)
{
return false;
}
}
return true;
}
// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes == min)
{
candidates[i].eliminated = true;
}
}
return;
}
Testing the program:
Hooray, now everything works correctly!
This assignment turned out to be very difficult for my level, so I figured it out for several days, maybe even about a week. Many times I wanted to quit everything, because there was a feeling that such a task was too tough for me. The bear was very supportive and believed that everything would work out. And we continued to move forward step by step. And now that the program has started working, I am very happy and proud of us that we are so good!
The task was designed in a very unusual and interesting way, so you learn a lot while completing them. It is important to do everything yourself, and not be guided by the ideas of other people. Bear and I looked at each other’s code only after our programs were fully operational. And it turned out that each of us has a completely unique approach to writing code. Do not look at other people’s ready-made solutions, this will not help you learn how to program. If something does not work out for you, do not despair and give yourself more time.
Everything will work out!