7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Assuming sufficient response: I will select the winner, when the Austrian Election results are confirmed. \$\endgroup\$ – Lyndon White Sep 5 '13 at 15:10
  • 3
    \$\begingroup\$ 1. The external link describes multiple systems, and it's ambiguous as to which one you want people to implement. 2. Neither the post nor the external link describes what happens when multiple candidates tie for last place. 3. A test case is a lot more useful when it includes the expected output as well as the input. \$\endgroup\$ – Peter Taylor Sep 5 '13 at 15:30
  • 5
    \$\begingroup\$ The title says Australia but your first comment says Austria ? You know they are two different countries, right ? One has kangaroos and the other has lederhosen. \$\endgroup\$ – Paul R Sep 5 '13 at 21:45
  • 1
    \$\begingroup\$ Your example program probably is sufficient for those people who own a copy of matlab. For the rest of us, an actual sample of output is surprisingly helpful. \$\endgroup\$ – breadbox Sep 6 '13 at 1:28
  • 1
    \$\begingroup\$ Reference implementations can sometimes clear up ambiguities (if they're written in a transparent pseudocode), but when the issue is one of apparent failure to take into account corner cases the existence of a reference implementation which doesn't explicitly take them into account doesn't help. And when, as in your clarification, there's freedom to choose between three or more different approaches to the corner case, a reference implementation which only implements one of them is misleading. \$\endgroup\$ – Peter Taylor Sep 6 '13 at 8:13
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You just need to return the winning party. The actual number of votes they end up with is not required. \$\endgroup\$ – Lyndon White Sep 6 '13 at 0:11
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ "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." You have it the other way round. You have Index= Preference, Element = candidate ID. idk if this was intentional, or not (thinking on it, it is in someways a better format for the data, since it intrinsially stops people putting two choices at preference 1) \$\endgroup\$ – Lyndon White Sep 6 '13 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.