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!