Problem Set 1: How Close Was That Election?

The questions below are due on Monday April 06, 2020; 11:00:00 PM.
 
**Pset Due:** Monday, April 06 at 11:00PM EST
** There will be no checkoff for this pset. **
Download Files

Objectives:

• You may work with other students. However, each student should write up and hand in
• his or her assignment separately. Be sure to indicate with whom you have worked in the comments of your submission.

Collaboration:

• Students may work together, but students are not permitted to look at or copy each other’s code or code structure.
• Each student should write up and hand in their assignment separately.
• Include the names of your collaborators in a comment at the start of each file.
• Please refer to the collaboration policy in the Course Information for more details.

Introduction: A Look Into Election Results

In the United States, presidential elections are determined by a majority Electoral College vote. For this problem set, we’re going to see if it is possible to change the outcome of an election by moving voters around to different states. Given simplified election results dating back to 2008, your job is to find how close an election really was by finding the smallest number of voters needed to change an election outcome by relocating to another state. This is an interesting variation of the complementary knapsack problem presented in class, which we will explore more thoroughly below. You may find 6.0002 Lecture 1 to be helpful for this problem set.

Getting Started:

Download ps1.zip from the problem set website. This folder contains the following files:

• ps1.py​: code skeleton
• state.py​: helper class representing the election results for a given state.
• test_ps1.py: basic tests for your code
• 600_results.txt, 2008_results.txt, 2012_results.txt, 2016_results.txt: files with election result data

Make sure all these files are saved in the same directory. Please do not rename these files, change any of the provided helper functions, change function names, or delete docstrings.

Please review the Style Guide for good coding practices.

---

1) Loading Election Data

In state.py, you’ll find that we have already implemented the State class for you. Familiarize yourself with the class, as you’ll find it helpful throughout the pset.

In this problem, we will implement a function that allows us to load election results from tab-delimited data files containing election data. We will be storing information regarding a state using the State class, given to you in state.py.

Each line in a data file contains the following information, each separated by a tab character:

• State name (2-letter state abbreviation),
• # Democrat votes,
• # Republican votes,
• # Electoral College votes

Each file begins with a header, that you should ignore when loading the election. Here are the first few lines of 2012_results.txt:

State   Democrat    Republican  EC_Votes
AL	795696		1255925	9
AK	122640		164676		3
 

Implement the function get_election(filename) It should take in the data text filename as a string, read its contents, and return a list of corresponding State objects.

Hint: If you don’t remember how to read lines from a file, check out the online Python documentation here

Some functions that may be helpful: str.split, open, file.readline

Example: Check that your implementation is correct by running the following lines on your console, also located at the bottom of ps1.py under if __name__ == "__main__" :

>>> election = get_election("2012_results.txt")
>>> print(len(election))
51
>>> print(election[0])
In AL, 9 EC votes were won by gop by a 460229 vote margin.

You should now pass the test `test_1_get_election` in **test\_ps1.py**.

---

2) Election Helper Functions

You will now implement several functions that will be useful for the remainder of the problem set.

For election_outcome(election), fill in the function such that it returns ('dem', 'gop') if the Democratic candidate won the election (i.e. receives** more electoral college (EC) votes** than the GOP candidate), or ('gop','dem') if the GOP candidate won. You may assume that there will be no ties.

For winning_candidate_states(election), fill in the function such that it returns a list of states won by the winning candidate.

For reqd_ec_votes(election), fill in the function such that it returns the number of additional Electoral College votes required by the losing candidate in order to win. To win, a candidate must have 1 more than half the total number of EC votes, i.e. if there are 538 electoral votes, a candidate must have >= 270 electoral votes in order to win the election.

Implement the election_outcome(election), winning_candidate_states(election), and reqd_ec_votes(election)functions.

Example: Check that your implementation is correct by running the following lines on your console, also located at the bottom of ps1.py under if __name__ == "__main__" :

