introduction

Lors d'une élection générale, on souhaiterait calculer un prix constant par siège parlementaire. Cela signifie que pour la N >= 0répartition des sièges et une liste nsdes votes par parti, nous aimerions trouver un nombre dtel que

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

Pour rendre les choses intéressantes (et plus comme le monde réel), nous ajoutons deux autres faits:

1. Deux partis peuvent se rassembler en une «coalition», de sorte que les sièges sont attribués à la «coalition» par la somme des voix de tous les partis. Ensuite, les sièges obtenus par la `` coalition '' sont répartis entre les partis de la même manière (trouver un diviseur, etc.)

2. Un parti qui n'a pas obtenu un certain pourcentage des voix (par exemple 3,25%) obtient automatiquement 0 siège, et ses votes ne comptent pas pour une «coalition».

Défi

On vous donne:

1. Une liste de listes, chacune des listes imbriquées contient des nombres entiers (nombre de votes), et est de longueur 1 pour un parti unique, ou de longueur 2 pour une «coalition».
2. Pourcentage minimal de votes (aka "bar" pour "barrage") pour obtenir des sièges, sous forme de fraction (donc 3,25% est donné comme 0,0325)
3. Nombre total de sièges à répartir entre tous les partis (entier)

Vous devez imprimer la même structure de liste imbriquée, avec le nombre de votes substitué aux sièges du Parlement.

Winner est le code avec le plus petit nombre d'octets.

Cas d'angle:

• Il pourrait y avoir (et il y aura généralement) plus d'un diviseur possible. Comme il n'est pas dans la sortie, cela n'a pas vraiment d'importance.
• Imaginez N=10et ns = [[1]], donc le diviseur peut être 0,1 (pas un entier)
• Par exemple certains cas ne peuvent pas être résolus, ns=[[30],[30],[100]], bar=0, N=20. Il y a une limite avec d=7.5laquelle la somme des valeurs plancher passe de 19 à 21. On ne s'attend pas à ce que vous résolviez ces cas. (merci au membre de la communauté Arnauld d'avoir signalé ce cas)

Exemple d'entrée et de sortie

Un exemple Python3 très non optimisé:

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

Exemple d'entrée:

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

Et sa sortie:

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

Quelques autres exemples de sorties:

Si bar=0.1nous obtenons une confrontation intéressante entre deux partis, car aucun des petits partis n'est compté dans:

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

Et si N=0(cas d'angle) alors bien sûr, personne ne reçoit rien:

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

05AB1E , 42 39 octets

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

Essayez-le en ligne!

05AB1E manque de bonne récursivité, donc l'implémentation d'une recherche binaire comme dans le code de référence serait douloureuse. Heureusement, nous n'avons pas du tout besoin de trouver le diviseur!

Prenons un exemple simple: [600, 379, 12, 9] votes, 100 sièges, pas de coalitions, pas de bar. Premièrement, nous calculons le nombre de sièges fractionnaires que chaque parti obtient, en définissant les sièges fractionnaires commeparty_votes * seats / sum_of_votes . Dans notre exemple, cela donne [60, 37,9, 1,2, 0,9].

Ce qui est intéressant, c'est que si un parti obtient fdes sièges fractionnaires, il obtiendra l'un int(f)ou les int(f) + 1vrais sièges. Cela signifie que nous savons déjà comment 60 + 37 + 1 = 98 des sièges seront attribués, et il nous reste 2 "sièges bonus" à répartir entre les 4 partis (aucun parti ne peut obtenir plus d'un siège bonus). À qui s'adressent ces sièges bonus? Les parties avec le ratio le plus élevé de f / (int(f) + 1)(preuve laissée en exercice au lecteur). Dans nos exemples, les ratios sont [0.98, 0.997, 0.6, 0.9], donc les deux premiers partis obtiennent chacun un siège bonus.

Jetons un coup d'œil au code. Tout d'abord, nous remplaçons le décompte des voix de tous les partis qui ne respectent pas la barre par 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

Maintenant, pour contourner le manque de récursivité, nous utilisons un maladroit 2Fpour répéter le code principal deux fois. Lors de la première passe, il répartira le total des sièges entre les coalitions, et lors de la deuxième passe, il répartira les sièges de chaque coalition entre ses partis. Étant donné que la première passe ne s'exécute qu'une seule fois, mais que la deuxième passe s'exécute pour chaque coalition, cela implique un travail plutôt chargé.

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

D'accord, après ce bit obscur, le haut de la pile est maintenant une liste de votes (votes de la coalition au premier passage, votes des partis au second), et en dessous, le nombre de sièges à attribuer. Nous l'utilisons pour calculer la liste des sièges fractionnaires:

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

Maintenant, nous calculons les ratios:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitwise ne fonctionne pas magnifiquement, ici. Il tronque en entier, ajoute 1 et nie, le tout dans un seul octet. Pourquoi nier? Dans 05AB1E, la division par 0 renvoie 0, et nous en avons besoin pour trier en dernier.

D {# copie triée des ratios ®1% # votes fractionnaires mod 1 (alias les parties décimales) O # somme de ce qui précède (c'est le nombre de sièges bonus) ò # arrondi au plus proche (requis en raison de la virgule flottante bs) è # index dans les ratios triés

Cela nous donne le (n + 1) e meilleur rapport, où n est le nombre de sièges bonus (+1 car l'indexation est basée sur 0). Ainsi, les partis qui obtiennent un siège bonus sont ceux qui ont un ratio strictement inférieur à celui-ci.

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

Python 2 , 220 octets

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]

Essayez-le en ligne!

Fondamentalement, juste un golf de la mise en œuvre de référence ...

Gelée , 63 36 octets

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

Essayez-le en ligne!

Un programme complet prenant trois arguments: le nombre de votes dans le format décrit par la question, la barre et N dans cet ordre. Renvoie une liste de listes de nombre de sièges. Le pied de page sur TIO est juste pour mettre en évidence la structure de liste de la sortie. (Sinon, Jelly se cache[] pour les listes d'articles uniques.)

Explication

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

Soumission originale (plus grande mais plus efficace)

Gelée , 63 octets

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

Essayez-le en ligne!

Wolfram - pas de golf

Était simplement curieux de le résoudre en utilisant LinearProgramming , pas un candidat au golf, mais peut-être une approche intéressante à un problème:

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

Lisez quelques explications et essayez-les!