Design a Balloon Festival Simulator
Overview
This question evaluates proficiency in data structures, event-driven simulation, numerical aggregation of spatially varying fields, and time-based state tracking for mutable entities.
Implement a class BalloonFestival with the following API and rules.
Goal Track hot air balloons (yours and competitors), evolving wind fields, and balloon stability over time. When inspected at a timestamp, return the sorted names of your team’s balloons that are stable and flying at or above the highest stable competitor balloon.
Initialization init(yourBalloonNames: list[str])
- Registers the set of balloon names that belong to your team; all other names that appear later are competitors.
- Each balloon name is unique.
- Constraint: 1 ≤ len(yourBalloonNames) < 2^20.
Operations BalloonAscended(timestamp: float, balloonName: str, altitude: float) -> bool
- Marks a balloon as ascended to the given altitude and updates its state.
- Balloons are stable by default upon ascending.
- Returns True if the state was updated successfully; otherwise False.
BalloonDescended(timestamp: float, balloonName: str) -> bool
- Marks a balloon as descended to the ground and resets its stability to the default.
- Returns True on success; otherwise False.
SetWindSpeed(timestamp: float, altitude: float, windSpeed: float) -> bool
- Updates the wind speed centered at the given altitude.
- Constraints: 0 < altitude < 2^15, 0 ≤ windSpeed < 2^5.
- Returns True on success; otherwise False.
InspectBalloons(timestamp: float) -> list[str]
- Returns the sorted names of your team’s balloons that are stable at the given timestamp and whose altitudes are ≥ the highest stable competitor balloon at that timestamp. If none qualify, return [].
Stability Rules
- A balloon becomes immediately unstable if the wind speed at its altitude exceeds 15 m/s.
- An unstable balloon regains stability only after it has remained at an altitude where the wind speed is ≤ 15 m/s for at least 300 seconds (inclusive).
Wind Model
- Wind from multiple defined altitudes adds cumulatively.
- Let WindSpeedAtAltitude be the wind defined at WindAltitude, and h be a balloon’s current altitude.
- The contribution from that wind source at altitude h is: WindSpeed(h) = WindSpeedAtAltitude / (1 + ((h - WindAltitude) / 100)^
- The total wind speed at altitude h is the sum of contributions from all defined wind sources at the inspection time.
Requirements
- Design data structures and algorithms to support the above operations correctly and efficiently over many events.