13
\$\begingroup\$

It's time... to count the votes!

Today there are local elections in my entire country. Here, the number of seats for each party is decided using the D'Hondt method. Your goal is to implement a program or function that will decide how many seats each party gets, in the shortest amount of bytes.

For this method there are a fixed number of seats to distribute, and it's done like so:

  1. Every party is assigned a variable number, which starts at the number of votes it got.
  2. Then the first seat is given to the party who has the biggest value in their variable and then that value for that party becomes their total number of votes divided by 1+seats, rounded down, where seats is the number of seats it already has (so after getting the first, their votes are divided by 2, and by 3 after getting the second seat).
  3. After that the parties votes are compared again. The process continues until all the seats have been assigned.

If the highest number is a tie between two or more parties, it is resolved randomly (It has to be random, it can't just be the first of the two in the list).

Input

You will receive a number N, which will indicate the number of seats available, and a list of the votes each party received, in whatever format you prefer. Example:

25
12984,7716,13009,4045,1741,1013

Output

You should output a list of the seats each party got. In the example above it would be something like

8,5,9,2,1,0

They should be in the same order as the parties in the input.

Examples

5
3,6,1

outputs: 2,3,0

135
1116259,498124,524707,471681,359705,275007,126435

outputs: 45,20,21,19,14,11,5

Bonus

-20% bonus if take the parties name as input and give them in the output, like for example:

25
cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013

outputs

cio:8
pcc:5
irc:9
icb:2
cub:1
bb:0
\$\endgroup\$
  • \$\begingroup\$ I feel we already did something like this \$\endgroup\$ – edc65 May 24 '15 at 11:58
  • \$\begingroup\$ I couldn't find anything alike in the search... But if you find anything I will change it or remove the question, no problem! \$\endgroup\$ – rorlork May 24 '15 at 12:00
  • \$\begingroup\$ @rcrmn There is something wrong with your last example. Maybe you meant 153 total seats instead of 135. \$\endgroup\$ – Tyilo May 24 '15 at 13:39
  • \$\begingroup\$ @Tyilo Right! I wrote it wrong in my test program and copied the answers without double-checking. It's fixed now. Thank you! \$\endgroup\$ – rorlork May 24 '15 at 13:43
  • 1
    \$\begingroup\$ Thanks @Jakube , that was a problem with the program I used to calculate, which returned the output ordered in seats with labels. Dennis you can return it in any order, since the label works as an identifyer. You can assume it only has letters if it's easier for you. \$\endgroup\$ – rorlork May 24 '15 at 15:10
6
\$\begingroup\$

CJam, 35.2 28.8 28.0 26.4

q2*~,m*mr{~)f/1=~}$<:(f{1$e=1\tp}

This full program is 33 bytes long and qualifies for the bonus.

Try it online in the CJam interpreter.

Example run

$ cjam seats <<< '[["cio"12984]["pcc"7716]["irc"13009]["icb"4045]["cub"1741]["bb"1013]]25'
["cio" 8]
["pcc" 5]
["irc" 9]
["icb" 2]
["cub" 1]
["bb" 0]

How it works

q2*~   e# Repeat the input from STDIN twice. Evaluate.
       e# STACK: Array seats Array seats
,      e# Range: seats -> [0 ... seats-1]
m*     e# Take the cartesian product of the array from the input and the range.
mr     e# Shuffle the array. This makes sure tie breakers are randomized.
{      e# Sort by the following key:
  ~    e#     Dump: [["party" votes] number] -> ["party" votes] number
  f/   e#     Divide each: ["party" votes] number -> ["party"/number votes/number]
  1=   e#     Select: ["party"/number votes/number] -> votes/number
  ~    e#     Bitwise NOT.
}$     e#
<      e# Keep only the elements that correspond to seats.
:(     e# Shift each array.
       e# RESULT: S := [[number] ["party" votes] [number] ["party" votes] ...]
f{     e# For each A := ["party" votes]:
       e#     Push S.
  1$   e#     Push a copy of A.
  e=   e#     Count the occurrences of A in S.
  1\t  e#     Replace the vote count with the number of occurrences.
  p    e#     Print.
}      e#
\$\endgroup\$
6
\$\begingroup\$

Pyth, 36 bytes - 20% = 28.8

J<_hCo/@eCQhNheN.S*UQUvzvz.e,b/JkhCQ

This qualifies for the bonus.

Try it online: Demonstration or Test harness

Explanation:

                                       implicit: z = 1st input (as string)
                                                 Q = 2nd input (evaluated)

                      vz               evaluate z (#seats)
                     U                 generate the list [0,1,...,seats-1]
                   UQ                  generate the list [0,1,...,len(Q)-1]
                  *                    Cartesian product of these lists
                .S                     shuffle (necessary for break ties randomly)
     o                                 order these tuples N by:
        eCQ                               list of votes
       @   hN                             take the N[0]th vote count
      /      heN                          and divide by N[1]+1
   hC                                  extract the party index of the tuples
  _                                    reverse the list
 <                      vz             take the first #seats elements
J                                      and store them in J

                          .e     hCQ   enumerated map over the names of the parties
                                       (k = index, b = name):
                            ,             generate the pair:
                             b/Jk            name, J.count(k)
                                       print implicitely
\$\endgroup\$
  • \$\begingroup\$ J is unnecessary. You can get rid of it and save 2 bytes. \$\endgroup\$ – isaacg May 24 '15 at 16:55
  • \$\begingroup\$ Also, if you swap z and Q, and then save Cvz to K, you can save another byte. \$\endgroup\$ – isaacg May 24 '15 at 16:58
  • \$\begingroup\$ @isaacg Nope, it is very important. Because of the shuffling the expression might yield different results in .e and it messes up the counting. \$\endgroup\$ – Jakube May 24 '15 at 17:00
  • 1
    \$\begingroup\$ Actually, the second tip doesn't work either, sorry, because I missed the UQ. \$\endgroup\$ – isaacg May 24 '15 at 17:01
  • 2
    \$\begingroup\$ @isaacg Post it as an answer. \$\endgroup\$ – Jakube May 24 '15 at 17:26
5
\$\begingroup\$

Javascript, 210 bytes

v=(a,b,c,d,e,f,g)=>{d=Object.assign({},b),c={};for(g in b)c[g]=0;for(;a--;)e=0,f=Object.keys(d),f.forEach(a=>e=d[a]>e?d[a]:e),f=f.filter(a=>d[a]===e),f=f[~~(Math.random()*f.length)],d[f]=b[f]/-~++c[f];return c}

Notes:

  • Requires a modern browser/engine with support for ES6. Tested in Firefox.
  • Uses the very important /-~++ operator :)

Example usage:

v(25, {cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013})
\$\endgroup\$
  • 1
    \$\begingroup\$ It's not necessary to declare all of your variables as arguments. \$\endgroup\$ – nderscore May 24 '15 at 19:50
  • 2
    \$\begingroup\$ Yes, but I wanted to avoid polluting the global scope of possible \$\endgroup\$ – user2951302 May 24 '15 at 20:16
  • 1
    \$\begingroup\$ JS golf is all about polluting the gobal scope :) \$\endgroup\$ – nderscore May 24 '15 at 23:13
  • 2
    \$\begingroup\$ I've golfed your method down to 168 bytes. Sorry for mangling the variable names. F=(N,X)=>{for(t=[o={}],[t[o[j]=0,j]=X[j]for(j in X)];N--;t[z=y[new Date%y.length]]=X[z]/-~++o[z])m=0,y=[(m=m<t[j]?t[j]:m,j)for(j in X)],y=y.filter(j=>t[j]==m);return o} \$\endgroup\$ – nderscore May 25 '15 at 0:44
4
\$\begingroup\$

Pyth - 54 bytes

AGZQ=kZK*]0lZVGJhOfqeTh.MZZ.e(kb)Z XJK1 XZJ/@kJ+@KJ1;K

Input format (stdin):

[25,[12984,7716,13009,4045,1741,1013]]

Output format (stdout):

[8, 5, 9, 2, 1, 0]

Variables used:

G = total number of seats
K = array of seats currently assigned to each party
k = number of votes for each party
Z = k/(K+1)
J = which party should have the next seat
\$\endgroup\$
  • \$\begingroup\$ Use vz and Q instead of G and Z. This way you will save the assignment with A. \$\endgroup\$ – Jakube May 24 '15 at 15:43
2
\$\begingroup\$

Perl, 110

#!perl -pa
$n=pop@F;@x=map
0,@F;/a/,$x[$'/$n]++for(sort{$b-$a}map{map{($'/$_|0).rand.a.$i++}//..$n}@F)[0..$n-1];$_="@x"

Input space separated with the seat count last.

Try me.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.