C++

Forum

 
Ranked Choice Voting

Orion98 (41)
I'm currently writing a program where it performs a series of ranked choice elections based on an input text file containing 3 sets of 5 ballots of the voters' choices out of the 3 candidates running for election.

I already figured out how to run the program in round 1 of the election, but I'm stuck on how to do a round 2 of the election where it'll eliminate the lowest performing candidate, recount the ballots using the highest non-eliminated choice, and determine the winner of round 2.

I'm still new to C++ and If anyone could give me advice on how to do this, I would appreciate it!

Text file(elections.txt):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
15
1
2
3
3
2
1
2
1
3
1
2
3
2
3
1
15
1
2
3
1
2
3
1
2
3
1
2
3
2
1
3
15
3
2
1
3
2
1
3
1
2
1
2
3
1
3
2


My Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
using namespace std;

const char *FILENAME = "elections.txt";
const int MAXBALLOTS = 500;
const int NUM_CANDIDATES = 3;

int elect_candidate(int ballots[MAXBALLOTS][NUM_CANDIDATES],
                    int numBallots) {

        int tally[NUM_CANDIDATES + 1] = { 0 };
        double percentages[NUM_CANDIDATES + 1];

        // Run round 1
        cout << endl;
        cout << "Round 1:" << endl;
        for (int i = 0; i < numBallots; i++) {
            int choice = ballots[i][0];
            tally[choice]++;
        }
        cout << "Percentages for each candidate: " << endl;
        for (int i = 1; i < NUM_CANDIDATES + 1; i++) {
            percentages[i] = (double)tally[i] / numBallots;
            cout << fixed << setprecision(2);
            cout << "#" << i << ": " << percentages[i];
            cout << endl;
        }

        // Round 2 code flow:
        // - Eliminate the lowest performing candidate
        // - Recount the ballots using the highest
        //   non-eliminated choice
        // - Determine winner and return 1, 2, or 3

        return -1;
}
int main()
{
    ifstream f(FILENAME);
    string tmp;
    int nLines;
    int numBallots = 0;

    int ballots[MAXBALLOTS][NUM_CANDIDATES];

    cout << "********************" << endl;
    cout << "C++ Election of 2020" << endl;
    cout << "********************" << endl;

    // While we are not at end-of-file
    while (getline(f, tmp)) {
        // Read the number of lines for this election
        nLines = atoi(tmp.c_str());
        // Read in each ballot
        for (int i = 0; i < nLines; i += 3) {
            // Read in a single ballot (3 lines each)
            cout << "Read ballot: ";
            for (int j = 0; j < NUM_CANDIDATES; j++) {
                getline(f, tmp);
                ballots[numBallots][j] = atoi(tmp.c_str());
                cout << " " << ballots[numBallots][j];
            }
            numBallots++;
            cout << endl;
        }
        cout << "Read " << numBallots << " ballots..." << endl;

        int winner = -1;

        // Run the election
        winner = elect_candidate(ballots, numBallots);
        cout << "********************" << endl;
        cout << "Candidate #" << winner << " wins." << endl;
        cout << "********************" << endl;
        cout << endl;

        // TEMPORARY -- Turn this on if you want to
        // just load 1 set of ballots.
        // return 0;

        // Reset ballot counter for next round
        // -- continue loading more elections.
        numBallots = 0;
    }
    return 0;
}


My Output for Round 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
********************
C++ Election of 2020
********************
Read ballot:  1 2 3
Read ballot:  3 2 1
Read ballot:  2 1 3
Read ballot:  1 2 3
Read ballot:  2 3 1
Read 5 ballots...

Round 1:
Percentages for each candidate:
#1: 0.40
#2: 0.40
#3: 0.20
********************
Candidate #-1 wins.
********************

Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  2 1 3
Read 5 ballots...

Round 1:
Percentages for each candidate:
#1: 0.80
#2: 0.20
#3: 0.00
********************
Candidate #-1 wins.
********************

Read ballot:  3 2 1
Read ballot:  3 2 1
Read ballot:  3 1 2
Read ballot:  1 2 3
Read ballot:  1 3 2
Read 5 ballots...

Round 1:
Percentages for each candidate:
#1: 0.40
#2: 0.00
#3: 0.60
********************
Candidate #-1 wins.
********************


Expected Output for Round 1:
1
2
3
4
5
6
7
8
 
Read 5 ballots.
Candidate #2 wins.

Read 5 ballots.
Candidate #1 wins.

Read 5 ballots.
Candidate #3 wins.
Last edited on
dhayden (5798)
Can you explain the assignment some more? Preferably post the exact text.

Your comments say that a single ballot has 3 lines. What does each line mean? elect_candidate() seems to indicate that they are the voter's choices, in order. But if that's true, then what purpose do their 2nd and 3rd choices serve?
Orion98 (41)
@dhayden;
Each line means one voter's ranked choice from the text file.

