Wprowadzenie

W wyborach powszechnych chcielibyśmy obliczyć stałą cenę za mandat parlamentu. Oznacza to, że w N >= 0celu rozdzielenia miejsc i listy nsgłosów na partię chcielibyśmy znaleźć taką liczbę d, która

sum(floor(n/d) for n in ns) == N 

Aby uczynić rzeczy interesującymi (i bardziej podobnymi do realnego świata), dodajemy dwa dodatkowe fakty:

1. Dwie partie mogą zebrać się w „koalicji”, dzięki czemu mandaty zostaną przyznane „koalicji” przez sumę głosów wszystkich partii w niej uczestniczących. Następnie mandaty „koalicji” są podzielone między partiami w podobny sposób (znajdź dzielnik itp.)

2. Partia, która nie uzyskała określonego odsetka głosów (np. 3,25%) automatycznie otrzymuje 0 mandatów, a jej głosy nie liczą się do „koalicji”.

Wyzwanie

Dostaniesz :

1. Lista list, każda z list zagnieżdżonych zawiera liczby całkowite (liczba głosów) i ma długość 1 dla jednej partii lub długość 2 dla „koalicji”.
2. Minimalny procent głosów (aka „bar” dla „zapory”), aby uzyskać miejsca, jako ułamek (więc 3,25% podano jako 0,0325)
3. Całkowita liczba miejsc do podziału między wszystkie strony (liczba całkowita)

Masz wydrukować tę samą strukturę listy zagnieżdżonej, z liczbą głosów zastąpionych miejscami w parlamencie.

Zwycięzca to kod z najmniejszą ilością bajtów.

Narożniki:

• Może istnieć (i zwykle będzie) więcej niż jeden możliwy dzielnik. Ponieważ nie ma go na wyjściu, tak naprawdę nie ma znaczenia.
• Wyobrazić sobie, N=10i ns = [[1]], dlatego mogą być dzielnikiem 0,1 (nie całkowitą)
• Niektóre przypadki nie można rozwiązać, na przykład ns=[[30],[30],[100]], bar=0, N=20. Istnieje granica, w d=7.5której suma wartości zmiennoprzecinkowych skacze z 19 do 21. Nie oczekuje się, że rozwiążesz te przypadki. (podziękowania dla członka społeczności Arnaulda za wskazanie tej sprawy)

Przykład wejścia i wyjścia

Bardzo niezoptymalizowany przykład Python3:

from math import floor

def main(_l, bar, N):
    # sum all votes to calculate bar in votes
    votes = sum(sum(_) for _ in _l)

    # nullify all parties that didn't pass the bar
    _l = [[__ if __ >= bar * votes else 0 for __ in _] for _ in _l]

    # find divisor for all parliament seats
    divisor = find_divisor([sum(_) for _ in _l], N)

    # find divisor for each 'coalition'
    divisors = [find_divisor(_, floor(sum(_)/divisor)) for _ in _l]

    # return final results
    return [[floor(___/_) for ___ in __] for _, __ in zip(divisors, _l)]

def find_divisor(_l, N, _min=0, _max=1):
    s = sum(floor(_ / _max) for _ in _l)
    if s == N:
            return _max
    elif s < N:
            return find_divisor(_l, N, _min, (_max + _min) / 2)
    else:
            return find_divisor(_l, N, _max, _max * 2)

print(main(l, bar, N))

Przykładowe dane wejściowe:

l = [[190970, 156473], 
    [138598, 173004], 
    [143666, 193442], 
    [1140370, 159468], 
    [258275, 249049], 
    [624, 819], 
    [1125881], 
    [152756], 
    [118031], 
    [74701]]
bar = 0.0325
N = 120

I jego wydajność:

[[6, 4], [0, 5], [4, 6], [35, 5], [8, 8], [0, 0], [35], [4], [0], [0]]

Kilka innych przykładowych wyników:

Jeśli bar=0.1uzyskamy interesujący spór między dwiema stronami, ponieważ żadna z mniejszych partii nie jest liczona:

[[0, 0], [0, 0], [0, 0], [60, 0], [0, 0], [0, 0], [60], [0], [0], [0]]

A jeśli N=0(przypadek narożny) to oczywiście nikt nic nie dostaje:

[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0], [0], [0], [0]]

05AB1E , 42 39 bajtów

ÐOOI*@*DO¸I¸¸2Fнζε`sDO/*Щ±/D{®1%Oòè‹+ï

Wypróbuj online!

05AB1E nie ma dobrej rekurencji, więc wdrożenie wyszukiwania binarnego jak w kodzie referencyjnym byłoby bolesne. Na szczęście wcale nie musimy znajdować dzielnika!

Posłużmy się prostym przykładem: [600, 379, 12, 9] głosów, 100 mandatów, brak koalicji, brak baru. Najpierw obliczamy, ile miejsc ułamkowych otrzymuje każda strona, definiując jako ułamkowe miejsca party_votes * seats / sum_of_votes. W naszym przykładzie daje to [60, 37,9, 1,2, 0,9].

Interesujące jest to, że jeśli impreza otrzyma fułamkowe miejsca, dostanie jedno int(f)lub więcej int(f) + 1miejsc. Oznacza to, że wiemy już, w jaki sposób zostanie przydzielonych 60 + 37 + 1 = 98 miejsc, i mamy 2 „miejsca premiowe” do rozdzielenia między 4 strony (żadna ze stron nie może uzyskać więcej niż 1 miejsce premiowe). Do kogo trafiają te dodatkowe miejsca? Strony z najwyższym współczynnikiem f / (int(f) + 1)(dowód pozostawiony jako ćwiczenie dla czytelnika). W naszych przykładach współczynniki są [0.98, 0.997, 0.6, 0.9], więc każda z pierwszych dwóch grup otrzyma dodatkowe miejsce.

Rzućmy okiem na kod. Po pierwsze, zastępujemy liczbę głosów wszystkich stron, które nie spełniły kryteriów, liczbą 0:

Ð          # triplicate the first input (list of votes)
 OO        # flattened sum
   I*      # multiply by the second input (bar)
     @     # greater than? (returns 0 or 1)
      *    # multiply

Teraz, aby obejść brak rekurencji, używamy dziwnego, 2Faby dwukrotnie powtórzyć główny kod. Przy pierwszym przejściu rozdzieli całkowitą liczbę miejsc między koalicjami, a przy drugim przejściu rozdzieli miejsca każdej koalicji między partiami. Ponieważ pierwsze przejście przebiega tylko raz, ale drugie przejście przebiega dla każdej koalicji, wymaga to raczej dużo pracy.

DO¸I¸¸2Fнζε`s    # i don’t want to detail this tbh

Ok, po tym niejasnym bicie, na szczycie stosu znajduje się teraz lista głosów (głosy koalicyjne przy pierwszym podaniu, głosy partyjne przy drugim), a poniżej to liczba miejsc do przydzielenia. Używamy tego do obliczenia listy miejsc ułamkowych:

D        # duplicate
 O       # sum  
  /      # divide each vote count by the sum
   *     # multiply by the number of seats
    ©    # save the fractional seats in variable r

Teraz obliczamy współczynniki:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitowe nie działa pięknie tutaj. Obcina się do liczby całkowitej, dodaje 1 i neguje, wszystko w jednym bajcie. Dlaczego negować? W 05AB1E dzielenie przez 0 zwraca 0 i musimy je posortować na końcu.

