Problem 3

Simulate a shopping queue in discrete steps.

Here are the inputs:

• Number of checkouts with the respective efficiency p_0, p_1, ..., p_n with 0 <= p_i < 1. In every step, the cashier i scans with a probability p_i an item from the shopping cart of the customer at the front of the queue. When all the items from the shopping cart have been scanned, the customer leaves the queue.

• A new customer shows up with a probability e, 0 <= e < 1 at every step and enters one of the queues at random.

• The size of the shopping cart w. Every customer has a random number of items between 0 and w.

(We removed the feature “laziness factor” from the original problem statement. The feature was not very clear to us, and would not have had much impact on the contracts.)

Provide the following metrics of the simulation:

• finished: Number of people who left the queue at the end of the simulation.

• avg_queue_lengths: A list of the average length of each queue during the simulation

• max_queue_lengths: A list of the maximum length of each queue during the simulation

Classes:

Probability(value)	Represent a probability value.
Specs(checkout_efficiencies, ...)	Specify the parameters of the simulation.
Stats(finished, avg_queue_lengths, ...)	Structure the results of the simulation.
Customer(items_in_cart)	Represent the current state of the customer in the simulation.

Functions:

simulate(specs, steps)

Simulate in steps number of iterations according to the specs.

class Probability(value: float)

Represent a probability value.

Methods:

__new__(cls, value)

Enforce the properties of a probability on value.

static __new__(cls, value: float) → Probability

Enforce the properties of a probability on value.

Requires

• 0 <= value < 1

class Specs(checkout_efficiencies: List[Probability], new_customer_probability: Probability, max_cart_size: int)

Specify the parameters of the simulation.

Methods:

__init__(checkout_efficiencies, ...)	Initialize with the given values.
__repr__()	Represent the specs for easier debugging.

__init__(checkout_efficiencies: List[Probability], new_customer_probability: Probability, max_cart_size: int) → None

Initialize with the given values.

Requires

• len(checkout_efficiencies) > 0

• max_cart_size >= 1

__repr__() → str

Represent the specs for easier debugging.

class Stats(finished: int, avg_queue_lengths: List[float], max_queue_lengths: List[float])

Structure the results of the simulation.

Methods:

__init__(finished, avg_queue_lengths, ...)

Initialize with the given values.

__init__(finished: int, avg_queue_lengths: List[float], max_queue_lengths: List[float]) → None

Initialize with the given values.

Requires

• all(
      a_max >= 0
      for a_max in max_queue_lengths
  )
  

• all(
      an_avg >= 0
      for an_avg in avg_queue_lengths
  )
  

• finished >= 0

class Customer(items_in_cart: int)

Represent the current state of the customer in the simulation.

Methods:

__init__(items_in_cart)

Initialize with the given values.

__init__(items_in_cart: int) → None

Initialize with the given values.

Requires

• items_in_cart >= 0

simulate(specs: Specs, steps: int) → Stats

Simulate in steps number of iterations according to the specs.

Requires

• steps >= 1

Ensures

• len(result.max_queue_lengths) == len(specs.checkout_efficiencies)

• len(result.avg_queue_lengths) == len(specs.checkout_efficiencies)

• all(
      avg_queue_length <= max_queue_length
      for avg_queue_length, max_queue_length in zip(
          result.avg_queue_lengths, result.max_queue_lengths)
  )