Programming challenges: australian voting

Question

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 <iostream>
#include <string>
#include <sstream>

void parse_case(int &candidates_count, int &votes_count, char candidates[][80], int votes[][1000]) {
    std::cin >> candidates_count;
    std::cin.get();
    for (int j=0; j<candidates_count; j++) {
        std::cin.getline(candidates[j], sizeof(candidates[j]), '\n');
    }
    votes_count = 0;
    std::string line;
    while (std::getline(std::cin, line)) {
        if (line.empty()) {
            break;
        }
        std::stringstream ss(line);
        for (int k=0; k<candidates_count; k++) {
            ss >> votes[k][votes_count];
        }
        votes_count++;
    }
}

void reset_losers(bool losers[20]) {
    for (int k=0; k<20; k++) {
        losers[k] = false;
    }
}

void count_votes(int candidates_count, int votes_count, int candidate_votes[20], int votes[][1000]) {
    for (int j=0; j<candidates_count; j++) {
        candidate_votes[j] = 0;
    }
    for (int j=0; j<votes_count; j++) {
        candidate_votes[(votes[0][j]-1)]++;
    }
}

int find_winners(int candidates_count, int remaining_candidates_count, int votes_count, int candidate_votes[20], int subroutine_results[20]) {
    int max_votes = 0;
    int winners_count = 0;

    for (int k=0; k<candidates_count; k++) {
        if (candidate_votes[k] > max_votes) {
            max_votes = candidate_votes[k];
            subroutine_results[0] = k;
            winners_count = 1;
        } else if (candidate_votes[k] == max_votes) {
            subroutine_results[(++winners_count-1)] = k;
        }
    }

    if (winners_count == remaining_candidates_count || ( winners_count == 1 && (double) max_votes / votes_count > 0.5 ) ) {
        return winners_count;
    }

    return 0;
}

int find_losers(int candidates_count, int votes_count, int candidate_votes[20], int subroutine_results[20], bool losers[20]) {
    int min_votes = 1001;
    int losers_count = 0;

    for (int k=0; k<candidates_count; k++) {
        if (!losers[k]) {
            if (candidate_votes[k] < min_votes) {
                min_votes = candidate_votes[k];
                subroutine_results[0] = k;
                losers_count = 1;
            } else if (candidate_votes[k] == min_votes) {
                subroutine_results[(++losers_count-1)] = k;
            }
        }
    }

    for (int i=0; i<losers_count; i++) {
        losers[subroutine_results[i]] = true;
    }

    return losers_count;
}

void eliminate_loser(int remaining_candidates_count, int votes_count, int votes[][1000], int loser) {
    for (int i = 0; i<remaining_candidates_count; i++) {
        for (int j = 0; j<votes_count; j++) {
            if (votes[i][j] == loser + 1) {
                for (int l = i; l<remaining_candidates_count; l++) {
                    votes[l][j] = votes[l + 1][j];
                }
            }
        }
    }
}

int main( int argc, char * argv[] ) {
    int cases_count;
    int candidates_count;
    int remaining_candidates_count;
    int votes_count;
    char candidates[20][80];
    int votes[20][1000];
    int candidate_votes[20];
    int subroutine_results[20];
    bool losers[20];
    int winners_count;
    int losers_count;

    std::cin >> cases_count;
    std::cin.get();
    std::cin.get();

    for (int i=0; i<cases_count; i++) {
        parse_case(candidates_count, votes_count, candidates, votes);
        reset_losers(losers);
        remaining_candidates_count = candidates_count;
        winners_count = 0;
        while (!winners_count) {
            count_votes(candidates_count, votes_count, candidate_votes, votes);
            winners_count = find_winners(candidates_count, remaining_candidates_count, votes_count, candidate_votes, subroutine_results);
            if (winners_count == 0) {
                losers_count = find_losers(candidates_count, votes_count, candidate_votes, subroutine_results, losers);
                for (int k = 0; k<losers_count; k++) {
                    eliminate_loser(remaining_candidates_count, votes_count, votes, subroutine_results[k]);
                    remaining_candidates_count--;
                }
            }
        }
        for (int j=0; j<winners_count; j++) {
            std::cout << candidates[subroutine_results[j]] << std::endl;
        }
        std::cout << std::endl;
    }

    return 0;
}

The automatic submission to https://uva.onlinejudge.org/ and/or to http://www.programming-challenges.com/ is failing, so there must be a problem.

Trying to reproduce the problem I wrote an input data set generator and I compared my results with the results of a program accepted by the online judge (you can do that at http://www.udebug.com/), but my results are consistent with the expected ones (see the data sets I'm using here).

I suppose there must be some edge case that makes it fail but so far I couldn't find it. Any suggestion is welcome.

Answer 1

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<std::string> candidates;
std::vector<std::vector<int>> 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<int> 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<std::string> const& candidates,
    std::vector<std::vector<int>> 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<int> losers(std::vector<int> 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.

Answer 2

Turns out that the error was in the last line of the output. The https://uva.onlinejudge.org/ online judge was just returning Wrong without any hint, but http://www.programming-challenges.com/ gave me a Presentation error, suggesting that there was a formatting issue.

The problem was actually at the end of the single case handling, where I was printing an empty line to separate from the next case.

I should have printed that only if there actually was another case.

Changing:

std::cout << std::endl;

to:

if (i+1 < cases_count) {
    std::cout << std::endl;
}

made the submission successful.