9
\$\begingroup\$

Given a list of the populations of each state, output, from greatest to least, the number of votes that state gets in the electoral college.

Input: The first number represents the total number of votes to distribute; it is followed by a list of and populations. In this example, abbreviations for states are used, but any name containing uppercase and lowercase letters could be used. You can take this in any format you like, as long as the only information contained is the state's abbreviation and its population.

Input may be taken as arguments to a function, or any way you want.

Example (possible) input: 538 [[CA 38000000], [NH 1300000] etc.]

Output: Output, in some format, the number of votes each state gets. Order the states from greatest to least. If two states have the same number of votes, order by whichever name would come first in a dictionary (which comes first alphabetically).

Before finding the number of votes, first check if there is a state named DC in the list of inputs, and if there is, give the state 3 votes, regardless of its population. Then, remove it from the list and assign the rest of the votes as though DC didn't exist.

The number of votes in the electoral college is defined to be the sum of the number of senators and representatives. Every state gets two senators, so subtract twice the number of states from the total (538, in the example input) to get the number of representatives. Assign every state one representative to start. Then, perform the following process:

  1. Assign each state a number, A, defined to be P/sqrt(2) where P is the population.

  2. Sort the states according to their values of A.

  3. Assign the first state (the one with the largest A) one more representative.

  4. Reassign values of A, as A = P/(sqrt(n)*sqrt(n + 1)), where n is the current number of representatives assigned to the state.

  5. Go back to step 2. Repeat until all representatives have run out.

Example (possible) output: {CA: 518, NH: 20}. The output doesn't have to be in this format, but must contain the same information.

