Bus Route Simulation – Boarding, Capacity, and Priority Passes

You are provided with a partially implemented codebase designed to simulate bus routes within a city. Buses operate along predefined routes with scheduled arrival times at each stop. Passengers arrive at various stops with specific travel intentions.

Core Entities

Each bus is defined by:

• A unique bus_id.
• A fixed capacity C, representing the maximum number of passengers allowed on board at any given time.
• A schedule: an ordered list of (time, stop_id) pairs, indicating when the bus is scheduled to arrive at each stop.

Each passenger is defined by:

• A unique passenger_id.
• appear_time: The time when the passenger arrives at their starting stop.
• from_stop: The identifier of the stop where the passenger begins their journey.
• to_stop: The identifier of the stop where the passenger intends to disembark.
• has_priority_pass: A boolean flag indicating whether the passenger holds a priority pass.

Simulation Rules

The simulation progresses in discrete time steps. At each scheduled bus arrival (time, stop_id) for a particular bus, the following sequence of events must occur:

1. The bus drops off all passengers currently on board whose to_stop matches the current stop_id.
2. The bus then picks up waiting passengers at the stop_id. Only passengers whose appear_time is less than or equal to the current time and who have not yet boarded any bus are eligible.
3. The bus must never exceed its capacity C at any point.
4. You are required to track and update the number of passengers on board the bus immediately after each drop-off and pick-up operation.

Basic data structures, such as BusSchedule and PassengerEvent, are already provided. Your task is to implement several critical functions.

Assumptions and Constraints

You may assume the following:

• The number of passenger events (E) will not exceed 100,000.
• The number of buses (B) will not exceed 1,000.
• Each bus schedule contains a maximum of 1,000 stops.
• All time values are non-negative integers.
• All bus schedules and passenger events are available in memory.
• The capacity parameter provided in Task 2 and Task 3 refers to the uniform capacity C for all buses.

Task 1: Downsample Simulation Population

The complete list of passenger events can be very large, potentially slowing down the simulation. Implement a function to downsample these passenger events. The goal is to reduce the number of simulated passengers while approximately preserving the original demand distribution across origin-destination (from_stop, to_stop) pairs.

Conceptual API:

List<PassengerEvent> downsamplePassengers(List<PassengerEvent> events, double factor)

• factor: A scaling factor, where 0 < factor <= 1 (e.g., 0.1 implies simulating approximately 10% of the passengers).
• The resulting list should contain roughly factor * events.size() passengers.
• The distribution of passengers across (from_stop, to_stop) pairs must be preserved as much as reasonably possible.

Clearly specify your strategy for selecting which passengers to retain to ensure the distribution is approximately preserved.

Task 2: Boarding and Dropping Logic with Capacity Tracking

Implement the primary simulation logic responsible for handling bus boarding and dropping. This logic must strictly enforce bus capacities and accurately track the number of passengers on board.

Conceptual API:

List<LogEntry> simulate(
    List<BusSchedule> busSchedules,
    List<PassengerEvent> passengers,
    int capacity
)

Each LogEntry object should contain:

• time
• bus_id
• stop_id
• passenger_id
• action (one of: "board", "drop")

Simulation Rules:

• For each (time, stop_id) pair in every BusSchedule, process events in strict time order.
• At each bus arrival:
  1. Drop off all passengers currently on that bus whose to_stop matches the current stop_id. Emit corresponding "drop" log entries.
  2. From the waiting passengers at stop_id (those with appear_time <= time and not yet boarded), pick up passengers without ever exceeding the bus's capacity. Emit corresponding "board" log entries.
• Initially, all buses start with zero passengers.
• You must continuously maintain and update the current passenger count for each bus after every board or drop action.

Your implementation must be efficient enough to handle the stated constraints.

Task 3: Validate Logs and Find Bugs

You will be given a log generated by a potentially buggy version of the simulation. Your task is to implement a validator function that verifies whether the log adheres to bus capacity constraints and fundamental consistency rules.

Conceptual API:

boolean validateLog(List<LogEntry> log, int capacity)

The validator must perform at least the following checks:

• Bus occupancy for any bus never becomes negative.
• Bus occupancy for any bus never exceeds the specified capacity.
• A passenger cannot drop off before having boarded a bus.
• A passenger cannot board more than once (i.e., cannot be simultaneously on multiple buses or board the same bus twice without an intervening drop-off).

You may optionally return the first error encountered (e.g., as an error description string instead of a boolean), but at minimum, it must detect log validity.

Describe the state you need to track while scanning the log and how you would update it.

Task 4: Support Priority Passengers

Extend your boarding logic from Task 2 to incorporate support for priority passes:

• Passengers holding has_priority_pass == true must be boarded before non-priority passengers when a bus arrives at a stop.
• Within the same priority level (i.e., all priority passengers, or all non-priority passengers), passengers should board in ascending order of their appear_time. If appear_time values are identical, ties should be broken consistently (e.g., by passenger_id in ascending order).
• All capacity constraints must continue to be strictly enforced.

Update your simulate(...) function to reflect this new boarding behavior, ensuring that log entries and on-board passenger counts remain accurate.

General Requirements

For all tasks, clearly define and utilize appropriate data structures, and design your solution to operate efficiently given the specified input sizes.