Text file(elections.txt):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
15
-
1
2
3
-
3
2
1
-
2
1
3
-
1
2
3
-
2
3
1


From output:
1
2
3
4
5
6
 
Read ballot: |1 2 3|
Read ballot:  3 2 1
Read ballot:  2 1 3
Read ballot:  1 2 3
Read ballot:  2 3 1
Read 5 ballots...


it's ranked choice voting. Instead of choosing a single candidate, voters must rank the available candidates in the order of their choice. For example, if three candidates are available, a voter might choose #2, #1, and #3 as their choices, with #2 being their first choice, #1 the second, and #3 the third.

The outcome is determined by a runoff:
1) The first choices on all ballots are counted. If one candidate receives more than 50% of the vote, that candidate is elected.
2) If no candidate receives more than 50% of the vote, the lowest scoring candidate is eliminated (or multiple candidates if there is a tie for lowest scoring).
3) The ballots are recounted, using the highest ranking non-eliminated candidate on each ballot.
4) The process is repeated until one candidate receives more than 50% of the vote or there is a tie.
Last edited on
dhayden (5798)
I put most of the code in elect_candidate() into a loop. In each round, if a candidate hasn't received a majority of the votes among the remaining candidates, then ballots for the lowest scoring candidate(s) are set to zero.

I think I've covered the edge cases but you should test it carefully.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
using namespace std;

const char *FILENAME = "elections.txt";
const int MAXBALLOTS = 500;
const int NUM_CANDIDATES = 3;

int elect_candidate(int ballots[MAXBALLOTS][NUM_CANDIDATES],
                    int numBallots)
{
    for (int round = 0; round < NUM_CANDIDATES; ++round) {
	// Each pass through this loop is a round of the election
	int tally[NUM_CANDIDATES + 1] = { 0 };
	double percentages[NUM_CANDIDATES + 1];

	cout << endl;
	cout << "Round " << round+1 <<":\n";
	for (int i = 0; i < numBallots; i++) {
	    // Get the highest ranking candidate who remains in the running
	    // for this voter.
	    int j;
	    for (j=0; j<NUM_CANDIDATES; ++j) {
		if (ballots[i][j] > 0) break;
	    }
	    if (j < NUM_CANDIDATES) {
		int choice = ballots[i][j];
		tally[choice]++;
	    } // else all of this voter's candidates have been eliminated
	}

	int best = 1;		// index of winner
	int bestCount = 0;
	int worst = 1;
	cout << "Percentages for each candidate: " << endl;
	for (int i = 1; i < NUM_CANDIDATES + 1; i++) {
	    percentages[i] = (double)tally[i] / numBallots;
	    cout << fixed << setprecision(2);
	    cout << "#" << i << ": " << percentages[i];
	    cout << endl;
	    if (tally[i] > tally[best]) {
		best = i;
		bestCount = 1;
	    } else if (tally[i] == tally[best]) {
		++bestCount;
	    } else if (tally[i] < tally[worst]) {
		worst = i;
	    }
	}
	if (best == worst) {
	    // it's a tie among all remaining candidates
	    return 0;
	}
	if (2*tally[best] > numBallots) {
	    // we have a winner!
	    return best;
	} else {
	    // No winner. Zero out the votes for the losing candidates.
	    for (int i = 0; i < numBallots; i++) {
		for (int j=0; j<NUM_CANDIDATES; ++j) {
		    if (tally[ballots[i][j]] == tally[worst]) {
			cout << "removing " << ballots[i][j]
			     << " from voter " << i+1 << '\n';
			ballots[i][j] = 0;
		    }
		}
	    }
	}
    }

    // You went through all the rounds and found no winner.
    return -1;
}

int main()
{
    ifstream f(FILENAME);
    string tmp;
    int nLines;
    int numBallots = 0;

    int ballots[MAXBALLOTS][NUM_CANDIDATES];

    cout << "********************" << endl;
    cout << "C++ Election of 2020" << endl;
    cout << "********************" << endl;

    // While we are not at end-of-file
    while (f >> nLines) {
        // Read in each ballot
        for (int i = 0; i < nLines; i += 3) {
            // Read in a single ballot (3 lines each)
            cout << "Read ballot: ";
            for (int j = 0; j < NUM_CANDIDATES; j++) {
		f >> ballots[numBallots][j];
                cout << " " << ballots[numBallots][j];
            }
            numBallots++;
            cout << endl;
        }
        cout << "Read " << numBallots << " ballots..." << endl;

        int winner = -1;

        // Run the election
        winner = elect_candidate(ballots, numBallots);
	switch(winner) {
	case -1:
	    cout << "No winner. Time for a runoff!\n";
	    break;
	case 0:
	    cout << "We have a tie!\n";
	    break;
	default:
	    cout << "********************" << endl;
	    cout << "Candidate #" << winner << " wins." << endl;
	    cout << "********************" << endl;
	}

        numBallots = 0;
    }
    return 0;
}

