É a eleição! A área em que estamos implementa o sistema de votação chamado escoamento instantâneo (às vezes chamado voto alternativo ou voto preferencial ). Cada eleitor ordena cada candidato do mais preferido ao menos preferido, marcando um "1" para o candidato mais preferido, um "2" para o segundo candidato e assim por diante até que cada candidato seja numerado. Vou deixar este coala amigável explicar o resto:

^{(Imagem modificada do original por Patrick Alexander , usada sob a licença CC BY-NC-SA 3.0 AU ).}

Se você preferir sua explicação instantânea do escoamento instantâneo em forma de texto, também há o artigo da Wikipedia .

(Observação: também é possível, embora improvável, que haja dois ou mais candidatos com menos votos. Nessas situações, escolha um deles aleatoriamente com probabilidades iguais e os elimine.)

Nesse desafio, a primeira linha de entrada é uma lista de strings, que são os nomes dos candidatos à eleição. Nestes exemplos, usei valores delimitados por canal, embora fique à vontade para ajustar o formato de entrada para se adequar ao seu idioma.

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

A seguir, há nlinhas de entrada que também são listas de strings, cada uma representando um único voto. A primeira entrada representa que vota a preferência nº 1, a próxima a preferência nº 2, etc. Por exemplo:

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

significaria que aquele voto em particular tem Alexander como sua primeira preferência, Semolina Sorcerer como seu segundo, Tau Not Two como seu terceiro, etc. Você pode assumir que todo voto conterá todo candidato e que não haverá votos em branco ou incompletos.

Dados os votos como entrada, seu programa ou função deve gerar o vencedor da eleição. Você pode encontrar uma implementação de referência não destruída no Python 3 aqui .

Exemplo de entradas e saídas

Entrada

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

Resultado

Alexander the Awesome

Entrada

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

Resultado

Sighted Citrusou Frosty Fox(aleatoriamente)

Entrada

Você pode obter a última entrada definida aqui . É uma das áreas de votação de uma recente eleição australiana e consiste em 63 428 votos.

Resultado

Ross HART

Pitão - 30 bytes

Vai refatorá-lo. Deduz a primeira linha do restante da entrada.

WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Conjunto de Teste .

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])

Experimente online!

Recebe entrada como uma matriz, com cada coluna representando as opções de um eleitor. Funciona por recursão: encontre um candidato com número mínimo de votos, exclua todas as entradas correspondentes na matriz, reformate a matriz e recorra até que a matriz tenha apenas 1 linha.

Os votos em cada iteração são calculados contando com tableos valores na linha superior, que são as principais opções atuais de cada eleitor. Isso é embaralhado samplepara quebrar os laços aleatoriamente.

n<-dim(m)-1fornece um vetor de comprimento 2, mas apenas o primeiro valor é usado (portanto, é equivalente, mas 1 byte menor que, n<-nrow(m)-1). Este valor é usado duas vezes: primeiro, ele é comparado a 0 para verificar se a última iteração foi atingida; segundo, se recuarmos, é o número de linhas da nova matriz.

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*

Experimente online!

Recebe entrada como uma lista de listas de preferências dos eleitores (a linha do cabeçalho não está incluída). A randomização em caso de empate é irritante!

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}

Experimente online!

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)

Experimente online!

Utiliza o ID do objeto da matriz como uma fonte de 'aleatoriedade'.
Baseado na resposta de Chas Brown - não tenho representante suficiente para comentar!