Trip State Transitions

Easy

State Machine · Uber

A ride-hailing service tracks each trip with a small state machine. Every trip starts in state "REQUESTED".

You are given:

transitions: a dict mapping a state to the list of states a trip may move to from it. A state that is not a key has no outgoing transitions.
events: a list of [trip_id, from_state, to_state, ts] change requests. ts is an integer timestamp. The log is not sorted by time.

Process the events in increasing ts order; events with equal ts are processed in their original list order. An event succeeds if, at the moment it is processed:

the trip's current state equals from_state, and
to_state is in transitions[from_state].

A successful event moves the trip to to_state. A failed event changes nothing. Trips are independent of each other.

Return a list of booleans where position i is True if events[i] succeeded and False otherwise (results in the original input order, not processing order).

Example 1

Input:: events = [["t1", "REQUESTED", "MATCHED", 5], ["t1", "MATCHED", "COMPLETED", 9], ["t1", "MATCHED", "IN_PROGRESS", 7]], transitions = {"REQUESTED": ["MATCHED", "CANCELLED"], "MATCHED": ["IN_PROGRESS", "CANCELLED"], "IN_PROGRESS": ["COMPLETED"]}
Output:: [True, False, True]
Explanation: Sorted by time, the trip goes REQUESTED -> MATCHED at 5 and MATCHED -> IN_PROGRESS at 7. At 9 the event claims the trip is MATCHED, but it is now IN_PROGRESS, so it fails.

Example 2

Input:: events = [["a", "REQUESTED", "COMPLETED", 1], ["b", "REQUESTED", "CANCELLED", 2], ["b", "CANCELLED", "MATCHED", 3]], transitions = {"REQUESTED": ["MATCHED", "CANCELLED"], "MATCHED": ["IN_PROGRESS", "CANCELLED"], "IN_PROGRESS": ["COMPLETED"]}
Output:: [False, True, False]
Explanation: COMPLETED is not reachable directly from REQUESTED. Trip b is cancelled at 2, and CANCELLED has no outgoing transitions, so the event at 3 fails.

Example 3

Input:: events = [["t", "REQUESTED", "MATCHED", 4], ["t", "REQUESTED", "CANCELLED", 4]], transitions = {"REQUESTED": ["MATCHED", "CANCELLED"], "MATCHED": ["IN_PROGRESS", "CANCELLED"], "IN_PROGRESS": ["COMPLETED"]}
Output:: [True, False]
Explanation: Both events have ts = 4, so they run in list order. The first moves the trip to MATCHED, so the second no longer sees REQUESTED.

Constraints

0 <= events.length <= 10^5
Each event is [trip_id, from_state, to_state, ts] with string ids and states and integer 0 <= ts <= 10^9
transitions has at most 20 keys; state names are non-empty uppercase strings