Note that if it is not possible to assign votes legally because there are less than 3*(# of states) votes, print whatever you want. You can crash, throw an error, etc.

Test cases:

538 [['CA' 38000000], ['NH' 1300000]] --> CA: 518, NH: 20
538 [['NH' 1300000], ['CA' 38000000]] --> CA: 518, NH: 20 (must be in order from greatest to least!)
538 [['DC' 1000000], ['RH' 1]] --> RH: 535, DC: 3
100 [['A', 12], ['B', 8], ['C', 3]] --> A: 51, B: 35, C: 14
100 [['A', 12], ['B', 8], ['C', 3], ['D', 0]]: --> [49, 34, 14, 3] (yes, even states with no population get votes)
2 [['A', 1]] --> aasdfksjd;gjhkasldfj2fkdhgas (possible output)
12 [['A', 1], ['B', 2], ['C', 3], ['D', 4]] --> A: 3, B: 3, C: 3, D: 3
42 [['K', 123], ['L', 456], ['M', 789]] --> M: 23, L: 14, K: 5
420 [['K', 123], ['L', 456], ['M', 789]] --> M: 241, L: 140, K: 39
135 [['C', 236841], ['D', 55540], ['G', 70835], ['K', 68705], ['M', 278514], ['Ms', 475327], ['Nh', 141822], ['Nj', 179570], ['Ny', 331589], ['Nc', 353523], ['P', 432879], ['R', 68446], ['Sc', 206236], ['Ve', 85533], ['Vi', 630560]] --> Vi: 20, Ms: 16, P: 14, Nc: 12, Ny: 12, M: 10, C: 9, Sc: 8, Nj: 7, Nh: 6, Ve: 5, D: 4, G: 4, K: 4, R: 4
\$\endgroup\$
  • \$\begingroup\$ After checking the expected output and comparing my code with it, the step that says "Reassign values of A, as A = P/(sqrt(n)*sqrt(n + 1)), where n is the current number of members assigned to the state." should be changed to "Reassign values of A, as A = P/(sqrt(n)*sqrt(n + 1)), where n is the current number of representatives assigned to the state.". That threw me off. \$\endgroup\$ – Patrick Roberts Jan 25 '16 at 8:41
  • \$\begingroup\$ What should happen if the number of states is more than half the number of votes? \$\endgroup\$ – msh210 Jan 25 '16 at 22:33
3
\$\begingroup\$

Clean, 263 244 222 bytes

v n s=sortBy(\(a,b)(c,d).b>d)([(t,3.0)\\t<-s|fst t=="DC"]++w(n-3*(length s))[(t,1.0)\\t<-s|fst t<>"DC"])
w 0s=w 0 s=[(p,r+2.0)\\(p,r)<-s]
w n s#s=sortBy(\a b.A a>A b)s
#(p,r)=hd s
=w(n-1)[(p,r+1.0):tl s]
A((_,p),r)=p/sqrt(r*r+r)

Call like

Start = v 538 [("DC", 1000000.0), ("RH", 1.0)]

Ungolfed version, full program (census.icl):

module census

import StdEnv

Start = votes 538 [("DC", 1000000.0), ("RH", 1.0)]

votes n states
# dc = filter (((==)"DC")o fst) states
= sortBy (\(a,b)(c,d).b>d) ([(t,3.0) \\ t <- dc] ++ votes` (n-3*length states) [(t,1.0)\\t<-removeMembers states dc])
where
    votes` 0 states = map (\(p,r).(p,r+2.0)) states
    votes` n states
    # states = sortBy (\a b.A a > A b) states
    # (p,r) = hd states
    = votes` (n-1) [(p,r+1.0):tl states]

    A ((_,p),r) = p / sqrt(r*r+r)
\$\endgroup\$
2
\$\begingroup\$

JavaScript ES6, 249 bytes 244 bytes

(r,s)=>{r-=s.length*3;s=s.map(t=>({s:t[0],p:t[1],a:t[1]/(q=Math.sqrt)(2),r:1}));while(r--)(t=>t.a=t.p/q(++t.r)/q(t.r+1))(s.filter(t=>t.s!='DC').sort((a,b)=>b.a-a.a)[0]);return''+s.sort((a,b)=>(r=b.r-a.r)?r:a.s>b.s?1:-1).map(t=>t.s+':'+(t.r+2))}

Test cases

d = (r, s) => {
  r -= s.length * 3;
  s = s.map(t => ({
    s: t[0],
    p: t[1],
    a: t[1] / (q = Math.sqrt)(2),
    r: 1
  }));
  while (r--)(t => t.a = t.p / q(++t.r) / q(t.r + 1))(s.filter(t => t.s != 'DC').sort((a, b) => b.a - a.a)[0]);
  return '' + s.sort((a, b) => (r = b.r - a.r) ? r : a.s > b.s ? 1 : -1).map(t => t.s + ':' + (t.r + 2))
};

document.write(
  '<pre>' +
  d(135, [
    ['C', 236841],
    ['D', 55540],
    ['G', 70835],
    ['K', 68705],
    ['M', 278514],
    ['Ms', 475327],
    ['Nh', 141822],
    ['Nj', 179570],
    ['Ny', 331589],
    ['Nc', 353523],
    ['P', 432879],
    ['R', 68446],
    ['Sc', 206236],
    ['Ve', 85533],
    ['Vi', 630560]
  ]) +
  '</pre>'
);

Credit to @Neil for saving 5 bytes!

\$\endgroup\$
  • \$\begingroup\$ .some((t,i)=>t.a=t.p/q(++t.r)/q(t.r+1)) would save you a byte if it works. \$\endgroup\$ – Neil Jan 25 '16 at 9:18
  • \$\begingroup\$ @Neil That doesn't do the same thing. The point is, that the 0th index is the only one whose representative attribute r is incremented each time. \$\endgroup\$ – Patrick Roberts Jan 25 '16 at 9:20
  • \$\begingroup\$ That's why I used .some and not .map. \$\endgroup\$ – Neil Jan 25 '16 at 9:21
  • \$\begingroup\$ Oh, yeah, 5 bytes, because you don't use i any more. Nice! \$\endgroup\$ – Neil Jan 25 '16 at 9:37
  • \$\begingroup\$ @Neil I just realized this wouldn't work for a scenario in which the state population is 0. Updating to alternate solution with equivalent bytes. \$\endgroup\$ – Patrick Roberts Jan 25 '16 at 9:44
1
\$\begingroup\$

Python 2, 219 bytes

v,s=input()
n={k:1 for k in s}
v-=3*len(s)
l=lambda x:-x[1]
if'DC'in s:del s['DC']
while v:A,_=sorted([(a,s[a]/(n[a]**2+n[a])**.5)for a in s],key=l)[0];n[A]+=1;v-=1
for a in n:n[a]+=2
print sorted(list(n.items()),key=l)

Takes input as

420,{'K':123,'L':456,'M':789}

Prints:

[('M', 241), ('L', 140), ('K', 39)]
\$\endgroup\$
  • \$\begingroup\$ I always found it funny how writing a full program in Python is almost always less bytes than writing a function because of indentation being a mandatory part of the syntax. \$\endgroup\$ – Patrick Roberts Feb 2 '16 at 4:29

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.