练习list的使用方法，实现Rank Ballot, Range Ballot, Approval Ballot和Single-candidate Ballot四种选举方法。
Requirement
In Assignment 2, you will work with a dataset that contains voting data from a Canadian election. You can complete the whole assignment with only the concepts from Weeks 1 through 6 of the course.
Goals of this Assignment
In completing Assignment 2, you will practice with the following concepts we have seen in the course so far:
- You will continue to use the Function Design Recipe to document, write, and test functions.
- You will write code that uses loops and the list data type in a variety of ways (looping over lists, list methods, list indexing, etc.)
- You will apply what you’ve learned about mutability, writing functions that mutate input only when it is appropriate to do so
- You will write code that uses conditionals, strings, boolean expressions, and other concepts from Assignment 1 and earlier in the course.
- You will reuse functions to help implement other functions according to their docstring description
- You will read a problem description in English and provided docstring examples, and implement function bodies to solve the problem according to these specifications
- You will continue to use Python 3, Wing 101, a checker module, and other tools
Background Information
Voting theory is the study of voting systems. A voting system is an algorithm for computing the winner of an election given a list of candidates and a set of ballots. For example, you may be familiar with the Plurality voting system: each voter marks their ballot for exactly one candidate, and the candidate with the most votes is elected.
There are dozens of different voting systems and many different types of ballots. In this assignment, we’ll be investigating five systems (Plurality, Approval Voting, Range Voting, Borda Count, and Instant Run-Off) that use four different types of ballots.
In case you’re curious, we have provided a table showing you where each voting system is used. (This is only for the curious since everything you need to know about each voting system and Canadian elections is contained within this handout.)
Canadian Elections: Ridings, Members of Parliament, and the House of Commons
Canada is divided into 338 geographical areas called ridings. In a standard Canadian election, one candidate from each political party runs in each riding. Each riding’s voters elect one of these candidates to the government using the Plurality voting system. These elected Members of Parliament (MPs) get a seat in the House of Commons. (So, there are 338 seats in the House of Commons.)
At present, there are five parties represented in the House of Commons; four of them put forward candidates in all provinces. To simplify the assignment somewhat, our simulation will include only those four parties:
- the Conservative Party of Canada (CPC) (Links to an external site.)
- the Green Party (Links to an external site.)
- the Liberals (Links to an external site.)
- the New Democratic Party (NDP) (Links to an external site.)
For the purposes of the assignment, we will not differentiate candidates from their parties; Ballots will include only the party names.
Files to Download
Starter Filesand extract the zip archive. A description of each of the files that we have provided is given in the paragraphs below.
Starter code: voting_systems.py
The voting_systems.py file contains some constants, some sample data, and function headers and docstrings for the functions you will write. For each function, read both the handout and the header and docstring (especially the examples) to understand what the function should do.
Data: sample_votes.csv
The sample_votes.csv file contains vote data in comma-separated values (CSV) format. You must not modify this file.
Simulation code: voting_simulation.py
The voting_simulation.py file will let you run a simulation that uses the code you write in voting_systems.py. You will not be submitting this file and there is no need to change it.
Checker: a2_checker.py
As we did in Assignment 1, we have provided a checker program (a2_checker.py) that you can run on your own computer before submitting your assignment to MarkUs. There are some other files that will appear that we have included so that the checker runs properly. Do not edit them, and do not move or delete them.
Types of Ballots
Four types of ballots are used in this assignment. This section refers to the constant PARTY_ORDER, which you can find at the top of the voting_systems.py file.
The Data
For this assignment, you will use data from a Comma Separated Value (CSV) file named sample_votes.csv. Each row of this file contains the following information about a single voter:
- riding number: the number of the riding to which the voter belongs
- voter number: a number assigned to a voter
- rank ballot: the voter’s rank ballot
- range ballots: the voter’s range ballot
- approval ballots: the voter’s approval ballot
Notice that the row of data for each voter does not contain their singlecandidate ballot. We will determine their single-candidate ballot from their top choice in their rank ballot.
Custom Data Type
Within our code, the data from each row in sample_votes.csv will be represented as a list that contains ints (for riding number and voter number) and sublists (for representing each of the rank, range and approval ballots).
Within the starter code in voting_systems.py, we will refer to this data as VoteData in our type contracts.
What to do
Suppose you want to analyze how different voting systems change the results of elections. There are multiple voting systems to compare, and hundreds of votes and ridings to consider. To make your life easier, you will write Python functions to help you manage this information.
Assumptions and Preconditions
You do not need to write any preconditions in this assignment, as we have provided the docstrings for the required functions for you. If you choose to write any of your own helper functions, you should write complete docstrings for them.
To simplify the assignment, you can make the following assumptions:
- There will only ever be 4 parties, and their names in PARTY_ORDER and a cleaned VoteData list will always be uppercase. Note that while the given PARTY_ORDER list is sorted in alphabetical order, that may not always be the case.
- If ties occur, they should be broken by choosing the party that comes first in PARTY_ORDER. We suggest you write your code ignoring ties at first, then test to see what happens and then think about how to implement this tie-breaking if necessary.
- All lists representing a single rank, range, or approval ballot will have the same number of elements as PARTY_ORDER (i.e. 4).
Task 0: Creating testing data
We have provided you with docstrings in the starter code in voting_system.py, however many of the docstrings only have one example. We have provided you with one sample list of VoteData called SAMPLE_DATA_1. Your task here is to create a second list sample list called SAMPLE_DATA_2 that contains 3 VoteData items representing the data of the voters in the following image:
We have started this off for you, setting SAMPLE_DATA_2 to be an empty list in the starter code. As you work through the following tasks, start by adding a second example that uses SAMPLE_DATA_2 in any docstring that does not contain 2 examples.
Task 1: Data cleaning
The code we provided in voting_simulation.py reads data from a CSV file produces a List[List[str]]. Here is a sample of the kind of list returned.
You are to write the function clean_data, which should modify the list according to the following rules:
- ridings should be ints
- voter numbers should be ints
- rank ballots should be a list of strs
- range ballots should be a list of ints
- approval ballots should be a list of bools
After applying the clean_data function to the example list above, it should contain this.
Each of the three sublists above is of type VoteData.
You must not use the built-in function eval in clean_data. This function is one of the more challenging functions in A2, because it mutates a list. We suggest that you start with some of the other functions in Task 2, and come back to this one later.
Task 2: Data extraction
Once the data has been cleaned, you can use the following functions to extract information from your data.
You can work on these functions even before you have completed the clean_data function by working with the provided sample data in the starter code, and by creating your own small lists of clean vote data for testing.
See the docstrings in the starter code for examples of how to work with that data.
Note: For all the functions in this task, the arguments to the functions should NOT be mutated.
Task 3: Data analysis
Once the data has been cleaned and you are able to extract the specific data you need, you can write functions to analyze the vote data and figure out election results.
You can work on these functions even before you have completed the clean_data function by working with the provided sample data in the starter code, and by creating your own small lists of clean vote data for testing.
See the docstrings in the starter code for examples of how to work with that data.
Task 3.1: Plurality Voting System
The plurality voting system uses single-candidate ballots. Implement a function which counts all single-candidate ballots from our vote data, as described below.
Task 3.2: Approval Voting System
The approval voting system uses approval ballots. Implement a function which counts all approval ballots from our vote data, as described below.
Task 3.3: Range Voting System
The range voting system uses range ballots. Implement a function which counts all range ballots from our vote data, as described below.
Task 3.4: Borda Count Voting System
The Borda count voting system uses rank ballots. The Borda Count is determined by assigning points according to ranking. A party gets 3 points for each first-choice ranking, 2 points for each second-choice ranking and 1 point for each third-choice ranking. No points are awarded for being ranked fourth.
For example, the rank ballot [‘LIBERAL’, ‘GREEN’, ‘CPC’, ‘NDP’] would contribute 3 points to the Liberal count, 2 points to the Green count and 1 point to the CPC count.
Task 3.5: Instant Run-Off Voting System
The calculations involved in Instant Run-off Voting are considerably more complex than the previous voting systems. To help you implement this system, we have defined two helper functions that you must implement and use in your solution. If you are having trouble with this task, we recommend focusing on the other parts of the assignment first, and then returning to this later.
The Instant Run-Off Voting (IRV) system uses rank ballots, and does the counting as shown in the flowchart below. Initially, it considers only the first choice in the rank ballot of each voter. If this gives one party a majority (more than* 50% of the votes), then this party wins the seat. If not, the party with the fewest votes is removed from every ballot. For example, if ‘GREEN’ is removed from the rank ballot [‘NDP’, ‘GREEN’, ‘LIBERAL’, ‘CPC’], the ballot becomes [‘NDP’, ‘LIBERAL’, ‘CPC’]. The process is repeated with the new shorter ballots. (* Update (Oct 20): the provided example in the docstring should return ‘NDP’.
If you downloaded the starter code before Oct 21, you can update the example. Otherwise you will have downloaded the corrected version.)
Task 4: Determine winner
Most of the vote data analysis functions we wrote in Task 3 return a list of integers representing the vote points received by each party, corresponding to their order in the constant list PARTY_ORDER. With this list of points, we can determine the winner for that particular voting system.
The points_to_winner function is meant to take in a list of points and return the name of the winning party. Complete this function’s body as described below.
What not to do
As you’re coding, keep in mind the following rules:
- Do not add statements that call print, input, or open.
- Do not use any break or continue statements. We are imposing this restriction (and we have not even taught you these statements) because they are very easy to abuse, resulting in terrible code.
- Do not modify or add to the import statements provided in the starter code.
Note: Using Constants
As in Assignment 1, your code should make use of the provided constants for the indexes in VoteData and for other special strings in the uncleaned data.
This will not only make your code easier to read, but if the columns in the data moved around, your code would still work.
You should also make use of the constant PARTY_ORDER throughout your code. You should not assume it will have particular values in it (i.e. you should not hardcode strings like ‘GREEN’ in your code.)
Testing your Code
We strongly recommended that you test each function as you write it. Once you’ve implemented a function, run it on the examples in the docstring, as well as some other examples that you come up with yourself to convince yourself it works. Be careful that you test the right thing. Some functions return values; others modify the data in place. Be clear on what the functions are doing before determining whether your tests work.