Autopilot for a Submarine Navigating Shifting Reef Gaps

A side-scrolling submarine game moves a sub to the right at a constant speed while it slowly sinks. Blowing ballast on a tick gives the sub a fixed upward velocity for that instant; otherwise it keeps sinking under constant downward drift. Reef pairs rise from the sea floor and hang from the surface, each pair leaving a gap the sub must pass through; touching a reef, the floor, or the surface ends the run. Instead of a player tapping a key, your code decides on every tick whether to blow ballast.

The controller is graded on several maps it has never seen, which differ in gap heights from one reef pair to the next and from one map to another — a controller tuned to one map's exact timings does not count.

Assume the following interface, and confirm the exact physics with the interviewer before relying on them:

from dataclasses import dataclass


@dataclass
class Reef:
    x_left: float      # left edge of the reef pair
    x_right: float     # right edge of the reef pair
    gap_bottom: float  # top of the lower reef
    gap_top: float     # bottom of the upper reef


@dataclass
class SubState:
    x: float          # sub's horizontal position (center)
    y: float          # sub's depth above the floor (center); y grows upward
    vy: float         # vertical velocity this tick; positive means rising
    reefs: list       # reefs the controller can see, sorted by x_left


def should_surface(state: SubState) -> bool:
    """Called once per tick. Return True to blow ballast on this tick."""

Constraints and Clarifications

• Assumed physics, one tick at a time: blowing ballast sets vy to a fixed positive value; otherwise vy decreases by a constant sink rate each tick. The sub's x then advances by a constant forward speed and y changes by the new vy.
• The sub, the floor, and the surface all have a small fixed radius/thickness to account for when checking collisions.
• The game is fully deterministic and the physics constants are known in advance.

Clarifying Questions

• How far ahead can the controller see — only the next reef, or the whole visible list?
• Is there a per-tick time budget the controller must respect?
• Should the same function handle an already-unwinnable state gracefully, or can it assume the state it's called with is always survivable?