Programming challenges: australian voting

I'm trying to solve the following problem:


Australian ballots require that voters rank all the candidates in
order of choice. Initially only the first choices are counted, and if
one candidate receives more than 50% of the vote then that candidate
is elected. However, if no candidate receives more than 50%, all
candidates tied for the lowest number of votes are eliminated. Ballots
ranking these candidates first are recounted in favor of their
highest-ranked non-eliminated candidate. This process of eliminating
the weakest candidates and counting their ballots in favor of the
preferred non-eliminated candidate continues until one candidate
receives more than 50% of the vote, or until all remaining candidates
are tied.


Input


The input begins with a single positive integer on a line by itself
indicating the number of cases following, each as described below.
This line is followed by a blank line. There is also a blank line
between two consecutive inputs. The first line of each case is an
integer n ≤ 20 indicating the number of candidates. The next n lines
consist of the names of the candidates in order, each up to 80
characters in length and containing any printable characters. Up to
1,000 lines follow, each containing the contents of a ballot. Each
ballot contains the numbers from 1 to n in some order. The first
number indicates the candidate of first choice; the second number
indicates candidate of second choice, and so on.


Output


The output of each test case consists of either a single line
containing the name of the winner or several lines containing the
names of all candidates who are tied. The output of each two
consecutive cases are separated by a blank line.


Sample Input


1



3

John Doe

Jane Smith

Jane Austen

1 2 3

2 1 3

2 3 1

1 2 3

3 1 2



Sample Output


John Doe

This is the code I wrote:

```
/*
* australian-voting.cpp
*/

#include
#

C++, not C

You tagged this question C++, but you're not really taking advantage of what C++ has to offer when it comes to this problem. Specifically: the containers. Strongly prefer to use containers over raw arrays (and even then, std::array is better).

As a first go then, we can have:

std::vector candidates;
std::vector> voter_rankings;

This will make everything much easier to deal with. For instance, the check to see if there's a first ballot winner?

// init to zero
std::vector scores(candidates.size(), 0);

// count 'em all up
for (const auto& ranking : rankings) {
    if (!ranking.empty()) {
        ++scores[ranking.front()];
    }
}

// find the max element
auto it = std::max_element(scores.begin(), scores.end());

 // if it's at least half, we have a winner!
 if (*it > candidates.size()/2) { ... }

Containers and algorithms make the code shorter and easier to follow. Win-win.

Start with a function

You should ideally just have:

std::string winner(std::vector const& candidates,
    std::vector> voter_rankings);

That you can call that will give you the result. All your logic for determining the solution is in main(). The various parts are split up into individual functions, which is good, but the whole thing needs to be separate too.

Note that I'm taking the second argument by value as we're going to destroy it as we go.

How many winners?

You need at least half the votes + 1, so there will only ever be one winner. Rather than doing floating point arithmetic, you can check that votes > candidates / 2. This works for both even/odd numbers of candidates.

Finding losers

Finding losers should return the losers:

std::vector losers(std::vector const& scores);

That's the full signature you need. In the OP example, scores the first go will be {2, 2, 1} so this should return {2}, indicating that that is the loser. You don't need a min_votes = 1001 variable - what if we were doing this for all of Australia and each candidate had over 5,000 votes! Your code would break. In fact, that's likely the source of your bug.

The algorithm here is simple: for each score, if either we have no losers or this score matches the losers' scores, append it. Otherwise, if the score is worse than the losers' scores, replace the losers with this one.

This also has the added benefit of not needing to main a separate losers structure that you need to remember to clear.

Also you may find it helpful to remove all instances of votes for a loser whenever you drop one. For instance, our rankings initially started as:

1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

After eliminating 3, the next go should probably look like:

1 2
2 1
2 1
1 2
1 2

Don't recalculate everything

When we drop the worst candidate, we don't need to re-calculate the full score. For instance, in your example, after the first round, we should have:

John Doe --> 2
Jane Smith --> 2
Jane Austen --> 1

So nobody wins and Jane Austen loses. What we need to do then is find all the voters for Jane Austen, and just adjust their votes. There's on such voter (3 1 2), so we just "transfer" (hence "single transferable vote") that vote to the next ranking: --Jane_Austen; ++John_Doe;

Given the losers function, that would be:

auto cur_losers = losers(scores);
// set these scores to -1, they're out of play
for (int loser : cur_losers) {
    scores[loser] = -1;
}

// transfer votes
for (auto& ranking : rankings) {
    bool lost = (scores[ranking.front()] == -1);
    // see erase-remove idiom
    ranking.erase(
        std::remove_if(ranking.begin(), ranking.end(), 
                       [&](int i){ return scores[i] == -1;}),
        ranking.end());
    if (lost) {
        ++scores[ranking.front()];
    }
}

This greatly simplifies the logic, and makes sure that we're not stuck counting votes for candidates that have already lost.

StackExchange Code Review Q#113283, answer score: 11