# CSCI 151 Lab 11: Ice Cream Store

## Overview

In this lab, we will use a heap-based priority queue to implement a *discrete event simulation*. This lab will:

- Give you practice using the priority queue API, and show you a (somewhat) real-world application of priority queues.
- Give you practice working with a program constructed from many interacting classes.

## Description

You are the manager of a new ice cream store, and you are trying to decide how many seats to put in your store so as to maximize your profit. In order to help you decide, you want to write a simulation that will test the outcome for different possibilities. Based on your observations of other ice cream stores, you have decided on the following scenario for your simulation.

Every so often, one or more groups of 1–6 people enter your store. You may assume that the number of groups entering at each time step follows a Poisson distribution with average 0.2 (that is, on average, one group of people enters your store every five time steps; you do not need to know what a Poisson distribution is). However, if there are not enough empty seats for everyone in a group, the group will leave. Also, if there are too many empty seats, they may assume that your store isn’t cool and leave to go to a different ice cream store. In particular, if the ratio of empty seats to the total number of seats is \(e\), then they will leave with probability \(C e\), where \(C\) is the “coolness parameter”. We will use a value of \(C = 3/4\). For example, if your store has 10 seats and 4 of them are occupied, then \(e = 6/10 = 3/5\), and a new group entering your store will leave with probability \(3/4 \cdot 3/5 = 9/20\).

If there are enough seats and the group thinks your store is cool, they will sit down. After a few minutes (a random number from 1–5) they will order some ice cream. Each person in the group will order a random number of scoops from 1–4 (you can decide how much to charge per scoop). Then they will stay while they eat their ice cream; you may assume that the amount of time a group stays follows a Poisson distribution with an average of 10 time steps. After they finish their ice cream, they will leave, vacating their seats.

## Setup

- Create a new Java project in Eclipse.
- Download DiscreteEventSimulation.java, Event.java, and PoissonGenerator.java, and import them into your project.
- ExponentialGenerator.java is also provided, but its use is optional. See below for an explanation of what it is and how to use it.

## Notes

To generate random numbers from a uniform distribution, you can use

`System.Random`

. First, add`import java.util.Random`

to the top of your file. Then, create a`Random`

object, and use it to generate random numbers:`Random r = new Random(); int dieRoll = r.nextInt(6) + 1; double prob = r.nextDouble(); // uniform on [0,1)`

Note that

`nextInt(n)`

generates a random integer between 0 and 5. Adding 1 means the result will be a random integer between 1 and 6.**Important note**: don’t create a new`Random`

object every time you want to generate a random number! If you need to generate a bunch of random numbers, make one`Random`

object and call`nextInt()`

on it repeatedly.*Be sure to compute the coolness parameter using floating-point arithmetic.*For example, writing`(3/4)*(emptySeats/numSeats)`

*will not work*since`3/4 == 0`

due to integer division, and probably`emptySeats/numSeats == 0`

as well, assuming both variables have type`int`

.To use

`PoissonGenerator`

, create a`PoissonGenerator`

object with the desired average as a parameter. Then you can call`nextInt()`

repeatedly to generate e.g. for each time step, call nextInt() to find out how many groups will arrive at that time step.If the objects of a class will all need to generate random numbers, you should make a random generator object (either

`Random`

or`PoissonGenerator`

) which is a*static*field. This means there will be only a*single*copy of the field shared by*all*objects of the class. For example:`public class Foozle { private static PoissonGenerator pois = new PoissonGenerator(10); ... }`

In this example, all

`Foozle`

objects will have access to single, shared, poisson generator called`pois`

.

## What to implement

You have three main tasks to complete; there is no particular order in which you must complete them, since each ends up depending on one of the others in some way.

Fill in the missing methods in

`DiscreteEventSimulation`

(namely,`run`

and`scheduleEvent`

).Fill in the implementation of

`Event.compareTo`

, so`Events`

can be stored in a priority queue.Create an

`IceCreamStore`

class which`extends DiscreteEventSimulation`

.`IceCreamStore`

