Distributing parliament seats

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

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