>>> winner, loser = election_outcome(election)
>>> print("Winner:", winner, "\nLoser:", loser)
Winner: dem
Loser: gop
>>> won_states = winning_candidate_states(election)
>>> names_won_states = [state.get_name() for state in won_states]
>>> print("States won by the winner: ", names_won_states)
States won by the winner: ['CA', 'CO', 'CT', 'DE', 'DC', 'FL', 'HI', 'IL', 'IA', 'ME', 'MD', 'MA', 'MI', 'MN', 'NV', 'NH', 'NJ', 'NM', 'NY', 'OH', 'OR', 'PA', 'RI', 'VT', 'VA', 'WA', 'WI']
>>> ec_votes_needed = reqd_ec_votes(election)
>>> print("EC votes needed:",ec_votes_needed)
EC votes needed: 64

You should now pass the test cases `test_2_election_outcome`, `test_2_winning_candidate_states`, and `test_2_reqd_ec_votes` in **test_ps1.py**.

---

3) Greedy Election

We will first use a greedy algorithm to explore how to flip the election result by relocating voters to different states. Our goal is to find “swing states,” a subset of states from winner_states where voters can be relocated into to flip the election. A greedy method to achieve this is:

1. Look at the subset of states that were won by the original winner of the election (returned by winning_candidate_states).
2. Choose the state with the narrowest win margin. If there are ties, choose the state that appears first alphabetically. Assume that we add just enough new voters from the opposing party (i.e. original loser of the election) in order to change the winner of that state. The original loser of the election should now receive the state’s EC votes.
3. Continue selecting state with the next lowest margin until the original loser of the election reaches (or just exceeds) reqd_votes (the output of reqd_ec_votes).

Hint: You may find it easier to first sort the list of states in increasing order based on their margin. For a custom class, such as State, the built-in lt() method is used to determine order when sorting a list of State objects. If you don’t remember how to sort a list, check out the following.

For example, if you have state A with 2 EC votes that won by a margin of 1000, and state B with 20 EC votes that won by a margin of 2000, the greedy algorithm would choose state A since it had the narrowest win margin (1000<2000).

Implement a greedy algorithm for moving voters in greedy_swing_states. The function should return a list of swing states where voters should be moved into. This should only return a subset of States that were originally lost by the losing candidate in the election (returned by winning_candidate_states). Return an empty list if there are no swing states.

Example: Check that your implementation is correct by running the following lines on your console, also located at the bottom of ps1.py under if __name__ == "__main__" :

>>> greedy_swing = greedy_swing_states(won_states, ec_votes_needed)
>>> names_greedy_swing = [state.get_name() for state in greedy_swing]
>>> print("Greedy swing states results:", names_greedy_swing)
Greedy swing states results: ['NH', 'NV', 'FL', 'DE', 'NM', 'IA', 'VT', 'ME', 'RI']
>>> voters_greedy = sum([state.get_margin()+1 for state in greedy_swing])
>>> ecvotes_greedy = sum([state.get_num_ecvotes() for state in greedy_swing])
>>> print("Greedy voters displaced:", voters_greedy, "for a total of", ecvotes_greedy, "Electoral College votes.")
Greedy voters displaced: 768385 for a total of 64 Electoral College votes.

You should now pass `test_3_greedy_swing_states` in **test_ps1.py**.

---

4) Dynamic Programming Election Shuffling

In the problem above, our greedy algorithm makes a series of locally optimal choices. However, in some cases, this may not lead to the overall optimal solution. For instance, consider the results of the 2012 election. The greedy algorithm returns [NH, NV, FL, DE, NM, IA, VT, ME, RI] for our swing states, requiring a total of 768,385 voters necessary to shift the election outcome. A dynamic programming algorithm that returns the optimal solution instead finds the list [FL, NH, OH, VA], needing only 429,526 voters to be displaced.

We will set up this problem as the complementary knapsack problem. We want to find a subset of winner_states (ie. swing states) which collectively contribute at least the minimum required number of EC votes to flip the election outcome, while moving as few total voters into these states. Think of each State as a potential object to include in your knapsack collection, the State’s number of ec_votes as its weight, and the State’s margin plus one (voters moved in to flip) as its value. Finding the optimal swing states is the complementary knapsack problem as we are trying to MINIMIZE the total value (voters moved) of our knapsack while staying ABOVE a certain threshold for total weight (ec_votes). It is different from the original knapsack problem that tries to MAXIMIZE the total value (voters moved) of our knapsack while staying BELOW a certain threshold total weight (ec_votes).