should have whatever additional fields you need to keep track of the store (*e.g.*number of seats available, current profits,*etc.*), as well as appropriate methods for manipulating these fields. It does not matter what fields and methods you use, but some choices are better than others—good abstractions here will make your life easier when implementing the different`Events`

.The constructor should take a

`maxTime`

along with whatever other parameters you need to initialize your fields. Note the constructor does not need to take a`Queue`

as a parameter; you will create the initial queue as part of the constructor.The first thing the constructor needs to do is call

`super`

to run the constructor for`DiscreteEventSimulation`

. Your constructor should look something like this:`public IceCreamStore(int maxTime, ...) { super(initialEventQueue(maxTime), maxTime); ...`

Now write an

`initialEventQueue`

method to create the initial queue of events:`private static PriorityQueue<Event> initialEventQueue(int maxTime) { ... }`

`initialEventQueue`

should create an empty priority queue, and then add some initial events to it as follows:For each time step

`t`

from 1 to the max number of time steps, generate an integer using a`PoissonGenerator`

with parameter 0.2. This will be the number of groups that arrive at time`t`

.For each group, pick a random number of people from 1–6 and create an

`EnterEvent`

for that group at time`t`

, and add it to the event queue.

Note, however, that this is slow: it takes time \(O(T)\) where \(T\) is the total number of time steps for the simulation. Alternatively, you can use the provided

`ExponentialGenerator`

which generates values from an exponential distribution. The exponential distribution corresponds to the*time interval between*events of a Poisson process. To generate events this way:- Create an
`ExponentialGenerator`

with parameter 0.2. - Initialize a variable
`double time`

with the output of the`nextDouble`

method of the exponential generator. - As long as
`time`

is less than or equal to the total number of time steps:- Create an
`EnterEvent`

at time`Math.floor(time)`

. - Increment
`time`

by the exponential generator’s`nextDouble`

.

- Create an

This creates one event per loop iteration, so it is \(O(E)\), where \(E\) is the total number of events. Since in our case there is on average one enter event for every five time steps, this will be faster than the previous method.

Create three classes called

`EnterEvent`

,`OrderEvent`

, and`LeaveEvent`

. Each should`extend Event`

, which means you will have to override the`processEvent`

method.Note the implementation of

`processEvent`

is given a`DiscreteEventSimulation`

, but it will always in fact be an`IceCreamStore`

. You should just cast it, like so:`IceCreamStore store = (IceCreamStore)sim;`

Finally, you should implement an

`IceCreamMain`

class with a`main`

method which sets up and runs a simulation.

Here is some sample output from my solution, when an ice cream store with 10 seats is simulated for 20 time steps. Yours does not have to look exactly like this, but should contain similar information.

```
-- Time 3 -------------------
A group of size 1 enters.
They sit down.
There are now 9 available seats.
They will order in 4 minutes.
-- Time 7 -------------------
A group of 1 people is ready to order.
#1 orders 1 scoops.
They will leave in 9 minutes.
-- Time 9 -------------------
A group of size 2 enters.
They decide your store is not cool.
-- Time 11 -------------------
A group of size 5 enters.
They sit down.
There are now 4 available seats.
They will order in 4 minutes.
-- Time 13 -------------------
A group of size 6 enters.
There are not enough seats. They leave.
-- Time 15 -------------------
A group of 5 people is ready to order.
#1 orders 3 scoops.
#2 orders 1 scoops.
#3 orders 4 scoops.
#4 orders 3 scoops.
#5 orders 4 scoops.
They will leave in 13 minutes.
-- Time 16 -------------------
A group of size 1 leaves.
There are now 5 available seats.
The store made a total profit of $5.
```

## Evaluation

Simulate the ice cream store with every possible number of seats from 1 to 100. For each number of seats, run ten simulations of 5000 steps each, and average the results.

Make a graph of your results. What is the optimal number of seats? How do you think this depends on the “coolness parameter” \(C\)? What else might affect the optimal number of seats? Write up your answers in an evaluation document.