Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 1: A Grocery Store Simulation

Assignment 1: A Grocery Store Simulation

Due date: Monday, March 4, at 6:00 p.m.

You may work individually or with one other person on this assignment. Partners must be invited in MarkUs (and invitations accepted) by Monday, February 26 at 6:00 p.m.

Important: To find out what you can and cannot do in the code you write for your assignments, please review the “Technical (programming) requirements” on the course page Policies and Guidelines: Assignments 

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:

<timestamp> Arrive <name> <items>

where <items> is one or more pairs of <item name> <item time>

· the “line close” event has the following format:

<timestamp> Close <line_index>

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. Login to MarkUs.

2. 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

3. Run the self-tests on MarkUs one more time to confirm that your code is able to run and that it is passing these tests.

4. Congratulations, you are finished with your second assignment in CSC148! Go have some chocolate or do a cartwheel. :)