Implement bus route simulation features

Bus Route Simulation – Boarding, Capacity, and Priority Passes

You are given a partially implemented codebase for simulating bus routes in a city. Buses travel along fixed routes with scheduled arrival times at each stop. Passengers appear at stops and want to travel to other stops.

Each bus has:

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

Each passenger has:

• A unique passenger_id .
• appear_time : when the passenger appears at a stop.
• from_stop : the stop where they start.
• to_stop : the stop where they want to get off.
• has_priority_pass : a boolean indicating whether the passenger has a priority pass.

The simulation runs in discrete time. At each scheduled bus arrival (time, stop_id) for a bus:

1. The bus drops off all passengers currently on the bus whose to_stop equals stop_id .
2. The bus picks up waiting passengers at stop_id whose appear_time <= time and who have not yet boarded any bus.
3. The bus must never exceed capacity C .
4. You must track and update the number of passengers on board after each drop-off and pick-up.

The codebase defines basic data structures like BusSchedule and PassengerEvent, but several key functions are left for you to implement.

You may assume:

• Number of passenger events E is up to 100,000.
• Number of buses B is up to 1,000.
• Each bus schedule has at most 1,000 stops.
• All times are non-negative integers and you can assume that bus schedules and passenger events are available in memory.

Task 1 – Reduce Simulation Population

The full list of passenger events may be very large, making the simulation slow. Implement a function to downsample the passenger events to reduce the number of simulated passengers while approximately preserving the demand distribution across origin–destination pairs.

API (conceptual):

where:

• 0 < factor <= 1 is a scale factor (e.g., 0.1 means simulate ~10% of the passengers).
• The result should:
  • Contain roughly factor * events.size() passengers.
  • Preserve the distribution of passengers across (from_stop, to_stop) pairs as much as reasonably possible.

Specify clearly how you choose which passengers to keep so that the distribution is roughly preserved.

Task 2 – Boarding and Dropping Logic with Capacity Tracking

Implement the main simulation logic that handles bus boarding and dropping, ensuring capacities are never exceeded and on-board counts are correctly tracked.

API (conceptual):

where each LogEntry has:

• time
• bus_id
• stop_id
• passenger_id
• action in {"board", "drop"}

Simulation rules:

• For each (time, stop_id) in each BusSchedule , process events in time order .
• At each bus arrival:
  1. Drop off all passengers on that bus whose to_stop == stop_id (emit "drop" log entries).
  2. Among waiting passengers at stop_id with appear_time <= time and not yet boarded any bus, pick up passengers without ever exceeding capacity .
• Initially, all buses have zero passengers.
• You must maintain and update the current passenger count for each bus after each board / drop .

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

Task 3 – Validate Logs and Find Bugs

You are given a log generated by some (possibly buggy) version of the simulation. You need to verify whether the log respects the bus capacity constraints and basic consistency rules.

API (conceptual):

The validator should check at least the following:

• Bus occupancy for any bus never becomes negative .
• Bus occupancy for any bus never exceeds capacity .
• A passenger cannot drop off before boarding .
• A passenger cannot board more than once (i.e., cannot be on multiple buses or board the same bus twice).

You may also return the first error found (e.g., by returning an error description instead of just boolean), but at minimum you must be able to detect whether the log is valid or not.

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

Task 4 – Support Priority Passengers

Extend your boarding logic in Task 2 to support priority passes:

• Passengers with has_priority_pass == true should be boarded before non-priority passengers when a bus arrives at a stop.
• Within the same priority level (priority vs non-priority), passengers should board in arrival order ( appear_time ascending, breaking ties consistently, e.g., by passenger_id ).
• Capacity constraints must still be strictly enforced.

Update simulate(...) so that log entries reflect this behavior, and the on-board passenger counts remain correct.

For all tasks, clearly define and use appropriate data structures, and design your solution to run efficiently for the given input sizes.