python assignment
11/3/2019 1/13 Polling places You may work alone or in a pair on this assignment. Every two years, many people around the country wait in long lines to vote due, in part, to inadequate provisioning of voting booths. In this assignment you will write code to simulate the flow of voters through precincts. The information generated by your simulator could be used by an election official as a crude lower bound to help determine the number of voting booths need- ed at a precinct. We will view this problem as an instance of the more general problem of simulating an / / queue, where: the first indicates that arrivals (voters arriving at the polls) obey a Markov process; the second indicates that the service times obey a Markov process (the amount of time a voter takes to complete a ballot); and finally the indicates that there are servers (the number of voting booths). We will tell you how to structure your implementation at a high level, but you will be responsible for the design details. Getting started See these start-up instructions if you intend to work alone. See these start-up instructions if you intend to work with the same partner as in a previous assignment. See these start-up instructions if you intend to work in a NEW pair. The pa4 directory includes a file named simulate.py, which you will modify, a file named util.py that contains a few useful functions, a directory named data, which contains precint configuration files (de- scribed below), and a series of tests contained in files test_avg_wait_time.py, test_simulate_election_day.py and test_find_number_of_booths.py. Please put all of your code for this assignment in simulate.py. Do not edit other files or add extra files for the required classes. Precinct Configuration The configuration for a precinct is specified using a dictionary containing this information: The name of the precinct (name) number of voters assigned to the precinct (num_voters), number of hours the polls are open (hours_open), The number of voting booths (num_booths) The voter distribution (voter_distribution). For example: {'name': 'Downtown', 'num_voters': 5, 'hours_open': 1, 'num_booths': 1, 'voter_distribution': {'type': 'poisson', 'arrival_rate': 0.11, 'voting_duration_rate': 0.1} M M N M M N N https://www.classes.cs.uchicago.edu/archive/2019/fall/30121-1/_images/voting_booths.png 11/3/2019 2/13 Notice how the voter_distribution field contains another dictionary containing these fields: The type of distribution (type). In this assignment, we will only deal with one type of distribution: poisson The rate at which voters arrive (arrival_rate) and the rate at which voters complete their voting (voting_duration_rate). The significance of these rates is explained later. Information about precincts is stored in a JSON file that contains a dictionary with two keys: precincts, containing a list of precinct configurations as specified above, and seed, containing a random seed. Similar to PA1, the random seed will be used to ensure that a simulation involving randomness produces the same result (which will allow us to test whether your code produces the expected results). We recommend re- viewing PA1 (and how it used random seeds) if you’re unsure of how random seeds are used in the context of running a simulation. We have provided a function, load_precincts in util.py that takes the name of a JSON precincts file and returns two values: a list of precinct configurations (as specified above) and the random seed. This function is already called from the code we provide for you, so you should not make any calls to load_precincts in the code you’ll add to simulate.py. However, it can be a useful function when testing your code. In particular, you should take a moment to familiarize yourself with the data stored in these JSON files, and how to access each value once you’ve loaded the file with load_precincts. We suggest you start by looking at data/config-single-precinct-0.json, and loading that file from IPython: Representing Voters In this assignment you will need to model voters using a Voter class. This class must include the time the voter arrives at the polls, voting duration, that is, the amount of time the voter takes to vote, and the time the voter is assigned to a voting booth (aka, the start time). For simplicity, we will model time as a floating point number, representing the number of minutes since the polls opened. So, if we say a voter arrived at the polls at time 60.5, that means they arrived an hour and thirty seconds after the polls opened. While not strictly necessary, we found it convenient for debugging purposes to store the time the voter leaves the voting booth (i.e., the departure time) as well. In [1]: import util In [2]: precincts, seed = util.load_precincts("data/config-single-precinct-0.json") In [3]: precincts Out[3]: [{'hours_open': 1, 'name': 'Downtown', 'num_booths': 1, 'num_voters': 5, 'voter_distribution': {'arrival_rate': 0.11, 'type': 'poisson', 'voting_duration_rate': 0.1}}] In [4]: seed Out[4]: 1468604453 In [5]: len(precincts) Out[5]: 1 In [6]: p = precincts[0] In [7]: p["num_voters"] Out[7]: 5 In [8]: p["voter_distribution"]["arrival_rate"] Out[8]: 0.11 11/3/2019 3/13 The start time for a voter, which is not available at construction time, should be initialized to None when the voter object is constructed. This value should be reset to the correct value when the voter is assigned to a voting booth. Similarly, voters’ departure times cannot be determined until we know their start times. Your implementation must include at a minimum: a constructor and public attributes named arrival_time, voting_duration, and start_time. Our utility function for printing voters, described be- low, relies on the existence of these attributes. This class is straightforward. It merely serves as a way to encapsulate information about a voter. Our im- plementation is roughly 10 lines. Please note, the precinct class, described next, is the only class that is allowed to call the Voter constructor. Precincts Cities are broken up into voting precincts, and your implementation must include a Precinct class that represents a single precinct, and which will be responsible for simulating the behaviour of voters in that precinct. A precinct is open for some number of hours, and has some maximum number of voters who can vote in the precinct (you can think of this as the number of voters who are registered to vote in that precinct). We will assume that all registered voters will go to the polls on election day, but not all of them may get to vote, because some could arrive after the polls close. As we will explain later on, a precinct also has some number of voting booths (which can affect how quickly we can process voters) Notice how having a Precinct class allows us to have multiple Precinct objects in our program, each with its own set of parameters. This will make it easier for us to simulate the behavior of multiple precincts, as well as compare the effects of those parameters. For example, we could create two Precinct objects with the exact same parameters, but where one precinct has one voting booth and the other one has two voting booths. Simulating both can provide insights into how the number of voting booths can af- fect waiting times. We have already provided a skeleton for the Precinct class that includes the constructor and a simulate method to simulate a single voting day on that precinct. While you are allowed to add additional methods to this class, you cannot modify the parameter list of the constructor and the simulate method. Please note that we will consider each Precinct as completely independent from each other: voters cannot go from one precinct to another, and there is no shared information between the precincts. Generating Voters One of the main responsibilities of the Precinct class is to generate the voters according to some random distribution (in our case, we will only be using a Poisson distribution), so let’s take a closer look at how those voters will be generated. Both the arrival time and the voting duration of our voters will follow a Poisson process. From Wikipedia: a Poisson process, named after the French mathematician Simeon-Denis Poisson (1781-1840), is a sto- chastic process in which the time to the next event is independent of past events. We can use the following fact to generate a voter sample: if the number of arrivals in a given time interval [0,t] follows the Poisson distribution, with mean , then the gap between arrivals times follows the exponential distribution with rate parameter . This means that a Precinct object must keep track of time. We will assume that we keep track of time in minutes starting at time zero. To generate a voter, you will need to generate an arrival time and a voting duration. To generate the arrival time of the next voter, you will generate an inter-arrival time ( ) from the exponential distribution using the specified arrival rate as and add it to the current time ( ). You’ll then move time forward by updating the time from to . Notice how represents the time that elapses between the arrival of the previous voter and the arrival of the next voter. t ∗ λ λ gap λ t t t + gap gap 11/3/2019 4/13 For example, let’s say we want to generate a voter in a precinct, and the random number generator returns 5.7 for that voter’s gap. Since this is the first voter we generate, their arrival time will be 5.7, and we ad- vance the precinct’s current time from 0 to 5.7. We then generate another voter, and the random number generator returns 2.4 for the voter’s gap. This means that this second voter arrives 2.4 minutes after the previous voter, so the second voter’s arrival time will be 8.1 (5.7 + 2.4) and we advance the precinct’s current time to 8.1. When we generate a voter, we also need to assign a voting duration to that voter. You will draw the voter’s voting duration from the exponential distribution using the specified voting duration rate as . For testing purposes, it is important that you draw the gap and the voting duration in the same order as our code. To reduce the likelihood that the testing process fails simply because the values were drawn in the wrong order, we have provided a function, gen_poisson_voter_parameters, in util.py that takes the arrival rate and the voting duration rate as arguments and returns a pair of