House Of Representatives
April 12, 2011
The United States counts its citizens every ten years, and the result of that census is used to allocate the 435 congressional seats in the House of Representatives to the 50 States. Since 1940, that allocation has been done using a method devised by Edward Huntington and Joseph Hill that minimizes percentage differences in the sizes of the congressional districts.
The Huntington-Hill method begins by assigning one representative to each State. Then each of the remaining representatives is assigned to a State in a succession of rounds by computing for each State, where n is the current number of representatives (initially 1), p is the population of the State, and g(n, p) is the State’s population divided by the geometric mean of the current number of representatives and the number of representatives that the State would have if it was assigned the next representative. The geometric mean g(n, p) is calculated for each State at each round and the representative assigned to the State with the highest geometric mean g(n, p).
For instance, once each State has been assigned one representative, the geometric mean g(n, p) for each State is its population divided by the square root of 2. Since California has the biggest population, it gets the 51st representative. Then its geometric mean is recalculated as its population divided by the square root of 2 × 3 = 6, and in the second round the 52nd representative is assigned to Texas, which has the second-highest population, since it now has the largest geometric mean g(n, p). This continues for 435 − 50 = 385 rounds until all the representatives have been assigned.
Your task is to compute the apportionment of seats in the House of Representatives; the population data is given on the next page. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
[…] today’s Programming Praxis exercise, our goal is to calculate the amount of seats each state gets in the […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/12/programming-praxis-house-of-representatives/ for a version with comments):
A Python solution:
My solution and first attempt to play with upcoming C++0x standard (compiles nicely with GCC version 4.5): github
Thought I should admit that before posting I have read the solution and understood that using sorted vector and insertion via lower_bound function is not as nice as using priority queue :)
For this one I reformatted the source file as:
Alabama: 4779736
Alaska: 710231
Arizona: 6392017
…
My Python solution.
My original solution involved a
State class, but pylint objected that it didn't have enough public methods to warrant its own class.
Apologies for the incorrectly clsoed “code” tag above; only
State
should be tagged.Note that in python’s heapq module, heappop returns the smallest item. Here we want the state with the largest geomean. So we use -geomean to get the desired ordering.
Interstingly, Montana has the lowest representation, with 1 rep per 989k people, and Rhode Island has the highest, with 1 representative per 526k people.
Not very ruby like in some ways (use of arrays) but pretty darn small …
I set the number of representatives to 1 in the initial data. The tricky line is line 23, so let’s step through it. We know we have 385 representatives left so we’ll go through each of them. The next piece is the collect which will generate an array of the g(n, p) values. We then do the each_with_index.max which returns an array of the maximum and the index of the maximum and we grab the index out of the [1] value. We then add 1 to the [2] value (representatives) of the state_pop_data array.
My try in REXX
Factor language code. Kind of clunky since heaps are not treated as sequences, so result needs to be converted to an array for printing. Also more stack shuffling than usual is used here.
( scratchpad ) house
California 53
Texas 36
New York 27
Florida 27
Illinois 18
Pennsylvania 18
Ohio 16
Michigan 14
Georgia 14
North Carolina 13
New Jersey 12
Virginia 11
Washington 10
….
In F#,
In scala. It could be a bit shorter if I made seats mutable in the State class. Now I have to remove the old State from the List and add the one with the added seat. Not very efficient :)