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:
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.)
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'.
You are given :
- 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'.
- Minimal percentage of votes (a.k.a "bar" for "barrage") to get seats, as a fraction (so 3.25% is given as 0.0325)
- 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.
- There might (and usually will be) more than one possible divisor. Since it is not in the output, it doesn't really matter.
ns = [], so the divisor may be 0.1 (not an integer)
- Some cases can't be solved, for example
N=20. There's a boundary with
d=7.5where 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))
l = [[190970, 156473], [138598, 173004], [143666, 193442], [1140370, 159468], [258275, 249049], [624, 819], , , , ] bar = 0.0325 N = 120
And its output:
[[6, 4], [0, 5], [4, 6], [35, 5], [8, 8], [0, 0], , , , ]
Some more example outputs:
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], , , , ]
N=0 (corner case) then of course no one gets anything:
[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], , , , ]