Orion98 (41)
@dhayden; I appreciate your help! But I realized the rounds were optional and all I had to figure out was to determined the winner in each set of ballots. However, when I rewrote the code, I'm still getting this output where it shows '-1' for one of the candidates when its suppose to display '2'.

Edit: I figured the -1 is coming from the return value before int main(). I could change it to value '2', but I'm avoiding any hard-coding.

New Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
using namespace std;

const char *FILENAME = "elections.txt";
const int MAXBALLOTS = 500;
const int NUM_CANDIDATES = 3;

int elect_candidate(int ballots[MAXBALLOTS][NUM_CANDIDATES],
                    int numBallots) {

        int tally[NUM_CANDIDATES + 1] = { 0 };
        double percentages[NUM_CANDIDATES + 1];

        for (int i = 0; i < numBallots; i++) {

	    int j;
	    for (j = 0; j < NUM_CANDIDATES; ++j) {
		if (ballots[i][j] > 0)
            break;
	    }
	    if (j < NUM_CANDIDATES) {
		int choice = ballots[i][j];
		tally[choice]++;
	    }
	}
        int best = 1;
        int bestCount = 0;
        int worst = 1;
        cout << "Percentages for each candidate: " << endl;
        for (int i = 1; i < NUM_CANDIDATES + 1; i++) {
            percentages[i] = (double)tally[i] / numBallots;
            cout << fixed << setprecision(2);
            cout << "#" << i << ": " << percentages[i];
            cout << endl;

        if (tally[i] > tally[best]) {
		best = i;
		bestCount = 1;
	    } else if (tally[i] == tally[best]) {
		++bestCount;
	    } else if (tally[i] < tally[worst]) {
		worst = i;
	    }
	}
	if (best == worst) {
	    return 0;
	}
	if (2 * tally[best] > numBallots) {
	    return best;
	} else {
	    for (int i = 0; i < numBallots; i++) {
		for (int j = 0; j < NUM_CANDIDATES; ++j) {
		    if (tally[ballots[i][j]] == tally[worst]) {
			ballots[i][j] = 0;
		    }
		}
    }
}
    return -1;
}
int main()
{
    ifstream f(FILENAME);
    string tmp;
    int nLines;
    int numBallots = 0;

    int ballots[MAXBALLOTS][NUM_CANDIDATES];

    cout << "********************" << endl;
    cout << "C++ Election of 2020" << endl;
    cout << "********************" << endl;

    // While we are not at end-of-file
    while (getline(f, tmp)) {
        // Read the number of lines for this election
        nLines = atoi(tmp.c_str());
        // Read in each ballot
        for (int i = 0; i < nLines; i += 3) {
            // Read in a single ballot (3 lines each)
            cout << "Read ballot: ";
            for (int j = 0; j < NUM_CANDIDATES; j++) {
                getline(f, tmp);
                ballots[numBallots][j] = atoi(tmp.c_str());
                cout << " " << ballots[numBallots][j];
            }
            numBallots++;
            cout << endl;
        }
        cout << "Read " << numBallots << " ballots..." << endl;
        cout << endl;

        int winner = -1;

        // Run the election
        winner = elect_candidate(ballots, numBallots);
        cout << "********************" << endl;
        cout << "Candidate #" << winner << " wins." << endl;
        cout << "********************" << endl;
        cout << endl;

        numBallots = 0;
    }
    return 0;
}


New Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
********************
C++ Election of 2020
********************
Read ballot:  1 2 3
Read ballot:  3 2 1
Read ballot:  2 1 3
Read ballot:  1 2 3
Read ballot:  2 3 1
Read 5 ballots...

Percentages for each candidate:
#1: 0.40
#2: 0.40
#3: 0.20
********************
Candidate #-1 wins.
********************

Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  1 2 3
Read ballot:  2 1 3
Read 5 ballots...

Percentages for each candidate:
#1: 0.80
#2: 0.20
#3: 0.00
********************
Candidate #1 wins.
********************

Read ballot:  3 2 1
Read ballot:  3 2 1
Read ballot:  3 1 2
Read ballot:  1 2 3
Read ballot:  1 3 2
Read 5 ballots...

Percentages for each candidate:
#1: 0.40
#2: 0.00
#3: 0.60
********************
Candidate #3 wins.
********************

Last edited on
dhayden (5798)
I realized the rounds were optional
If the rounds are optional then why do the voters select 3 choices?
I'm still getting this output where it shows '-1' for one of the candidates when its suppose to display '2'.
Percentages for each candidate:
#1: 0.40
#2: 0.40
#3: 0.20
********************
Candidate #-1 wins.
********************

Since no candidate has a majority, shouldn't it go to a second round? Otherwise, why would #2 win here instead of #1? They both tied according to your percentages.

I think you need to restore the code that does the rounds.
Topic archived. No new replies allowed.