Introducción

En una elección general, a uno le gustaría calcular un precio constante por escaño en el parlamento. Esto significa que para N >= 0que se distribuyan los escaños y una lista nsde votos por partido, nos gustaría encontrar un número dtal que

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

Para hacer las cosas interesantes (y más como el mundo real), agregamos dos hechos más:

1. Dos partidos pueden reunirse en una 'coalición', de modo que los asientos se otorguen a la 'coalición' por la suma de los votos para todos los partidos en ella. Luego, los asientos que obtuvo la 'coalición' se dividen entre los partidos de manera similar (encontrar divisor, etc.)

2. Un partido que no aprobó cierto porcentaje de los votos (por ejemplo, 3.25%) automáticamente obtiene 0 escaños, y sus votos no cuentan para una 'coalición'.

Desafío

Te dan:

1. Una lista de listas, cada una de las listas anidadas contiene números enteros (número de votos) y tiene una longitud de 1 para un solo partido, o una longitud de 2 para una 'coalición'.
2. Porcentaje mínimo de votos (también conocido como "barra" para "bombardeo") para obtener escaños, como una fracción (por lo que 3.25% se da como 0.0325)
3. Número total de asientos que se distribuirán entre todas las partes (entero)

Debe imprimir la misma estructura de lista anidada, con el número de votos sustituido por escaños en el parlamento.

El ganador es el código con la menor cantidad de bytes.

Casos de esquina:

• Puede haber (y generalmente habrá) más de un posible divisor. Como no está en la salida, realmente no importa.
• Imagina N=10y ns = [[1]], entonces el divisor puede ser 0.1 (no un entero)
• Algunos casos no se pueden resolver, por ejemplo ns=[[30],[30],[100]], bar=0, N=20. Hay un límite d=7.5en el que la suma de los valores del piso salta de 19 a 21. No se espera que resuelva estos casos. (gracias al miembro de la comunidad Arnauld por señalar este caso)

Ejemplo de entrada y salida

Un ejemplo muy poco optimizado de 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))

Entrada de ejemplo:

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

Y su salida:

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

Algunas salidas más de ejemplo:

Si bar=0.1obtenemos un enfrentamiento interesante entre dos partes, ya que ninguna de las partes más pequeñas se cuenta en:

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

Y si N=0(caso de esquina), por supuesto, nadie obtiene nada:

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

05AB1E , 42 39 bytes

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

Pruébalo en línea!

05AB1E carece de una buena recursividad, por lo que implementar una búsqueda binaria como en el código de referencia sería doloroso. ¡Afortunadamente, no necesitamos encontrar el divisor en absoluto!

Usemos un ejemplo simple: [600, 379, 12, 9] votos, 100 escaños, sin coaliciones, sin barra. Primero, calculamos cuántos asientos fraccionarios obtiene cada partido, definiendo los asientos fraccionarios como party_votes * seats / sum_of_votes. En nuestro ejemplo, eso produce [60, 37.9, 1.2, 0.9].

Lo interesante es que si una fiesta obtiene fasientos fraccionados, obtendrá asientos reales int(f)o int(f) + 1reales. Esto significa que ya sabemos cómo se asignarán 60 + 37 + 1 = 98 de los asientos, y nos quedan 2 "asientos adicionales" para distribuir entre las 4 partes (ninguna parte puede obtener más de 1 asiento adicional). ¿A quién van estos asientos de bonificación? Las partes con la proporción más alta de f / (int(f) + 1)(prueba dejada como ejercicio para el lector). En nuestros ejemplos, las proporciones son [0.98, 0.997, 0.6, 0.9], por lo que las dos primeras partes obtienen un asiento adicional cada una.

Echemos un vistazo al código. Primero, reemplazamos el recuento de votos de todos los partidos que no cumplieron con la barra con 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

Ahora, para evitar la falta de recursión, usamos un torpe 2Fpara repetir el código principal dos veces. En el primer pase distribuirá el total de escaños entre coaliciones, y en el segundo pase distribuirá los escaños de cada coalición entre sus partidos. Dado que el primer pase se ejecuta solo una vez, pero el segundo pase se ejecuta para cada coalición, esto implica bastante trabajo ocupado.

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

De acuerdo, después de este poco oscuro, la parte superior de la pila ahora es una lista de votos (votos de coalición en el primer pase, votos del partido en el segundo), y debajo de eso está el número de asientos para asignar. Usamos esto para calcular la lista de asientos fraccionarios:

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

Ahora, calculamos las razones:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitwise no funciona de maravilla, aquí. Se trunca a entero, agrega 1 y niega, todo en un solo byte. ¿Por qué negar? En 05AB1E, la división por 0 devuelve 0, y los necesitamos para ordenar al final.

D {# copia ordenada de las proporciones ®1% # votos fraccionarios mod 1 (también conocido como las partes decimales) O # suma de lo anterior (este es el número de asientos de bonificación) ò # redondeado al más cercano (requerido debido al punto flotante bs) è # índice en las proporciones ordenadas

Esto nos da la mejor relación (n + 1), donde n es el número de asientos de bonificación (+1 porque la indexación está basada en 0). Por lo tanto, las partes que obtienen un asiento adicional son aquellas que tienen una proporción estrictamente menor que esta.

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

Python 2 , 220 bytes

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]

Pruébalo en línea!

Básicamente solo un golf de la implementación de referencia ...

Jalea , 63 36 bytes

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

Pruébalo en línea!

Un programa completo que toma tres argumentos: el número de votos en el formato descrito por la pregunta, barra y N en ese orden. Devuelve una lista de listas de recuentos de asientos. El pie de página en TIO es solo para resaltar la estructura de la lista de la salida. (De lo contrario, Jelly se esconde[] para las listas de elementos individuales).

Explicación

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

Presentación original (más grande pero más eficiente)

Jalea , 63 bytes

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

Pruébalo en línea!

Wolfram - sin golf

Tenía curiosidad por resolverlo usando LinearProgramming , no un candidato para jugar al golf, pero quizás un enfoque interesante para un problema:

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

¡Lee alguna explicación y pruébalo!