Simulate an instant runoff election

Question

It's the election! The area which we are in implements the system of voting called instant runoff (sometimes called alternative vote or preferential voting). Each voter orders each candidate from most preferred to least preferred, marking a "1" for their most preferred candidate, a "2" for their second candidate, and so forth until each candidate is numbered. I'll let this friendly koala explain the rest:

preferential voting

^{(Image modified from original by Patrick Alexander, used under the CC BY-NC-SA 3.0 AU licence).}

If you prefer your instant runoff explanation in text form, there's also the Wikipedia article.

(Note: It's also possible, although unlikely, for there to be two or more candidates with the least votes. In these situations, choose one of them randomly at equal probabilities and eliminate them.)

In this challenge, the first line of input is a list of strings, which are the names of the candidates for the election. In these examples I've used pipe delimited values, although feel free to adjust the input format to suit your language.

The Omitted Anti-neutrino|Placazoa|Alexander the Awesome|Tau Not Two|Semolina Sorcerer

Following that are n lines of input which are also lists of strings, each which represents a single vote. The first entry represents that votes #1 preference, the next the #2 preference, etc. For example:

Alexander the Awesome|Semolina Sorcerer|Tau Not Two|Placazoa|The Omitted Anti-neutrino

would mean that that particular vote has Alexander as their first preference, Semolina Sorcerer as their second, Tau Not Two as their third, etc. You can assume that every vote will contain every candidate, and that there will be no blank or incomplete votes.

Given the votes as input, your program or function should then output the winner of the election. You can find an ungolfed reference implementation in Python 3 here.

Example Inputs and Outputs

Input

Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Alexander the Awesome|Dionysius|Red Trainmen
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Red Trainmen|Alexander the Awesome|Dionysius
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Portal Butter|Dionysius
Red Trainmen|Alexander the Awesome|Dionysius|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Red Trainmen|Dionysius|Portal Butter|Alexander the Awesome
Alexander the Awesome|Dionysius|Red Trainmen|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Dionysius|Portal Butter

Output

Alexander the Awesome

Input

Depressed Billy|Sighted Citrus|Frosty Fox|Electronic Accident
Frosty Fox|Sighted Citrus|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Depressed Billy|Sighted Citrus|Electronic Accident|Frosty Fox
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Electronic Accident|Frosty Fox|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Sighted Citrus|Electronic Accident|Frosty Fox|Depressed Billy
Frosty Fox|Electronic Accident|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Depressed Billy|Electronic Accident

Output

Sighted Citrus or Frosty Fox (randomly)

Input

You can get the last input set here. It is one of the voting areas of a recent Australian election, and consists of 63 428 votes.

Output

Ross HART

• Maltysen: Do we have to take the first line, or can we infer it from the rest of the input?
• absinthe: @Maltysen You can omit the first line if you want, although please make a note of it in your submission.
• pixma140: @absinthe - the Australian voting set is not there anymore, do you have a copy of it anywhere?

Answer 1

Pyth - 30 bytes

Will refactor it. Infers first line from rest of input.

WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Test Suite.

Answer 2

R, (削除) 101 (削除ここまで) 99 bytes

f=function(m)`if`(n<-dim(m)-1,f(matrix(m[m!=names(t<-sample(table(m[1,])))[which.min(t)]],n)),m[1])

Try it online!

Takes input as a matrix, with each column representing the choices of one voter. Works by recursion: find a candidate with minimal number of votes, delete all corresponding entries in the matrix, reformat the matrix, and recurse until the matrix has only 1 row.

The votes at each iteration are computed by counting with table the values in the top row, which are the current top choices of each voter. This is shuffled with sample to break ties at random.

n<-dim(m)-1 gives a vector of length 2, but only the first value is used (so it is equivalent, but 1 byte shorter than, n<-nrow(m)-1). This value is used twice: first it is compared to 0 to check whether the last iteration has been reached; second, if we recurse, it is the number of rows of the new matrix.

Answer 3

Python 2, 209 bytes

def f(s):
 d={}
 for v in s:
	k=v[0];d[k]=d.get(k,[])+[v]
	if len(d[k])>len(s)/2:return k
 D=d.values()
 for v in choice([g for g in D if len(g)==len(min(D,key=len))]):v.pop(0)
 return f(s)
from random import*

Try it online!

Takes input as a list of lists of voter prefernces (the header row is not included). The randomization in case of a tie is vexing!

Answer 4

Perl 5 -plF\|, 155 bytes

%r?push@v,[@F]:map$r{$_}=1,@F}{while(@v/2>=$c{$\=pop@t}){map{shift@$_ while!$r{$$_[0]}}@v;%c=();map$c{$$_[0]}++,@v;$r{(@t=sort{$c{$a}-$c{$b}}keys%c)[0]}=0}

Try it online!

Answer 5

Python 2, 200 bytes

def f(s):
 d={}
 for v in s:
 k=v[0];d[k]=d.get(k,[])+[v]
 if len(d[k])>len(s)/2:return k
 D=d.values()
 x=[g for g in D if len(g)==len(min(D,key=len))]
 for v in x[id(x)%len(x)]:v.pop(0)
 return f(s)

Try it online!

Utilises the object ID of the array as a source of 'randomness'.
Based off Chas Brown's Answer - I don't have enough rep to comment!