We will divide this problem into two parts that together will solve the complementary knapsack problem. First, we will implement a dynamic programming algorithm to solve the original knapsack problem in move_max_voters. Then we will take the complement of the list returned in move_max_voters to get our final solution in move_min_voters.

4a) Move_max_voters

Implement a dynamic programming algorithm in move_max_voters to find the list of States with the largest number of total voters needed to relocate in order to get AT MOST ec_votes. If every state has a number of EC votes that is greater than ec_votes, return the empty list.

A move_max_voters solution that does not use dynamic programming will receive zero points for this problem.

Notes:

• If you try using a brute force algorithm or plain recursion on this problem, it will take a substantially long time to generate the correct output.
• You may implement your algorithm using the top-down recursive method with memoization as shown in lecture, or the bottom-up tabulation method as explained in the texbook. If using a top-down method, it may be helpful to create a helper function.
• The memo parameter in move_max_voters is optional. You may or may not need to use this parameter, depending on your implementation. You should NOT change the default parameter value.
• If you decide to use the memo parameter, check if it is set to the default parameter, None. If it is, re-assign memo to an empty dictionary inside the function body. Note that directly using the empty dictionary (or any mutable object) as the default parameter value could lead to undesirable behavior.

Example: Check that your implementation of move_max_voters is correct by running the following lines on your console, also located at the bottom of ps1.py under if __name__ == "__main__" :

>>> total_lost = sum(state.get_num_ecvotes() for state in won_states)
>>> non_swing_states = move_max_voters(won_states, total_lost-ec_votes_needed)
>>> non_swing_states_names = [state.get_name() for state in non_swing_states]
>>> print("States with the largest margins:", non_swing_states_names)
States with the largest margins: ['WI', 'WA', 'VT', 'RI', 'PA', 'OR', 'NY', 'NM', 'NJ', 'NV', 'MN', 'MI', 'MA', 'MD', 'ME', 'IA', 'IL', 'HI', 'DC', 'DE', 'CT', 'CO', 'CA']
>>> max_voters_displaced = sum([state.get_margin()+1 for state in non_swing_states])
>>> max_ec_votes = sum([state.get_num_ecvotes() for state in non_swing_states])
>>> print("Max voters displaced:", max_voters_displaced, "for a total of", max_ec_votes, "Electoral College votes.", "\n")
Max voters displaced: 11353398 for a total of 268 Electoral College votes.

4b) Move_min_voters

Our dynamic programming function, move_max_voters, provides us with the list of states that maximizes the total voters moved while staying below some threshold total number of EC votes. By passing in carefully chosen parameters when calling move_max_voters in move_min_voters, we can use the resulting list to indirectly determine our list of swing states to flip the election result.

Consider the 2012 election. In winner_states, Obama is the original winner and Romney is the original loser. winner_states are either kept by Obama (non-swing), or flipped to Romney (swing).

If we set the threshold number of EC votes as the maximum number of EC votes that Obama can still keep from the original total EC votes in winning_candidate_states while still ensuring that Romney has enough EC votes to win the election, move_max_voters will return the non-swing states. The swing-states are the states in
winner_states that aren’t in the list of non-swing states, i.e the complement of move_max_voters. These swing-states minimize voter movement to flip the election.

Implement move_min_voters which returns a list of States that comprise our “swing states.” Swing states should include the states that require the minimum numbers of total voters to be relocated in order for the original election loser to win the required number of EC votes to win the election.

Hints:

• This function should be relatively simple. If you are having trouble getting started talk to us at OH.
• Consider the full list of states won by Obama and remove the states that Obama should continue to win (the non-swing states). The remaining states are ones that Romney should now win (i.e. the swing states).
• This function should call move_max_voters, with the parameter ec_votes set to (total #EC votes won by Obama – reqd_votes).
• move_min_voters is analogous to the complementary knapsack problem that was discussed in lecture. move_max_voters solves the associated knapsack problem.

Check that your implementation of move_min_voters is correct by running the following lines on your console, also located at the bottom of ps1.py under if __name__ == "__main__" :

>>> swing_states = move_min_voters(won_states, ec_votes_needed)
>>> swing_state_names = [state.get_name() for state in swing_states]
>>> min_voters_displaced = sum([state.get_margin()+1 for state in swing_states])
>>> swing_ec_votes = sum([state.get_num_ecvotes() for state in swing_states])
>>> print("Complementary knapsack swing states results:", swing_state_names)
Complementary knapsack swing states results: ['FL', 'NH', 'OH', 'VA']
>>> print("Min voters displaced:", min_voters_displaced, "for a total of", swing_ec_votes, "Electoral College votes. \n")
Min voters displaced: 429526 for a total of 64 Electoral College votes.

You should now pass **test_4_move_max_voters** and **test_4_move_min_voters** in **test_ps1.py**. If you fail these, this is a sign that your dynamic programming solution is not correct. Feel free to ask for help during office hours, We’re here to help :)!

---

5) Valid Voter Shuffling

In Problems 3 and 4, we found the swing states that could be targeted in order to flip the election. The swing states were won by the original election winner, but we want to move voters into these swing states in order to flip the outcome of the election. In this problem, you will find a valid way to move voters from states that were won by the original election loser to each of the states in our swing states. However, you must consider that residents of New York, Washington, Massachusetts, and California have a lot of state pride and would **not** be willing to move to any state.

Your task is to find a mapping of the form {(from_state, to_state): voters_moved} indicating the number of voters being moved from a state won by the original election loser to a swing state. To flip the outcome of the swing state, (margin + 1) new voters must relocate to that state.

This is an open-ended problem and there are many correct ways to approach it. Here is one:

1. Find the list of states that were won by the election loser, let’s call these the losing_candidate_states. These are the states we will move voters from.
2. Go through each state in swing_states, and move just enough voters from the losing_candidate_states into this state to upset the winner of the state.

• For each state in swing_states, you’ll need state.get_margin()+1 voters to relocate to that state in order to upset the winner of the state.
• For each state in the losing_candidate_states, you may not relocate more than state.get_margin()-1 voters. As that would change the outcome of the election of that state.

Important Notes:

• States that were won by the original losing candidate should continue to be won by the original losing candidate after voter shuffling (margin must be greater than 0).
• One state can supply voters for multiple states.
• Multiple states can supply voters for one state.
• Remember that you cannot move residents from NY, WA, MA or CA.
• You may mutate the election data if you choose!

_Implement shuffle_voters(election, swing_states). The function should return a tuple with (1) a dictionary with keys (from_state, to_state) and their corresponding voters_moved values, (2) the number of Electoral College votes gained by the shuffling, and (3) the number of relocated voters necessary. If there is no valid way to reshuffle voters, returns None. _

You can test your implementation of shuffle_voters by running the test file. There are multiple correct reshuffling of voters that satisfies the requirements and flips the result of the election.

You should now pass `test_5_shuffle_voters` in **test\_ps1.py**.

Hand-In Procedure

1. Time and Collaboration Info

At the start of ps1.py, in a comment, write down the number of hours (roughly) you spent on the problems in that part, and the names of the people you collaborated with. For example:

  # Problem Set 1
  # Name: Jane Lee
  # Collaborators: John Doe
  # Time: 8 hours

2. Sanity checks

After you are done with the problem set, run your files and make sure they run without errors. Make sure that any calls you make to different functions are under if __name__ == '__main__'. Be sure to run test_ps1.py and make sure all the tests pass.

Note: Passing all of the tests in test_ps1.py does not necessarily mean you will receive a perfect score. The staff will run additional tests on your code to check for correctness.

6) Submission

Be sure to run test_ps1.py and make sure all the tests pass.
The tester file contains a subset of the tests that will be run to determine the problem set grade.

You may upload new versions of each file until the deadline, but anything uploaded after that time will be counted towards your late days, if you have any remaining. If you have no remaining late days, you will receive no credit for a late submission.

Note on submitting: Simply Select the file and it will automatically be uploaded to the website. No further action is needed!

MAKE SURE YOU ARE LOGGED IN