~/problems / Simulation & OOP design / Object-oriented design and extensible simulations

Hot-air balloon festival stability tracker

medium ~50 min Optiver

Your team flies several hot-air balloons at a festival. Wind is produced by "wind centres" at certain altitudes, and a balloon caught in strong wind becomes unstable. Build BalloonFestival to track who is flying, how windy it is at each balloon, and which balloons are stable.

Wind

A centre at altitude c with speed s contributes s / (1 + ((h - c) / 100) ** 2) m/s at altitude h. The wind at h is the sum over all centres. Setting a centre at an altitude that already has one replaces its speed (a speed of 0 switches it off).

Stability

  • A balloon that ascends starts out stable, and is immediately checked against the wind at its new altitude.
  • Whenever the wind at a flying balloon's altitude is greater than 15, it becomes (or stays) unstable.
  • An unstable balloon becomes stable again once the wind at its altitude has been at most 15 for 300 continuous seconds. If the calm starts at time t, it is stable at every time >= t + 300, unless the wind rose above 15 again in between, which resets the clock. The calm starts at the moment the wind drops to 15 or below.
  • Descending puts the balloon on the ground and resets it to stable. Balloons on the ground are never reported.

API

Every method except the constructor takes an integer timestamp (seconds) first. A call whose timestamp is not strictly greater than the timestamp of the last successful call fails: it returns False (or [] for inspect_balloons) and changes nothing. Calls that fail for any other reason also change nothing and don't advance the clock.

  • BalloonFestival(names: list[str]): your balloons (unique names), all on the ground. No wind centres yet.
  • balloon_ascended(timestamp, name, altitude) -> bool: the balloon is now flying at altitude (a positive int). It may already be flying, in which case it moves. False for an unknown name.
  • balloon_descended(timestamp, name) -> bool: False for an unknown name or a balloon that isn't flying.
  • set_wind_speed(timestamp, center_altitude, speed) -> bool: set a centre (speed >= 0, otherwise False), then re-check every flying balloon.
  • inspect_balloons(timestamp) -> list[str]: among flying balloons that are stable at timestamp, find the highest altitude and return every stable balloon at that altitude, in the order the names were given to the constructor. [] if there is none. A valid call counts as successful even when it returns [].

The tests keep wind totals well away from exactly 15, so float rounding won't matter.

Scale: up to 1,000 balloons and thousands of wind updates. Recomputing each balloon's wind from every centre on every update is too slow; when a centre changes, adjust each balloon's total by the difference in that one centre's contribution.

f = BalloonFestival(["red", "blue", "gold"])
f.balloon_ascended(10, "red", 200)       # True
f.balloon_ascended(20, "blue", 300)      # True
f.set_wind_speed(30, 300, 20)            # True: blue sees 20 (unstable), red sees 10
f.inspect_balloons(40)                   # ["red"]
f.set_wind_speed(50, 300, 12)            # True: blue sees 12, calm since 50
f.inspect_balloons(349)                  # ["red"]
f.inspect_balloons(350)                  # ["blue"]  (300 s of calm; 300 is higher than 200)
f.balloon_descended(345, "blue")         # False: timestamp went backwards
f.balloon_descended(360, "gold")         # False: gold isn't flying

Topic: Object-oriented design and extensible simulations. Classes that survive new requirements: games, payments, subscriptions, refactors.

0:00
Ctrl ' run · Ctrl ↵ submit
esc