Es ist die Wahl! Der Bereich, in dem wir uns befinden, implementiert das Abstimmungssystem, das als Instant Runoff bezeichnet wird (manchmal als alternative Abstimmung oder bevorzugte Abstimmung bezeichnet ). Jeder Wähler ordnet jeden Kandidaten von am meisten bevorzugt bis am wenigsten bevorzugt an, wobei er eine "1" für seinen am meisten bevorzugten Kandidaten, eine "2" für seinen zweiten Kandidaten usw. kennzeichnet, bis jeder Kandidat nummeriert ist. Ich werde diesen freundlichen Koala den Rest erklären lassen:

^{(Bild geändert vom Original von Patrick Alexander , verwendet unter der CC BY-NC-SA 3.0 AU Lizenz ).}

Wenn Sie Ihre Erklärung zum sofortigen Ablauf in Textform bevorzugen, gibt es auch den Wikipedia-Artikel .

(Hinweis: Es ist auch möglich, obwohl es unwahrscheinlich ist, dass es zwei oder mehr Kandidaten mit den geringsten Stimmen gibt. Wählen Sie in diesen Situationen einen von ihnen zufällig mit gleichen Wahrscheinlichkeiten aus und eliminieren Sie sie.)

In dieser Herausforderung ist die erste Eingabezeile eine Liste von Zeichenfolgen, die die Namen der Kandidaten für die Wahl sind. In diesen Beispielen habe ich Werte mit Pipe-Trennzeichen verwendet. Sie können das Eingabeformat jedoch auch an Ihre Sprache anpassen.

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

Daran schließen sich nEingabezeilen an, die auch Listen von Zeichenfolgen sind, von denen jede eine einzelne Stimme darstellt. Der erste Eintrag steht für die erste Präferenz, der nächste für die zweite Präferenz usw. Zum Beispiel:

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

Dies würde bedeuten, dass diese bestimmte Stimme Alexander als erste Präferenz hat, Semolina Sorcerer als zweite, Tau Not Two als dritte usw. Sie können davon ausgehen, dass jede Stimme jeden Kandidaten enthält und dass es keine leeren oder unvollständigen Stimmen gibt.

Angesichts der Stimmen als Eingabe sollte Ihr Programm oder Ihre Funktion dann den Wahlsieger ausgeben. Sie können eine ungolfed Referenz - Implementierung in Python 3 finden Sie hier .

Beispiel Ein- und Ausgänge

Eingang

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

Ausgabe

Alexander the Awesome

Eingang

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

Ausgabe

Sighted Citrusoder Frosty Fox(zufällig)

Eingang

Sie können den letzten Eingabesatz bekommen hier . Es ist eines der Wahlgebiete einer kürzlich abgehaltenen australischen Wahl und besteht aus 63.428 Stimmen.

Ausgabe

Ross HART

Pyth - 30 Bytes

Wird es umgestalten. Leitet die erste Zeile von der restlichen Eingabe ab.

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

Probieren Sie es online!

Nimmt Eingaben als Matrix auf, wobei jede Spalte die Auswahlmöglichkeiten eines Wählers darstellt. Arbeiten durch Rekursion: Finden Sie einen Kandidaten mit einer minimalen Anzahl von Stimmen, löschen Sie alle entsprechenden Einträge in der Matrix, formatieren Sie die Matrix neu und wiederholen Sie den Vorgang, bis die Matrix nur noch eine Zeile enthält.

Die Stimmen bei jeder Iteration werden berechnet, indem mit tableden Werten in der oberen Reihe gezählt wird, die die aktuellen Top-Auswahlmöglichkeiten der einzelnen Wähler sind. Dies wird mit gemischt sample, um Unentschieden zufällig zu brechen.

n<-dim(m)-1Gibt einen Vektor der Länge 2 an, aber es wird nur der erste Wert verwendet (also äquivalent, aber 1 Byte kürzer als, n<-nrow(m)-1). Dieser Wert wird zweimal verwendet: Zuerst wird er mit 0 verglichen, um zu überprüfen, ob die letzte Iteration erreicht wurde. zweitens, wenn wir wiederkehren, ist es die Anzahl der Zeilen der neuen Matrix.

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*

Probieren Sie es online!

Nimmt Eingaben als Liste mit Listen der Wählerpräferenzen entgegen (die Kopfzeile ist nicht enthalten). Die Randomisierung im Falle eines Unentschieden ist ärgerlich!

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}

Probieren Sie es 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)

Probieren Sie es online!

Verwendet die Objekt-ID des Arrays als Quelle für 'Zufälligkeit'.
Basierend auf Chas Browns Antwort - Ich habe nicht genug Repräsentanten, um einen Kommentar abzugeben!