\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\Rightarrow} \newcommand{\IFF}{\Leftrightarrow} \newcommand{\TRUE}{\text{True}\xspace} \newcommand{\FALSE}{\text{False}\xspace} \newcommand{\IN}{\,{\in}\,} \newcommand{\NOTIN}{\,{\notin}\,} \newcommand{\TO}{\rightarrow} \newcommand{\DIV}{\mid} \newcommand{\NDIV}{\nmid} \newcommand{\MOD}[1]{\pmod{#1}} \newcommand{\MODS}[1]{\ (\text{mod}\ #1)} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cL}{\mathcal L} \newcommand{\cK}{\mathcal K} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cZ}{\mathcal Z} \newcommand{\emp}{\emptyset} \newcommand{\bs}{\backslash} \newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\ceil}[1]{\left \lceil #1 \right \rceil} \newcommand{\abs}[1]{\left | #1 \right |} \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \)

CSC148 Fall 2023 Assignment 1: Elevator Simulations

One of the oldest and most widespread uses of computer programming is to create and run simulations, which are programs that model a particular domain, be it a complex chemical or physical system, the spread of a contagious disease, or financial systems like the stock market. These simulations are parameterizable, meaning we can run the same simulation program several times with different input parameters to see how the system’s behaviour changes.

On this assignment, you’ll create a simulation of a (simplified) elevator system, in which elevators carry people between different floors of a building, using different algorithms for deciding how elevators move between floors.1 We’ll use a time-based simulation, for which the state of the simulation is updated in rounds that each represent a fixed length of time (e.g., 1 second). By varying the different parameters of the system, you’ll be able to compare different algorithms, making judgments about whether one is better than another in some cases, or in all cases.

Logistics

PythonTA update

Before starting this assignment, please update your PythonTA version to 2.6.3 (this fixes a few bugs that some students ran into).

You can do this in PyCharm:

  1. Open the Settings window.
  2. Go to Project: csc148 -> Python Interpreter.
  3. Select python-ta in the table of packages.
  4. Click on the “up triangle” button above (or beside) the table to upgrade python-ta.
    • Or, if you can’t find the button, click on the “plus” button and search for python-ta, and check the “Specify version” box and select 2.6.3.

Starter files

To obtain the starter files for this assignment:

  1. Login to MarkUs and go to CSC148.
  2. Under the list of assignments, click on Assignment 1.
  3. (new!) To access the starter files, you’ll first need to either create a group or indicate you are working individually. You can change this later if you decide to partner with another student.
  4. Then, click on the Download Starter Files button (near the bottom of the page). This will download a zip file to your computer.
  5. Extract the contents of this zip file into your csc148/assignments/a1 folder.
  6. You can then open these files in your PyCharm csc148 project, just like all of your other course materials.

General instructions

This assignment contains a series of programming tasks to complete. This is similar in structure to the Weekly Preparation Synthesize exercises, but more complex. Your programming work should be completed in the different starter files provided (each part has its own starter file). We have provided code at the bottom of each file for running doctest examples and PythonTA on each file.

Like the prep exercises, this assignment will be automatically graded using a combination of test cases to check the correctness of your work and PythonTA to check the code style and design elements of your work.

This assignment is similar in style to Assignment 0, but more complex. Please start early!

Our problem domain: an elevator system simulation

For this assignment you will build a program that runs a simulation of a building’s elevator system, with people using elevators to move between floors. Our elevator simulation consists of four main parts:

  1. The basic entities contained in the simulation: people and elevators.
  2. The algorithms that determine how the entities appear and change over time:
    • how frequently and on which floors new people appear, and to which people want to go
    • where elevators choose to move to
  3. The main simulation runner, which is responsible for setting up the initial parameters of the simulation, running the simulation, determining when the simulation should end, and reporting the results of the simulation.
  4. A visualizer which provides functions and classes for visualizing the simulation using Pygame. Almost all of this code will be written for you; your responsibility will be to read the provided documentation to understand how to use these functions and classes in your own code!

We’ll go into more detail for each of these components as you proceed throughout this assignment. But first, watch the short video below to see an example simulation run. Keep in mind the following questions as you watch—you might not know the answers now, but should be able to answer all of these as you work through this assignment!

  1. How many floors and elevators are there, and how are these chosen?
  2. What determines where the people came from (and where they want to go)?
  3. What is “controlling” the elevator movement?
  4. What state is changing over time as the simulation runs?

Part 1: The basic entity classes

First, please read the following description of the two key entities in this simulation.

People

A person in the simulation has three characteristics: which floor they started on, which floor they want to go to, and the number of simulation rounds they have been waiting to reach their target floor. Each person’s waiting time increases both when they are waiting at a floor and when they are traveling on an elevator. Each person arrives at a particular floor and then waits at that floor until they can board an elevator. When their elevator arrives at their target floor, the person leave the elevator.

Elevators

Each elevator keeps track of the floor it is currently on and a target floor which determines where it is moving to. An elevator is idle (not moving) when its target floor is equal to its current floor. The current floor is always a positive integer—we don’t worry about an elevator being “between floors”. All elevators in the simulation begin a Floor 1 of the building.

Each elevator also keeps track of its passengers (the people who currently on it) as well as its maximum capacity—if an elevator is full, no more people can board it.

Open a1_entities.py. We have provided the start of the two classes, Person and Elevator, that represent the key entities in this simulation. Your first task is to read through the provided code and complete these classes according to the descriptions above.

While this is similar to the work you did on Assignment 0, there are a few key differences that make this work more complex:

  1. Person and Elevator are subclasses of abstract “sprite” classes from visualizer.py. You’ll need to read through their respective superclasses (PersonSprite and ElevatorSprite) to see what methods are abstract and must be implemented. You may also need to override some of their other methods.

  2. You may need to return to these classes throughout this assignment to add new attributes or methods (especially in Part 4). Don’t worry about getting the classes “perfect” right now. Instead, complete what you can and then move on, and then be prepared to return and modify your design later.

Check your work

As usual, we’ve provided some sample tests as either doctests or unit tests (in a1_sample_test.py). We strongly encourage you to add your own for this part, and for the rest of the assignment. This follows the same approach as Assignment 0.

Part 2: Setting up the simulation

Next, open a1_simulation.py. We have provided the start of a Simulation class that will act as the main simulation runner for this assignment. This is a big class, so we’ve broken down what you need to do into multiple steps. For this part, your task is to complete the Simulation initializer. Remember that the purpose of the initializer is to initialize all of the instance attributes; we have provided descriptions of all instance attributes already, and part of this task is to read and understand the expectations for these instance attributes.

To complete the initializer, you’ll need to read the following box to understand the configuration values that will be used to create a simulation.

Initializing the simulation

The simulation initializer takes in a single parameter, config, which is a dictionary with the following keys:

We have started the initializer for you; the only task in this part is to complete it so that it initializes all of the attributes.

Check your work

In addition to the provided sample test cases, if you scroll down to the bottom of a1_simulation.py, where you’ll see a provided function called run_example_simulation. If you call this function in the Python console or the main block, you should see a Pygame window with the number of elevators and floors specified in the configuration dictionary.

You can try changing the number of elevators in the example simulation to test your work visually. Due to the limitations of our visualizer, the simulation looks best when given fewer than ~8 floors and elevators. However, your program should be able to handle simulation configurations beyond this range! When testing these cases, set visualize to False so that the simulation simply runs in the background, without visualizing anything.

Tip: the Pygame window should close itself after 15 rounds, but if you ever want to stop the simulation early, simply go to PyCharm’s Run pane and click on the red Square (“stop”) button.

Part 3: Simulation rounds

Now that the simulation is set up, let’s get it to actually, well, simulate changes! To do so, you’ll implement a series of helper functions (and classes) that represent various forms of state changes in the simulation. To start, read the following box, which describes the actions that occur in each round of the simulation.

Simulation rounds

Our elevator simulation proceeds in rounds, where each round represents the time it takes for an elevator to move from one floor to another and for people to get on or off the elevators. Each simulation round consists of five different phases, which occur in the following order.

  1. Elevator disembarking. Every person who is currently on an elevator and at their target floor leaves the elevator.

  2. New arrivals. New people are added to the simulation (appearing at their start floor).

  3. Elevator loading. People board elevators on their floor according to the following restrictions:

    • People board in order of when they arrived at the floor (like a queue!).
    • People only board an elevator that isn’t full.
    • People only board an elevator if the elevator is idle (its target floor equals its current floor), or if the elevator’s target floor is in the same direction as the person’s target floor.
      • For example, if a person is at floor 3 and wants to go to floor 1, they will board any elevator at floor 3 whose target floor is < 3 or == 3 (idle), but not > 3.
    • If there are multiple possible elevators a person can choose from, the person chooses the leftmost elevator (remember, the simulation stores elevators in a list).

    Note: Unlike “real” elevators, in our simulation an elevator’s target floor is only updated in the next phase, after as many people as possible have boarded it. This means that an idle elevator will allow people to board it independent of their target floors. Someone might board an idle elevator only to find that it begins moving in the opposite direction from where they want to go!2

  4. Elevators move.

    1. An algorithm updates the target floor of each elevator. This may, but is not required to, take into account the elevator’s passengers and/or the people who are waiting for an elevator.
    2. Then, each elevator moves one floor closer to its target floor (or stays at the same floor, if it has reached its target floor).

  5. Update wait times. Every person in the simulation who is either waiting or on an elevator has their waiting time increased by 1. This will be used to report simulation statistics in Part 4.

Review

Having read this description, go back and watch the demo video we’ve posted above. That video shows the simulation running for 15 rounds, and each round executes each of the five phases we’ve described above. Make sure you can see what’s happening in each phase. You might still have questions about some of the details, which is okay; we’ll explore these details throughout this part of the assignment.

Part 3(a): People arrivals and wait time tracking

During each simulation round, new people may arrive at the elevators. Since this is a simulation, we need an algorithm to decide how many people arrive at a given round, and the starting and target floors of each person. Moreover, because we want our simulation to support different algorithms to generate arrivals, we’ll use inheritance to allow the programmer to define different kinds of algorithms.

  1. Open a1_algorithms.py and read through the class ArrivalGenerator, which is the abstract superclass that defines the public interface for the arrival generation algorithms you’ll define.

    (Oct 16) Note: the return value of the ArrivalGenerator.generate method should be a dictionary whose keys are floor numbers and whose corresponding values are each a list of Persons who start on that floor.

  2. Then, implement the SingleArrivals subclass. (For now you can ignore the other, more complex, subclass; you’ll implement that in Part 5.)

  3. Now, open a1_simulation.py and implement Simulation.generate_arrivals to actually run your arrival generation algorithm. This should both update the simulation’s waiting instance attribute, as well as call the Visualizer.show_arrivals method appropriately to actually show the new arrivals in the Pygame window.

  4. Finally, implement Simulation.update_wait_times. Note that this method isn’t visualized, it should just update the Person objects in the simluation.

Check your work

You should now be able to run the sample simulation and see people arriving at each round. Of course, nothing else in the simulation is happening yet, but that’s a start!

Part 3(b): Elevator boarding

Now that you have people and elevators, you can complete the third phase of the simulation round: having people board elevators. This can be done entirely in Simulation.handle_boarding with one or two helper functions to help split up your code. You’ll need to remember to update the state of each elevator as it takes on new passengers, and to visualize the change by calling Visualizer.show_boarding appropriately.

Check your work

Now when you run the sample simulation, you should see that in addition to people arriving at floors, anyone who arrives on the first floor moves to the leftmost elevator that still has room. Note that because you haven’t implemented any elevator moving algorithm, the elevators will fill up on the ground floor, letting you verify that your implementation correctly handles boarding when some elevators are full.

If you read through all the documentation in visualizer.py, you should see some visual effects as the simulation runs: elevators getting full, and people getting angrier. Note: you’ll notice that the visualizer seems to draw sprites in a random (or reverse) order, so the “oldest” sprites are covered by newer ones. This is normal, and not a bug with your code!

Part 3(c): Elevator moving

Each round, an elevator moving algorithm can update the target floor for each elevator to alter its moving direciton in the simulation. A moving algorithm receives as input two values: a list of all the elevators in the simulation, and a dictionary mapping floor numbers to a list of people who are waiting on that floor.

This is an extremely flexible model of how elevators move, and the reason we do this is so that that you can implement a variety of fun and interesting elevator algorithms!

As with the arrival generation, our simulation will support multiple kinds of elevator moving algorithms. To complete this part:

  1. Open a1_algorithms.py and read through the MovingAlgorithm abstract class.

  2. Then, implement the EndToEndLoop subclass. (For now you can ignore the other, more complex, subclass; you’ll implement that in Part 5.)

  3. Finally, open a1_simulation.py and complete the Simulation.move_elevators method. This method will need to do three things:

    1. Call the moving algorithm’s update_target_floors method to update elevator target floors.
    2. Move each elevator one floor closer to its target floor.
    3. For each elevator, calculate the direction it moved in (with the appropriate Direction value), and then call Visualizer.show_elevator_moves appropriately.

Check your work

Now when you run the simulation, you should see people arriving, boarding elevators, and those elevators moving. Notice that with the EndToEndLoop algorithm, all elevators (including empty ones) move in sync, going from the bottom floor to the top floor, back to the bottom floor, and so on in a loop. Since you haven’t yet implemented the people disembarking from elevators, no person will actually get off an elevator (and so you should see them getting angrier and angrier as they ride the elevator).

Part 3(d): Elevator disembarking

Now it’s time to implement the last phase of a simulation round: elevator disembarking. Remember that this occurs at the start of each round: whenever a person is on an elevator and that elevator is at their target floor, the person leaves the elevator.

You can implement this action entirely in the Simulation.handle_disembarking method. You’ll need to call Visualizer.show_disembarking appropriately to visualize this happening.

Check your work

After completing this step, you should now have a fully working simulation that executes (and visualizes!) all four stages of a simulation round: people disembarking from elevators once they’ve reached their target floor, new people arriving (according to SingleArrivals), people boarding elevators that have space, and elevators moving (according to EndToEndLoop).

Try varying the configurations of the sample simulation run; you’ll likely find some bugs in at least one of these stages, and now is an excellent time to fix them!

Part 4: Tracking and reporting statistics

Now that you have a working simulation, you’ll next modify your implementation to track a set of summary statistics for this simulation and report them when the simulation ends. Read the box below to understand what statistics you’ll need to report.

Simulation statistics

At the end of the simulation, you are responsible for reporting summary statistics for the simulation, in a dictionary with the following keys:

The max_time and avg_time statistics should only take into account the people who reached their target floor. Report -1 for these two statistics if no person reached their target floor during the simulation run (i.e., people_completed has a value of 0).

Your task here is to add to your existing code so that you can keep track of and report these statistics. By “add to your existing code”, we mean doing the following:

Check your work

Try running a very small simulation (e.g., 1 elevator, 5 rounds) first, and manually calculate the expected value for each statistic. Then after running the simulation, you’ll be able to check the value of each statistic.

Also check out the sample tests we’ve provided, and add to them!

Part 5: Implementing more complex algorithms

Your final task for this assignment is to implement two new classes in algorithms.py: an additional ArrivalGenerator subclass and an additional MovingAlgorithm subclass. This illustrates the power of inheritance: after implementing these two subclasses, you should be able to use them in a simulation without requiring any changes to the Simulation code!

Read the following box that describes these two new algorithms, and then implement them in a1_algorithms.py.

class FileArrivals(ArrivalGenerator): Reading arrival data from a file

A comma-separated values (csv) file is a text file that uses commas to separate pieces of data. Our second approach for arrival generation is to read arrivals from a csv file, in the following format:

For example, the following data file (data/sample_arrivals.csv)

0, 1, 4, 5, 3
2, 1, 2
5, 4, 2

represents the following arrivals:

You may make the following assumptions about input files for this assignment:

  1. The round numbers are non-negative, and are less than the maximum number of rounds in the simulation.
  2. Each round number is unique (no two lines start with the same number). But do not assume that the lines are sorted by round number.
  3. Each person’s starting and target floors are distinct positive integers, and do not exceed the maximum number of floors in the simulation.

class FurthestFloor(MovingAlgorithm): taking into account passenger preferences

Unlike EndToEndLoop, this algorithm determines the target floor of each elevator based on the elevator’s passengers (if any) or the people waiting (if any). See the docstring for the FurthestFloor class for more detail.

Check your work

At this point, it may be tempting to just run your simulation a bunch of times and watch the Pygame window, but this is not a very robust approach to checking whether your algorithms are correct. Instead, we recommend using your FileArrivals class to create test inputs for the arrivals, and then carefully trace what should actually happen on small inputs, and use these inputs to check whether your FurtherFloor moving algorithm works as intended as well. You can then either run the simluation with these custom test inputs and check the statistics, or (better!) add to the sample tests in a1_sample_test.py to encode the expected behaviour as test cases.

Submission instructions

Before submitting your work, please do the following:

  1. Make sure you can run every assignment file. As we explain in Running and Testing Your Code Before Submission, it is essential that your submitted code not contain syntax errors. Python files that contain syntax errors will receive a grade of 0 on all grading involving those files. You have lots of time to work on this assignment and check that each file runs (e.g., right-click -> “Run in Python Console”), so please make sure to do this regularly and fix syntax errors right away. Remember, this doesn’t mean you need to have completed the whole assignment! You can still get lots of partial credit for the work you complete as long as your code can be run by Python.
  2. Run your tests one last time (both doctests and pytest). This will help catch any “last-minute changes” that might accidentally have introduced a bug into your code.
  3. In each module, run the provided python_ta.check_all() code to check for PythonTA errors, and fix them! Tip: most formatting errors (e.g., blank lines, whitespace) can be fixed automatically in PyCharm by using the menu option Code -> Reformat Code.
  4. Remove any code you added just for debugging, such as print function calls. Remove any large blocks of commented-out code. If you want to save an old or alternate approach, create a copy of the file instead.
  5. Take pride in your beautiful code. 😎

Now, to actually submit your work:

  1. Login to MarkUs.

  2. Go to Assignment 1, then the “Submissions” tab.

  3. If you are working with a partner, make sure you have formed a group on MarkUs.

  4. Submit the following files: a1_algorithms.py, a1_entities.py, and a1_simulation.py. Do not submit any other files. Please note that MarkUs is picky with filenames, and so your filenames must match these exactly, including using lowercase letters.

    Tip: you can select multiple files at once for submission.

    If you are working with a partner, only one of you needs to submit the files.

  5. Refresh the page, and then download each file to make sure you submitted the right version.

Remember, you can submit your files multiple times before the due date. So you can aim to submit your work early, and if you find an error or a place to improve before the due date, you can still make your changes and resubmit your files.

After you’ve submitted your work, please give yourself a well-deserved pat on the back and go take a rest or do something fun or eat some chocolate!

GIF of elevator dancing.

  1. David’s favourite elevator-related quotation: “Ethan says Type-A personalities have a whole subset of diseases that they, and only they, share, and the transmission vector for these diseases is the door close button on elevators that only get pushed by impatient, Type-A people.” (Douglas Coupland, Microserfs)↩︎

  2. Again, this is not the case in real life because of the use of elevator buttons on each floor. However, many of us have accidentally entered an elevator that was actually going in the wrong direction!↩︎