¡Es la elección! El área en la que estamos implementa el sistema de votación llamado escorrentía instantánea (a veces llamada votación alternativa o votación preferencial ). Cada votante ordena a cada candidato del más preferido al menos preferido, marcando un "1" para su candidato más preferido, un "2" para su segundo candidato, y así sucesivamente hasta que cada candidato esté numerado. Dejaré que este amigable koala explique el resto:

^{(Imagen modificada del original por Patrick Alexander , utilizada bajo la licencia CC BY-NC-SA 3.0 AU ).}

Si prefiere su explicación de escorrentía instantánea en forma de texto, también está el artículo de Wikipedia .

(Nota: también es posible, aunque poco probable, que haya dos o más candidatos con la menor cantidad de votos. En estas situaciones, elija uno de ellos al azar con las mismas probabilidades y elimínelos).

En este desafío, la primera línea de entrada es una lista de cadenas, que son los nombres de los candidatos para la elección. En estos ejemplos, he usado valores delimitados por tuberías, aunque puede ajustar el formato de entrada para adaptarlo a su idioma.

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

A continuación hay nlíneas de entrada que también son listas de cadenas, cada una de las cuales representa un solo voto. La primera entrada representa esa preferencia de votos n. ° 1, la siguiente la preferencia n. ° 2, etc. Por ejemplo:

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

significaría que ese voto en particular tiene a Alexander como su primera preferencia, Semolina Sorcerer como su segundo, Tau Not Two como su tercero, etc. Puede suponer que cada voto contendrá a cada candidato y que no habrá votos en blanco o incompletos.

Dados los votos como aportes, su programa o función debería generar el ganador de la elección. Puede encontrar una implementación de referencia no protegida en Python 3 aquí .

Ejemplo de entradas y salidas

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

Salida

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

Salida

Sighted Citruso Frosty Fox(al azar)

Entrada

Puede obtener la última entrada establecida aquí . Es una de las áreas de votación de una elección australiana reciente, y consta de 63 428 votos.

Salida

Ross HART

Pyth - 30 bytes

Lo refactorizará. Infiere la primera línea del resto de la entrada.

WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Test Suite .

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

Pruébalo en línea!

Toma información como una matriz, con cada columna representando las elecciones de un votante. Funciona por recursión: encuentre un candidato con un número mínimo de votos, elimine todas las entradas correspondientes en la matriz, vuelva a formatear la matriz y vuelva a recurrir hasta que la matriz tenga solo 1 fila.

Los votos en cada iteración se calculan contando con tablelos valores en la fila superior, que son las principales opciones actuales de cada votante. Esto se baraja samplepara romper los lazos al azar.

n<-dim(m)-1da un vector de longitud 2, pero solo se usa el primer valor (por lo que es equivalente, pero 1 byte más corto que n<-nrow(m)-1). Este valor se usa dos veces: primero se compara con 0 para verificar si se ha alcanzado la última iteración; segundo, si recurrimos, es el número de filas de la nueva 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*

Pruébalo en línea!

Toma información como una lista de listas de preferencias de votantes (la fila del encabezado no está incluida). ¡La aleatorización en caso de empate es desconcertante!

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}

Pruébalo en línea!

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)

Pruébalo en línea!

Utiliza el ID de objeto de la matriz como fuente de "aleatoriedad".
Basado en la respuesta de Chas Brown - ¡No tengo suficiente representante para comentar!