logo CodeStepByStep logo


Language/Type: C++ map collections STL
Related Links:

Write a function named gerrymanderingRatios that examines an input file of voting data to calculate whether voting districts have been created in a way that gives an unfair advantage to a particular political party.

Districting is the process by which a US state is divided into voting regions called districts. During an election, the candidate who earns the largest number of votes in a district (the "plurality" of votes) is elected as that district's representative. Gerrymandering is a malicious process of trying to draw district boundaries in such a way as to give one party more representatives than their fair share. For example, if you spread the voters from a given party too thinly across many districts, they will not have enough votes to win a majority in any district. Similarly, if you too tightly pack the voters from a political party all into a small number of districts, all votes over the needed plurality (e.g. 50% in a two-party system) are wasted.

In the figure below, the square area of Democrat (D) and Republican (R) voters are divided into 5-person districts. The districting at left leads to 4/5 of the districts won by Democrats, while the districting at right is the opposite, awarding 4/5 of the districts to Republicans. These both seem unfair given the nearly equal total count of voters from the two parties.

gerrymandered toward D (left) and toward R (right)

For this problem let us define the "Gerrymandering ratio" as a measure of a given political party's performance in a given districting arrangement. It is computed by dividing the % of districts that party won by that party's % of the total vote. A ratio of 1.0 would be perfect representation. If the ratio is far above 1.0 for a given party, it implies that the districting was gerrymandered to favor that party. Similarly, if the ratio is far below 1.0, that party might be disadvantaged.

Gerrymandering Ratio for a Party
(Percent of districts where that Party won a majority of the vote)
(Percent of total votes won by that Party)

Your function accepts as its parameter a string representing a filename of an input file representing voting data. The box above at right shows an example contents of such a file. Each line of the input file will contains information about one voting district. First will be a single word token representing that district's name, followed by each individual vote from that district, each separated by a single space. The votes will be single uppercase characters indicating the political party of interest, such as D or R.

District1 D R D D D
District2 R D R R
District4 D D R R D R D
district5 D D R D R

Your job is to calculate the gerrymandering ratio for every political party that is represented in the data set. You should return this information as a map from each political party name (a string) to that party's gerrymandering ratio (a real number). For example, if the input file stream for the file above on the right is passed to your function, your code should determine that the D votes (Democrats) make up 12/26 (46.1%) of the total voters, but Democrats won 3/5 (60%) of the districts by majority vote. This means that the gerrymandering ratio for "D" party is 60 / 46.1, or roughly 1.3. You can perform a similar calculation for the other party in the data set, R, representing the Republicans, which would reveal a ratio of roughly 0.74. Based on this information, your function would return the following map:

{"D":1.3, "R":0.742857}

Assumptions: You may assume valid file input, that the file exists and exactly follows the format shown, with party votes in uppercase. You may assume that there is at least one line of district data in the file and that every district has at least one voter, though the districts might not all be the same size. You may assume that there are at least 2 political parties represented, though there might be more than 2 parties. Do not assume that the parties will be named "D" and "R".

Constraints: Choose an efficient solution. Choose data structures intelligently and use them properly. While your code is not required to have any particular Big-Oh, you may lose points if your code is extremely inefficient. Do not read the file more than once. Do not define custom classes/structures; solve this problem using the Stanford or STL collections.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.