Preferential Voting

Question

Australia (and many countries) has a perferential voting system, where voters, number the candidates from 1 - n, where n is the number of candidates, in order of preference. Until a candidate gets a absolute majority of votes, the number 1 votes for the candidate with minimum count of number 1 votes, are redistributed to their next preference. Full detail can be found at http://www.eca.gov.au/systems/single/by_category/preferential.htm, under the The Full Preferential Count

Implement a system that takes in a array of voting slips. where a voting slip is a array, where each index is a candidate ID, and the element at that index is the voters preference number for that candidate.

Eg: for a 3 candidates with, 7 voting slips, input could be:

    votes =
   2   1   3
   1   2   3
   3   2   1
   1   3   2
   1   2   3
   2   3   1
   3   2   1

You may take this input in your languages preferred 2D array like data structure.

Example function: (matlab)

function winningParty = countVotes (votes)
    [nVotes, nParties] = size(votes)

    cut = zeros(1,nParties) % no one is cut at the start
    while(max(sum(votes==1))<=0.5*nVotes) %while no  one has absolute majority
        [minVotes, cutParty] = min(sum(votes==1) .+ cut*nVotes*2)                           %make sure not cut twice, by adding extra votes to cut party

        votes(votes(:,cutParty)==1,:)--; % reassign there votes

        cut(cutParty) = true;
        votes

    end
    [winnersVotes, winningParty] = max(sum(votes==1))

Output:

octave:135> countVotes(votes)
nVotes =  7
nParties =  3
cut =

   0   0   0

minVotes =  1
cutParty =  2
votes =

   1   0   2
   1   2   3
   3   2   1
   1   3   2
   1   2   3
   2   3   1
   3   2   1

winnersVotes =  4
winningParty =  1
ans =  1 %This is the only line i care about

---

EDIT: In cases of tie for lowest portion of primary share, either can be removed. There can be no tie for winning candidate. Winner must have strictly greater than 50% of votes.

Answer 1

Python 3, 173 146 Python 2, 125(see below)

Original version, 173:

C=sorted(S[0]);C[-1]=0
while C:
 v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C};c=max(C,key=v.get);C.remove(min(C,key=v.get))
 if v[c]*2>len(S):C=print(v[c],c+1)

Expects input in this form:

S=[
   [2,   1,   3],
   [1,   2,   3],
   [3,   2,   1],
   [1,   3,   2],
   [1,   2,   3],
   [2,   3,   1],
   [3,   2,   1],
   ]

and prints number of votes and the winning candidate:

4 1

Commented version:

# create a list of the (still available) candidates;
# these will be used as indexes and therefore have to start at 0 instead of 1
C=sorted(S[0]);C[-1]=0 
# start a loop with some condition that's easily stoppable later
while C:
    # for each slip s, find the (still available) candidate with the best vote; count these for each (still available) candidate
    v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C}
    # find the candidate with the highest number of votes
    c=max(C,key=v.get)
    # remove the candidate with the lowest number of votest
    C.remove(min(C,key=v.get))
    # somebody with more than 50 % of the votes (=slips) already?
    if v[c]*2>len(S):
        # if yes, then print votes and candidate number
        # (the print function returns None, which makes the condition of the loop fail)
        C=print(v[c],c+1) 

EDIT After clarification of output by OP:

C=sorted(S[0]);C[-1]=0
while C:v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C};c=max(C,key=v.get);C.remove(min(C,key=v.get))
print(c+1)

(The loop runs to exhaustion of candidates, which is no problem, because the number of votes is not neeeded.)

EDIT 2, newest version, Python 2, 125:

Python 2 range yields a list, which is shorter than the construction I had to use for Python 3.

Also, c need not at all times be the candidate with tho most votes -- it's only important at the end. At the end, there is only one candidate left, so c just has to be some candidate (I use C[0]), because that must be the right one at the end.

That means that the name v is use only once. Replacing that usage with the definition of v saves some more characters.

C=range(len(S[0]))
while C:c=C[0];C.remove(min(C,key={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C}.get))
print c+1

Answer 2

GolfScript, 37 characters

.0=,({.0={`{\0==}+1$\,,}$1>`{&}+%}*0=

Input (on stack) is a list of votes where elements can be e.g. numbers or strings. Example:

[
  ["Bernard" "Archibald" "Chris"]
  ["Archibald" "Bernard" "Chris"]
  ["Chris" "Bernard" "Archibald"]
  ["Archibald" "Chris" "Bernard"]
  ["Archibald" "Bernard" "Chris"]
  ["Bernard" "Chris" "Archibald"]
  ["Chris" "Bernard" "Archibald"]
]

.0=,({.0={`{\0==}+1$\,,}$1>`{&}+%}*0=

# => either Archibald or Bernard (because of tie)