adh529’s blog

Problem:

“Australian ballots require that the voter rank the candidates in order of choice. Initially only the first choices are counted and if one candidate receives more than 50% of the vote, that candidate is elected. 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 favour of their highest ranked candidate who has not been eliminated. This process continues [that is, the lowest candidate is eliminated and each ballot is counted in favour of its ranked non-eliminated candidate] until one candidate receives more than 50% of the vote or until all candidates are tied.”

Two extremes:

All candidates are tied, equally ==> in which case, all candidates names should be printed, in no prescribed order.

One winner by majority on the first pass ==> in which case, the winner’s name should be printed

Let’s take a look at some sample input:

“The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.”

“The first line of input is an integer n <= 20 indicating the number of candidates. The next n lines consist of the names of the candidates in order. Names may be up to 80 characters in length and may contain any printable characters. Up to 1000 lines follow; each contains the contents of a ballot. That is, each 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.”

==begin==

1

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

==end==

In this simple example, after the first choice of each ballot is read in, candidate #3 (Sirhan Sirhan) is removed from the list of possible winners, and each vote next in preference on all ballots that had #3 as first pick, provided they are votes for possible candidates, are counted and added to the existing totals.

The output should trivially be: “John Doe”

==coding it==

Now let’s look at a simple machinery that will perform this type of calculation, even under large-scale scrutiny:

==begin pseudocode==

+read in #testcases

while(#testcases>0){

+read in #candidates

for(int i=0; i<#candidates; i++){
+read in name of each candidate and put into an array
}

//we do not have a preconceived idea of how many ballots ==> read til’ blank line
//by now we know how many choices to expect in each ballot
//and we also know the number and names of candidates
while(+read != “\n”){
+store ballot in its entirety in an array at index [ballot#]
+inspect the first choice of each ballot, and increment counters for respective candidates

}

if(by end of ballots, we have a first-pass winner (>50%))
print(winner);

while(winner!=found){
+throw away the loser(s) by eliminating them from list of possible winners
+inspect the next highest choice of preference for losers’ ballots and,
==>provided the next votes are not for existing losers, increment counters for respective candidates
====>if, however, the next preference is for a loser, repeatedly iterate down the preferential hierarchy until a vote for a possible winner is found
}  //lather, rinse, repeat, until a winner or a group of winners is found, and print respectively

#testcases-=1;
}  //lather, rinse, repeat, until we are done with every test case

==end pseudocode==