To wybory! Obszar, w którym się znajdujemy, wdraża system głosowania zwany natychmiastowym odpływem (czasem nazywany głosowaniem alternatywnym lub głosowaniem preferencyjnym ). Każdy głosujący porządkuje każdego kandydata od najbardziej preferowanego do najmniej preferowanego, oznaczając „1” dla najbardziej preferowanego kandydata, „2” dla drugiego kandydata i tak dalej, aż do momentu, gdy każdy kandydat zostanie numerowany. Pozwolę tej przyjaznej koali wyjaśnić resztę:

^{(Zdjęcie zmodyfikowane z oryginału przez Patricka Alexandra , użyte na licencji CC BY-NC-SA 3.0 AU ).}

Jeśli wolisz wyjaśnienia dotyczące natychmiastowego spływu w formie tekstowej, jest też artykuł w Wikipedii .

(Uwaga: jest również możliwe, choć mało prawdopodobne, aby było dwóch lub więcej kandydatów z najmniejszą liczbą głosów. W takich sytuacjach wybierz jednego z nich losowo z jednakowymi prawdopodobieństwami i wyeliminuj ich.)

W tym wyzwaniu pierwszym wierszem wejściowym jest lista ciągów, które są nazwiskami kandydatów w wyborach. W tych przykładach użyłem wartości rozdzielanych potokami, chociaż możesz dostosować format wejściowy do swojego języka.

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

Poniżej znajdują się nwiersze wprowadzania, które są również listami ciągów znaków, z których każdy reprezentuje pojedynczy głos. Pierwszy wpis reprezentuje preferencję głosów nr 1, następny preferencję nr 2 itd. Na przykład:

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

oznaczałoby to, że ten konkretny głos ma Aleksandra jako pierwszą preferencję, Semolina Sorcerer jako drugą, Tau Not Two jako trzecią itd. Możesz założyć, że każdy głos będzie zawierał każdego kandydata i że nie będzie żadnych pustych ani niekompletnych głosów.

Biorąc pod uwagę głosy jako dane wejściowe, twój program lub funkcja powinna następnie wyłonić zwycięzcę wyborów. Można znaleźć ungolfed implementację referencyjną w Pythonie 3 tutaj .

Przykładowe wejścia i wyjścia

Wejście

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

Wynik

Alexander the Awesome

Wejście

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

Wynik

Sighted Citruslub Frosty Fox(losowo)

Wejście

Ostatni zestaw danych wejściowych można uzyskać tutaj . Jest to jeden z obszarów głosowania w ostatnich wyborach w Australii i składa się z 63 428 głosów.

Wynik

Ross HART

Pyth - 30 bajtów

Dokonam refaktoryzacji. Podaje pierwszą linię od reszty danych wejściowych.

WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Pakiet testowy .

R , 101 99 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako macierz, przy czym każda kolumna reprezentuje wybory jednego wyborcy. Działa przez rekurencję: znajdź kandydata z minimalną liczbą głosów, usuń wszystkie odpowiadające mu wpisy w macierzy, sformatuj matrycę i powtarzaj, aż macierz będzie miała tylko 1 wiersz.

Głosy przy każdej iteracji są obliczane poprzez zliczenie z tablewartościami w górnym rzędzie, które są bieżącymi najlepszymi wyborami każdego głosującego. Jest to tasowane, sampleaby losowo zerwać więzi.

n<-dim(m)-1daje wektor o długości 2, ale używana jest tylko pierwsza wartość (więc jest równoważna, ale o 1 bajt krótsza niż, n<-nrow(m)-1). Ta wartość jest używana dwukrotnie: najpierw jest porównywana z 0, aby sprawdzić, czy osiągnięto ostatnią iterację; po drugie, jeśli powtórzymy, jest to liczba wierszy nowej macierzy.

Python 2 , 209 bajtów

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*

Wypróbuj online!

Pobiera dane wejściowe jako listę list preferencji wyborców (wiersz nagłówka nie jest uwzględniony). Randomizacja w przypadku remisu jest dokuczliwa!

Perl 5 -plF\| , 155 bajtów

%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}

Wypróbuj online!

Python 2 , 200 bajtów

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)

Wypróbuj online!

Wykorzystuje identyfikator obiektu tablicy jako źródło „losowości”.
Na podstawie odpowiedzi Chasa Browna - nie mam wystarczającej liczby przedstawicieli, aby móc komentować!