Distributing parliament seats

Question

Introduction

In a general election, one would like to calculate a constant price per parliament seat. This means that for N >= 0 seats to be distributed and a list ns of votes per party, we would like to find a number d such that

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

To make things interesting (and more like the real world), we add two more facts:

1. Two parties can gather in a 'coalition', so that the seats are given to the 'coalition' by the sum of votes for all parties in it. Then the seats the 'coalition' got are split between parties in a similar fashion (find divisor, etc.)

2. A party that didn't pass a certain percentage of the votes (e.g. 3.25%) automatically gets 0 seats, and its votes don't count for a 'coalition'.

Challenge

You are given :

1. A list of lists, each of the nested lists contains integers (number of votes), and is of length 1 for a single party, or length 2 for a 'coalition'.
2. Minimal percentage of votes (a.k.a "bar" for "barrage") to get seats, as a fraction (so 3.25% is given as 0.0325)
3. Total number of seats to be distributed between all parties (integer)

You are to print out the same nested list structure, with the number of votes substituted with parliament seats.

Winner is the code with the smallest amount of bytes.

Corner cases:

• There might (and usually will be) more than one possible divisor. Since it is not in the output, it doesn't really matter.
• Imagine N=10 and ns = [[1]], so the divisor may be 0.1 (not an integer)
• Some cases can't be solved, for example ns=[[30],[30],[100]], bar=0, N=20. There's a boundary with d=7.5 where the sum of floored values jumps from 19 to 21. You are not expected to solve these cases. (thanks to community member Arnauld for pointing this case out)

Example Input and Output

A very not-optimized Python3 example:

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

Example input:

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

And its output:

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

Some more example outputs:

If bar=0.1 we get an interesting stand-off between two parties as none of the smaller parties are counted in:

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

And if N=0 (corner case) then of course no one gets anything:

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

Answer 1

05AB1E, 42 39 bytes

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

Try it online!

05AB1E lacks good recursion, so implementing a binary search as in the reference code would be painful. Thankfully, we don’t need to find the divisor at all!

Let’s use a simple example: [600, 379, 12, 9] votes, 100 seats, no coalitions, no bar. First, we compute how many fractional seats each party gets, defining fractional seats as party_votes * seats / sum_of_votes. In our example, that yields [60, 37.9, 1.2, 0.9].

The interesting bit is that if a party gets f fractional seats, it will get either int(f) or int(f) + 1 real seats. This means we already know how 60+37+1 = 98 of the seats will be allocated, and we’re left with 2 “bonus seats” to distribute among the 4 parties (no party can get more than 1 bonus seat). Who do these bonus seats go to? The parties with the highest ratio of f / (int(f) + 1) (proof left as an exercise to the reader). In our examples, the ratios are [0.98, 0.997, 0.6, 0.9], so the first two parties get a bonus seat each.

---

Let’s take a look at the code. First, we replace the vote count of all parties that didn’t meet the bar with 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

Now, to work around the lack of recursion, we use an awkard 2F to repeat the main code twice. On the first pass it’ll distribute the total seats between coalition, and on the second pass it’ll distribute each coalition’s seats between its parties. Since the first pass runs only once, but the second pass runs for each coalition, this involves rather a lot of busy work.

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

Okay, after this obscure bit, the top of the stack is now a list of votes (coalition votes on the first pass, party votes on the second), and below that is the number of seats to allocate. We use this to compute the list of fractional seats:

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

Now, we compute the ratios:

Ð            # triplicate
 ±           # bitwise not
  /          # divide

Bitwise not works beautifully, here. It truncates to integer, adds 1, and negates, all in a single byte. Why negate? In 05AB1E, division by 0 returns 0, and we need these to sort last.

D{ # sorted copy of the ratios ®1% # fractional votes mod 1 (aka the decimal parts) O # sum of the above (this is the number of bonus seats) ò # round to nearest (required due to floating point bs) è # index into the sorted ratios

This gives us the (n+1)th best ratio, where n is the number of bonus seats (+1 because indexing is 0 based). Thus, the parties that get a bonus seat are those that have a ratio strictly less than this.

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

Answer 2

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]

Try it online!

Basically just a golf of the reference implementation...

Answer 3

Jelly, 63 36 bytes

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

Try it online!

A full program taking three arguments: the numbers of votes in the format described by the question, bar and N in that order. Returns a list of lists of seat counts. The footer on TIO is just to highlight the list structure of the output. (Otherwise Jelly hides [] for single-item lists.)

Explanation

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

Original Submission (larger but more efficient)

Jelly, 63 bytes

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

Try it online!

Answer 4

Wolfram - no golf

Was just curious to solve it using LinearProgramming, not a golfing candidate, but maybe an interesting approach to a problem:

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

Read some explanation and try it out!