Button Combination Detection

MediumPython

Problem

A Starlink user terminal can emit button-press events while an operator performs a diagnostic sequence. Given the event stream and a required button combination, determine whether the combination appears as consecutive presses within a maximum elapsed time.

The combination must match exactly and in order. An unrelated button press breaks the current match, but a valid sequence may overlap with another possible sequence. Return True when any valid occurrence exists, otherwise return False.

Formal Specification

Implement detect_combination(events, target, max_duration).

events is a list of (button, timestamp) pairs, ordered by nondecreasing timestamp. button is a string and timestamp is an integer number of milliseconds.
target is a non-empty list of button strings describing the required sequence.
max_duration is a nonnegative integer in milliseconds.
Return a boolean. A match is valid when its first and last event timestamps differ by at most max_duration.

Constraints

1 <= len(events) <= 10^5
1 <= len(target) <= 10^4
Events are ordered by nondecreasing timestamp
0 <= timestamp <= 10^12
0 <= max_duration <= 10^12

Function Signature

def detect_combination(events, target, max_duration):

Formal Specification

Implement detect_combination(events, target, max_duration).

events is a list of (button, timestamp) pairs, ordered by nondecreasing timestamp. button is a string and timestamp is an integer number of milliseconds.
target is a non-empty list of button strings describing the required sequence.
max_duration is a nonnegative integer in milliseconds.
Return a boolean. A match is valid when its first and last event timestamps differ by at most max_duration.