Learning Goals
By the end of this assignment you should be able to:
·
read code you didn’t
write and understand its design and implementation, including:
o
reading and fully
understanding the class and method docstrings (including attribute
descriptions, representation invariants, preconditions, etc.)
o
determining
relationships between classes, by applying your knowledge of composition and
inheritance
·
implement a class
from a provided specification, including:
o
defining instance
attributes and methods
o
writing the class
documentation and method docstrings
o
implementing the
class functionality according to specifications
·
implement an
inheritance hierarchy that uses an abstract parent class to allow polymorphism
in client code.
You should also have practiced these habits:
·
implementing and
running a test suite for your code throughout the development process
·
breaking complex
tasks into smaller, more manageable subtasks
·
consciously
distinguishing between what your code does and how it does it
Problem Description
Grocery stores often have a difficult task: they must
determine how many employees to hire to staff checkout lines with varying
numbers of customers arriving throughout the day. Too few open lines means
customers spend time waiting; too many, and the store loses money paying
employees with no work to do. It’s also important to get the right mix of
regular, express and self-serve checkout lines. Which combination is best
depends on the needs of the store’s customers.
In this assignment, you’ll build an event-driven simulation for a grocery store, which could help in making these
decisions. Your program will us data from input files to set up a simulation of
customers and checkout lines, simulate a sequence of events, and report summary
statistics after the simulation is complete.
Simulation
Description
Read through the following description carefully. Your
overall task for this assignment will be to create a program which fulfills the
requirements here. We have broken the assignment into tasks with detailed
instructions later in this handout.
The Grocery Store
Here we describe all the things that your simulation
will keep track of to model grocery store checkout lines.
A grocery store must keep track of all customers and checkout lines in the store.
Customers are each referred to by a unique
(case-sensitive) string that is their name. Customers go to a checkout line to
pay for their items. The number of items a customer has affects which checkout
lines they can join. Each item takes a certain amount of time for a cashier to
check out.
Every checkout line can hold some number of waiting
customers. All lines have the same capacity. There are three different types of
checkout lines:
·
Regular checkout
line. Any customer can join the line, if there is room. The time required to
check out is equal to the total time required for each of the customer’s items
to be checked out by a cashier.
·
Express checkout
line. Customers can only enter the line if they have fewer than 8 items, and
there is room. The time required to check out is the same as it is in a regular
checkout line.
·
Self-serve checkout
line. Any customer can join the line, if there is room. The time required to
checkout is equal to twice the total time required for the customer’s items to be checked out by a cashier (because the
customer has to do the work themself, and they are never as fast as an
experienced cashier!)
Tip: draw a little table summarizing how these differ
(similar to the SuperDuperManager worksheet for the various Vehicle subclasses).
Lines are referred to by a unique index, with the
following order: regular lines, express lines, and then self-serve lines. For
example, if there are 3 regular lines, 2 express lines, and 10 self-serve
lines, then:
·
lines 0-2 are regular
lines
·
lines 3-4 are express
lines
·
lines 5-14 are
self-serve lines
(Note: This restriction is meant to make it convenient
to store the lines in a single list.)
A grocery store starts the simulation with a fixed
number of each type of checkout line, all of which are open and can serve
customers. However, some checkout lines may close during the simulation (see
next section).
Events
We are building an event-driven simulation, a type of simulation which is governed by a set of events. Each event
happens at particular time, changes the state of the simulation, and possibly
generates new events. There are four different types of events which you must
define:
·
Customer Arrival: A
customer arrives at the checkout area ready to join a line and check out. Among
all the lines an arriving customer is allowed to join, they join the one with
the fewest customers. In the case of a tie, they join the line with the lowest
index (as represented by the grocery store). And if there is no line that they are allowed to join, they have to try
again by “re-arriving” at the next time interval. (See below for how this is
make to happen through our events queue.)
·
Checkout Started: A
customer starts the checkout process in a particular checkout line. (That is,
they have reached the front of the line and are the one whose items are being
processed).
·
Checkout Completed: A
customer finishes the checkout process and therefore leaves the checkout line
they are in.
·
Close Line: A
checkout line closes. All customers who were in the line must join a new line, except the first customer in the line (who gets to stay and
complete their checking out). No new customers may join the line after it has
closed. In our simple simulation, we have no event for re-opening a closed
line, so once a line closes, it stays closed.
We could have simulated things in finer detail. For
example, we aren’t simulating the unloading of the items from the cart onto the
checkout conveyor belt, or the checking out of each individual item that a
customer has, or the process of paying. We chose to simulate just in enough
detail to gather the statistics that we want, and that will help us decide what
configuration of checkouts to use in the store.
Events all have an associated timestamp, a non-negative integer representing when that event occurs, in seconds.
The simulation starts at time 0. The simulation code begins by reading events
from a file and storing them in a container. The simulation code then
repeatedly gets the next unprocessed event to occur (the one with the smallest
timestamp) and processes it to update the state of the store. What makes the
simulation interesting is that sometimes processing one event triggers future
new events:
·
Customer Arrival: If
a customer joins an empty checkout line, a new checkout Started event is added
with the same timestamp as the Customer Arrival event. If there is no line for
the customer to join, a new Customer Arrival event is generated for them, with
a timestamp that is one step in the future.
·
Checkout Started: If
a customer begins checking out, a new Checkout Completed event is added with
the same timestamp as the Checkout Started timestamp, plus the appropriate
amount of time based on the type of checkout line and the time required for the
customer’s items.
·
Checkout Completed:
If a customer finishes checking out, the next customer in the line (if there is
one) gets a Checkout Started event with the same timestamp as the Checkout
Completed event.
·
Close Line: If a line
closes, all but the first customer in line needs to go into a new line,
starting with the customer at the end – essentially they re-arrive at the
checkout area. So there is one Customer Arrival event per customer in the line
that is closing (except the first customer). The last customer in the line should have a Customer Arrival
event whose time is the same as the time of the “close line” event, and the other Customer Arrival events should follow it in time,
spaced 1 second apart.
Example: suppose there is a
checkout line with customers A, B, C, and D, with A being the first customer in
the line. Suppose this line closes at time 30. A remains in the line and three
new events are spawned: D has a Customer Arrival event at time 30, C has a
Customer Arrival event at time 31, and B has a Customer Arrival event at time
32.
Statistics
When the simulation is over, it should report three
statistics: the total number of customers in the simulation, the timestamp of
the final event, and the maximum time any customer spent waiting to checkout.
Starter code
Download the assignment materials and unzip it into your assignments/a1/ folder.
This folder contains the following files:
·
Starter code for the
simulation program:
o
store.py
o
event.py
o
simulation.py
o
container.py
·
Starter code for your
Task 3a unit tests of PriorityQueue:
o
test_priority_queue.py
·
Provided code for
testing the whole simulation:
o
test_a1.py
·
Provided code for
checking code coverage:
o
check_coverage.py
·
Sample grocery store
configuration files:
o
input_files/config_*.json. Notice the pattern in how we named these files; you can understand the
configuration just by reading the file name.
·
Sample event files:
o
input_files/events_*.txt
The starter code does not include the import statement
for check_contracts or the @check_contracts decorators necessary to turn on checking of contracts. You are welcome to
add these. Note that, to reduce load on the system and timeout issues, we will
set up both your self-tests and the full test suite so that checking of
contracts is turned off.
Your tasks for this assignment are below. Be sure to
use not only the provided doctests but also your own unit testing (implemented
with pytest) to check your code as you go.
Task 1: Modelling a
Grocery Store
In this task, you will complete the design,
implementation, and testing of classes for the store, customers, and different
kinds of checkout lines.
In store.py, we have provided
starter code for the required classes.
Your task is to complete the implementation of these
classes as noted in the TODOs in store.py.
Tips:
·
Before writing any
methods, read the inteface to all the classes in store.py so you are aware of
the services each class provides – or will eventually provide once you finish
the class. When you implement a method, it’s good to know what you don’t have to
do yourself, but instead can accomplish by calling these other methods.
·
Be aware that as you
implement the various methods, you may sometimes realize you want to go back
and revise something you implemented earlier. This is a normal part of the
process. (But there shouldn’t be any need for large revisions.)
Note about GroceryStore.__init__
One of the input files to the simulation is a file
which holds the configuration of a grocery store. It is in a format called
JSON, and contains these key-value pairs:
·
‘regular_count’: the number of regular checkout lines
·
‘express_count’: the number of express checkout lines
·
‘self_serve_count’: the number of self-serve checkout lines
·
‘line_capacity’: the maximum number of customers allowed in each line (all lines have
the same capacity)
The initializer for GroceryStore takes an open JSON file and creates a Python dictionary
from it, with the same key-value pairs shown above. We have provided the line
of code that does this.
Task 2: Events
We have provided starter code for the event classes in event.py. Read through the abstract class documentation carefully. Your first job
is to use inheritance to implement subclasses for three specific types of
events.
At the bottom of the event.py, you must also implement the function create_event_list, which reads in events from a file. It must handle files that have the
following format:
·
there is one event
per line
·
only “new customer”
and “line close” events appear
·
the “new customer”
event has the following format:
Arrive
where is one or more pairs of
·
the “line close”
event has the following format:
Close
You may assume that there will be at least one event in
the event file; that no customer will have two arrival events in the same event
file; and that the events can be simulated successfully (e.g., there will be at
least one checkout open so that all customers can eventually check out).
You can see examples of valid files, such as events_base.txt in input_files/.
Test your code thoroughly before moving on. You do not
need to submit a test suite for this specific task, but we encourage you to
write tests as if you were!
Task 3: Event queue
Our simulation needs a way to keep track of events.
While we could use a Python list for this, we don’t really need all the
functionality which Python lists provide. All we really need is a simple data type which allows us only to
insert objects and remove them one at a time.
This should sound like a familiar set of operations
from our discussions of ADTs; however, neither the Stack nor Queue ADT we
covered so far works here, because we don’t want to remove events based on when
we inserted them, but rather based on their timestamp.
This leads us to a new ADT: the PriorityQueue, which supports the following actions:
·
determine whether the
priority queue is empty (just like a regular queue)
·
insert an item with a
given priority
·
remove the item with
the highest priority
In the case of a tie for highest priority, the item
added most recently should be removed last.
Read container.py, which contains a Container abstract class, as well as a new, partially-complete PriorityQueue class.
Task 3a: Testing for
Priority Queue
Note: this task should be done alongside your work on
Task 3b
In this task, you will write a pytest test suite for
the PriorityQueue class defined in container.py. Write your tests in test_priority_queue.py.
You should aim to have a robust set of tests, covering
both simple and more interesting test cases. We will evaluate your tests by
checking: – that they catch bugs in buggy implementations of this class and –
that they achieve full code coverage. You can check the coverage by running check_coverage.py. Uncomment the lines at the bottom of that file to see the html coverage
report in your browser.
You must NOT make adjustments to the import statements
in the test file, and you are responsible for running the self tests on MarkUs
to ensure we can run your tests.
Tip: You can use the auto-test feature in PyCharm to
automatically re-run your tests every time you modify your code. Just run the
tests once and then press the little “arrows in a circle” button to the left of
the test results window to turn on auto-test. If you are using the “new UI” in
PyCharm, the auto-test toggle will be under the three vertical dots located to
the right of the button to rerun the tests just above where the Test Results
are displayed.
Task 3b: Implement
Priority Queue
Now complete the PriorityQueue.add implementation according to its docstring. (Notice that
we’re using a sorted
list to implement this class; in later courses, you’ll learn about a much more efficient implementation
called a heapLinks to an external site..)
Note: you must write the code to add the new item
yourself — do not use built-in sorting functionality, like list.sort. Hint: the rest of the items are already in sorted order, so you only
need to determine where to insert your new item. It can help to draw a few
small test cases and perform the insertions by hand in order to determine a
suitable algorithm.
Task 4: Simulation
The simulation.py file has the module that drives the overall simulation. It contains the
class GroceryStoreSimulation, which keeps track of everything needed for the simulation. Its
initializer sets up the simulation, and its run method operates the simulation by processing events and
doing all necessary record keeping. The module also has a main block that sets
up a simulation, runs it, and prints out the statistics that were gathered
during the simulation. Once your code is complete, this is the module you will
run in order to create and run a simulation.
Your job in Task 4 is to implement the GroceryStoreSimulation.run method. The main structure of this method should look
like this:
add
the initial events to self._events
while
we have events to process:
event = remove event from self._events
process event and find out what new events
this generates # Add this step once the rest is working.
add any new events to self._events
We strongly recommend that you omit the processing step
until you have made sure that you can create the initial event queue and loop
through it, getting the events out in the right order. A great way to check
would be to implement a __str__ for each of the events and print out the event on each iteration. Once
this is working properly, add to your loop the code to process each event.
Test your code thoroughly. You do not need to submit a
test suite for this task, but we encourage you to write tests as if you were!
Statistics
Add code to your run method that will keep track of statistics in a
dictionary with the following keys:
·
‘num_customers’: the total number of customers in the simulation.
·
‘total_time’: the timestamp of the last event.
·
‘max_wait’: the maximum amount of time any customer waited. Customer wait time is defined as the
difference in times between when the customer first attempted to join a line
and when the customer finished checking out. Hint: think about which events
will be relevant to calculating this statistic.
You will need to update the statistics on every
iteration of the loop.
You can assume that every simulation includes at least
one customer arrival event.
Polish!
Take some time to polish up. This step will improve
your mark, but it also feels so good.
Here are some things you can do:
·
Review your code and
look for ways to simplify the design, or improve the efficiency. Good code
means more than just working code.
·
Pay attention to any
violations of the Python style guidelines that PyCharm points out. Fix them!
·
In each file you will
be handing in, run the provided python_ta.check_all() code to check for pyTA errors. Fix them!
·
Check your docstrings
for any helper methods you wrote to make sure they are precise and complete,
and that they follow the conventions of the Function Design Recipe and the
Class Design Recipe.
·
Read through and
polish your internal comments.
·
Take pride in your
gorgeous code!
Submission
instructions
1.
Submit your final
versions of all five (5) assignment files:
o
store.py
o
event.py
o
simulation.py
o
container.py
o
test_priority_queue.py
Last Completed Projects
| topic title | academic level | Writer | delivered |
|---|