D {# posortowana kopia współczynników ® 1% # głosów ułamkowych mod 1 (aka części dziesiętne) O # suma powyższych (jest to liczba miejsc premiowych) ò # zaokrąglenie do najbliższego (wymagane ze względu na zmiennoprzecinkową bs) è # indeks do posortowanych proporcji

To daje nam (n + 1) najlepszy stosunek, gdzie n jest liczbą miejsc premiowych (+1, ponieważ indeksowanie opiera się na 0). Tak więc stronami, które dostają miejsce premiowe, są te, których stosunek jest ściśle mniejszy niż ten.

‹      # less than
 +     # add to the fractional seats
  ï    # truncate to integer

Python 2 , 220 bajtów

def d(l,n,a=0,b=1.):s=sum(x//b for x in l);return s-n and d(l,n,*[a,b,(a+b)/2,b*2][s>n::2])or b
def f(l,b,n):l=[[x*(x>=b*sum(sum(l,[])))for x in r]for r in l];return[[v//d(x,sum(x)//d(map(sum,l),n))for v in x]for x in l]

Wypróbuj online!

Zasadniczo tylko golf implementacji referencyjnej ...

Galaretka , 63 36 bajtów

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

Wypróbuj online!

Pełny program przyjmujący trzy argumenty: liczbę głosów w formacie opisanym przez pytanie, słupek i N w tej kolejności. Zwraca listę list liczby miejsc. Stopka w TIO służy jedynie do podświetlenia struktury listy wyników. (W przeciwnym razie galaretki chowają się []na listach z jednym przedmiotem).

Wyjaśnienie

F×S<ḷ×ḷµ§⁵:,1_×¥:@"§IṠʋ÷9ɗ¥ƬṪṪƲ¥¥@⁺"

F                                   | Flatten vote counts
 ×                                  | Multiply by bar
  S                                 | Sum
   <ḷ                               | Less than original vote counts (vectorises and respects input list structure)
     ×ḷ                             | Multiply by original vote counts
       µ                            | Start a new monadic link with processed vote counts as input
        §                           | Vectorised sum

         ⁵                      ¥@  | Apply the following as a dyad with the number of seats as the right argument and the vectorised sum of votes as left

           ,                  Ʋ¥    |(*)- Pair vote counts with seat sum and find divisor using the following as a monad:
            1             ¥Ƭ        |     - Starting with 1 as a guess for divisor, and using the paired vote counts and seat sum as the right argument, apply the following as a dyad, collecting intermediate results, until the results repeat
                         ɗ          |       - Following as a dyad:
                      ʋ             |         - Following as a dyad:
                :@"                 |           - Integer divide with arguments zipped and reversed, i.e. divide cote counts by current divisor guess and leave total seats alone
                   §                |           -  Vectorised sum (will sum vote counts but leave seat number alone)
                    I               |           - Find differences i.e. desired total seats minus current calculation based on current divisor guess. Will return a list.
                     Ṡ              |           - Sign of this (-1, 0 or 1)
                       ÷9           |         - Divide by 9 (-0.111, 0 or 0.111)
             _×¥                    |     - Now multiply the current divisor guess by this and subtract it from that guess to generate the next guess. If the current guess is correct, the guess will be unchanged and so the Ƭ loop will terminate
                            ṪṪ      |     - Take the last item twice (first time to get the final
                               output of the Ƭ loop and second to remove the list introduced by I
         :                          | - Integer divide the vote counts by the output of the above

                                  ⁺"| Apply the above dyad from the step labelled (*) again, this time with the output of the previous step (total votes per coalition) as right argument and the vote counts as left argument, zipping the two together and running the link once for each pair

Oryginalne zgłoszenie (większe, ale bardziej wydajne)

Galaretka , 63 bajty

:S_3ƭƒṠ©ḢḤ;$;ṪƲṖÆm;ḊƲ®‘¤?ߥ/}ṛ¹?,
1,0;çḢḢ
FS×Ċ’<ḷ×ḷµ:"§:⁵ç$$ç"Ɗ

Wypróbuj online!

Wolfram - bez golfa

Byłem ciekawy rozwiązania go za pomocą LinearProgramming , a nie kandydata do gry w golfa, ale może interesujące podejście do problemu:

findDivisor[l_, n_] := Quiet@Module[{s, c, r, m, b, cons, sol},
   s = Length[l];
   c = Append[ConstantArray[0, s], 1];
   r = Thread[Append[IdentityMatrix[s], -l]];
   m = Append[Join[r, r], Append[ConstantArray[1, s], 0]];
   b = Append[Join[ConstantArray[{0, -1}, s], ConstantArray[{-1, 1}, s]], {n, 0}];
   cons = Append[ConstantArray[Integers, s], Reals];
   sol = LinearProgramming[c, m, b, 0, cons];
   {1/sol[[-1]], Most@sol}
   ]
solve[l_, bar_, n_] := 
 With[{t = l /. x_ /; x <= bar Total[l, 2] -> 0},
  With[{sol = findDivisor[Total /@ t, n]}, 
   {First@sol, MapThread[findDivisor, {t, Last@sol}]}]
  ]

Przeczytaj wyjaśnienie i wypróbuj je!