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:
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'.
Challenge
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.
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
andns = [[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 withd=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]]
d=7.5
you get a jump from 19 seats to 21 seats. \$\endgroup\$