CSC 148H - Assignment #1 - Stacks and Queues
Due Friday May 30th 1pm
Due Sunday June 1st 1pm, no grace days for this assignment

Part 1 - Transforming a List of Integers (35%)

You are given a list of integers S, which you are asked to transform according to the following procedure:
  1. Find, if possible, the leftmost adjacent pair of integers in S, (x,y), such that y == x + 1
  2. If the pair exists
    1. Replace the pair by their sum. Label the resulting sequence S'.
    2. Set S = S' and go to line 1.
  3. If the pair does not exist, you are done and S is the result of the transform.

Examples

Example 1. S = [1,2,45,60] is transformed to [3,45,60].

Example 2. S = [1,2,3,4] is transformed to [3,7]

(1,2) is first replaced by 3, and then (3,4) is replaced by 7. In other words, the list is transformed from  [1,2,3,4] to [3,3,4] and finally to [3,7].

Example 3. S = [2,1,3,4] is transformed to [2,1,7]

(2,1) is NOT replaced by 3, since the order of x and y in step 1 is important.

Example 4. S = [12, 6, 7] is transformed to [25].

(6,7) is replaced by 13, and then (12,13) is replaced by 25.

Discussion

The transform procedure appears to be stated in very straightforward pseudocode that can be translated directly into a python program. Lets consider how this might be done. In line 1 of the transform procedure, you need to find the "leftmost adjacent pair of integers" satisfying the stated condition. The easiest way to do this is to read every element in the list from left to right until you find the first pair of integers that satisfies the condition. If you do this every time you perform line 1, however, the transform can be extremely inefficient. This is because, in the worst case, the leftmost pair of integers satisfying the condition can always be at the end of the list.

For example, consider the list [8,4,2,1,2], and try applying the transform procedure to it by hand. The list is transformed from [8,4,2,1,2] to [8,4,2,3] to [8,4,5] to [8,9] and finally to [17]. Observe that each time you perform line 1, the leftmost pair of integers satisfying the condition occurs at the end of the list, meaning that you have to scan the entire list before you find them.

More generally, assume n > 0 and consider a list of integers of the form [2^n, 2^(n-1), ..., 4, 2, 1, 2]. Essentialy, the list consists of decreasing powers of 2, starting at 2^n, followed by a "2" that's tacked on at the end. When the transform procedure is applied, the list of integers will evolve as follows:

Initially S = [2^n, 2^(n-1), ..., 4, 2, 1, 2] n+2 elements in the list
After 1 application of lines 1-2: S = [2^n, 2^(n-1), ..., 4, 2, 3] n+1 elements in the list
After 2 applications of lines 1-2:
S = [2^n, 2^(n-1), ..., 4, 5] n elements in the list
...

After n+1 applications of lines 1-2:
 S = [2^(n+1) + 1] 1 element in the list

Initially, S consists of n+2 elements, so the first time you scan through the list you will have to read n+2 elements. After each application of lines 1-2, there is 1 less item to read. If you read every element in the list each time line 1 is performed, then the total number of "read operations" done during the transform procedure will be at least

(n+2) + (n+1) + n + (n-1) + ... + 4 + 3 + 2 + 1= (n+3)(n+2)/2 = (n^2 + 5n + 6)/2

In other words, for a list of 1,000 integers, you may end up having to do at least 500,500 read operations. For a list of 1,000,000 integers, you may end up having to do at least 500,000,500,000 read operations.

Luckily, there's a better way of implementing the transform procedure.

What to do

It should be apparent from the discussion above that treating the transform procedure as pseudocode to be translated directly into python code can yield a very inefficient implementation. Instead, you should treat the transform procedure as a description, or a specification, of what the transform should accomplish. In particular, it is not necessary that you calculate or store the "intermediate" list S' at any point -- we only care about the final result of the transform. We used the "intermediate" lists in our examples and discussion above to simplify the explanation of how we get from the input list of integers to the final transformed list, but there are more clever ways of implementing the transform without generating these intermediate lists.

Your job is to implement the transform procedure efficiently using a Stack. By using a stack you can avoid having to reread elements in the list unnecessarily when you're searching for the next pair of integers that satisfy the condition stated in line 1 of the transform.

Here are the files you should download: transform.py, and testtransform.py.

You need to:
  1. Implement the transform function in transform.py using the Stack class (already provided in transform.py).
  2. Create a number of suitable unit tests to convince yourself (and us) that you have implemented the transform function correctly. The testtransform.py file already contains one test to get you started.
Remember to comment your code. In particular, you should include a high-level description of how your implementation works.

Hints and Tips

Part 2 - Pizza Delivery (65%)

"The Deliverator belongs to an elite order, a hallowed subcategory." - Neal Stephenson, Snow Crash

In this part you will design and implement a pizza delivery simulation for the CosaNostra Pizza Shop. The simulation is parameterized by: (i) the number of minutes it takes to cook a pizza (cook_time);  (ii) the number of pizza delivery personnel (known as deliverators) that the pizza shop has in its employ (num_deliverators); and (iii)  a list of pizza orders, each of which has a unique identifier (ID), and specifies the number of minutes after the start of the simulation when the order is placed (order_time), and the number of minutes it will take to deliver the pizza to its desitination (delivery_time). The goal of the simulation is to determine the exact time each pizza arrives at its destination and the deliverator who delivered it.

Here is how pizzas are made and delivered:

When an order is made, an uncooked pizza is placed onto a conveyer oven. When the pizza comes out the other end of the oven (after cook_time minutes), it is placed onto a cooling rack. There is also a line up deliverators waiting to deliver the pizzas. Whenever a pizza is available on the rack, the next deliverator in line takes the pizza that has been on the rack the longest and goes out on delivery. The number of minutes that it takes for him to deliver the pizza is specified by the delivery_time of the order he's delivering. After he delivers the pizza, it takes him another delivery_time minutes to return to the shop, at which time he goes to the back of the line of waiting deliverators.

At the beginning of the simulation, there are num_deliverators deliverators waiting in line. To distinguish between deliverators during the simulation, the deliverators are each given a unique ID. The IDs are integers and are assigned based on the order in which the deliverators are standing in line at the beginning of the simulation: the deliverator at the front is assigned ID 0, the deliverator second in line is assigned 1, and so forth.

To simplify the simulation, we assume that the following times are negligible (i.e, take no time):
You may also assume that we will never run a simulation in which:

Getting Started

You should download the following files: simulator.py,  testsim.py, pqueue.py.

The simulator.py file contains the following definitions:

class PizzaOrder:
    """
    A pizza order that can be made during the pizza shop simulation
    """
   
    def __init__(self, id, order_time, delivery_time):
        """
        Create a new PizzaOrder based on:
        id: the unique ID for the order
        order_time: the number of minutes after the beginning of the
                    simulation when the order is made
        delivery_time: the number of minutes it takes to deliver pizza to
                       its destination
        """
        self.id = id
        self.order_time = order_time
        self.delivery_time = delivery_time


def simulate(cook_time, num_deliverators, orders):
    """
    Simulate a pizza shop, given:
    cook_time: number of minutes it takes to cook a pizza
    num_deliverators: number of deliverators employed by shop
    orders: a list of pizza orders
   
    Returns a dictionary that maps order ID to a list of 2 elements: the
    first element is the ID of the deliverator who delivered the pizza,
    and the second element is the number of minutes after the start of
    the simulation when the pizza got delivered.
    """

A call to the simulate() function starts the simulation. Its return value contains information about what pizza gets delivered when and by whom. To better understand the format of the return value, look at the example tests in the testsim.py file.

Your job is to implement the simulation. Note: A good implementation will entail more than simply putting all of your code in the simulate() function. You need to think carefully how your simulation will work, and design the simulation appropriately. The next section provides some guidance on how to do this.

More Help on How to Implement the Simulation

Sections 2.4.4 and 2.4.5 in your text book describe two different simulations. You may want to read over and understand these sections to see some examples of how a simulation can be implemented. However, you should be aware that these simulations are different in a number of respects from the simulation that you are asked to do in this assignment. In particular, the printer simulation (section 2.4.5) is non-deterministic. That is, what happens during the simulation has an element of randomness to it. Our simulation, on the other hand, is deterministic, since running the simulation any number of times with the same parameters (i.e., cook_time, num_deliverators, and orders) will always yield the same results.

Another noteworthy aspect about the printer simulation is the way that it updates the printer state each second of the simulation. Although this approach may be appropriate for the printer simulation, it is not an appropriate approach for implementing the pizza delivery simulation. Consider what would happen if we ran the simulation with a single pizza order that is made 1,000,000,000 minutes after the start of the simulation. Checking whether something needs to be done every minute is inefficient. Instead, your implementation should make use of an event queue: An event queue contains events of interest that occur during the simulation, and events are stored in order of the time when they occur.

Your simulation should process each event in the event queue, until the event queue is empty. Each time you process an event, the "current time" in your simulation will advance to the time associated with the event. This allows you to "fast forward" to interesting events in the simulation, instead of running the simulation second by second as is done in the printer simulation of section 2.4.5.

Processing an event will entail updating the state of various objects that you need to keep track of during the simulation, including, but not limited to, the event queue itself.

You may still be confused at this point about how to implement the simulation. This is okay. Some of the details in the above description are intentionally vague. The instructor and TAs both have  office hours hours to answer your questions, and you can always ask questions on the bulletin board.

Here are some other things that you might want to keep in mind when thinking about how to solve this problem:

What to Hand In

Submissions will be done electronically.

For part 1, you need to submit
The implementation of the Stack class in the transform.py file should remain unchanged from the implementation that we provided.

For part 2, you need to submit
You do not need to submit your unit tests for part 2. (Although you should still be doing unit tests on your own to test your code.)
You should ensure that your implementation works with the PriorityQueue class in the pqueue.py file that we provide, but you do not need to submit the pqueue.py file.

Marking

Part 1: (35%)
    Correctness (60%)
    Unit tests (30%)
    Documentation & Coding Style (10%)
   
Part 2: (65%)
    Correctness (50%)
    Design (25%)
    Documentation & Coding Style (25%)