Convert sampling-profiler stack snapshots into a flat, properly nested trace of function **start** and **end** events suitable for a flame-graph–style visualization. ## What to implement Implement `solution(samples)` (equivalent to `samples_to_trace(samples)`). - **Input** — `samples` is a list (or tuple) of snapshots ordered by timestamp ascending. Each snapshot is a 2-item pair `(t, stack)`: - `t` is a numeric timestamp (`int` or `float`). - `stack` is a list of function names (strings). `stack[0]` is the **outermost** active function and `stack[-1]` is the **innermost**. - **Output** — a list of events. Each event is a tuple `(timestamp, kind, function_name)` where: - `timestamp` is the event's time as a **float** (each input `t` is coerced to `float` in the output, so an integer input timestamp appears as a float). - `kind` is `'s'` (the function starts) or `'e'` (the function ends). ## Rules Process the samples in input order and emit events using **exactly** these rules: 1. **First sample.** Emit a start event (`'s'`) for every frame in its stack, from **outermost to innermost**, all at that sample's timestamp. 2. **Each transition.** For each consecutive pair of samples `(prev_t, prev_stack)` → `(curr_t, curr_stack)`: - Compute the **longest common prefix** length `k`: scan the two stacks position by position and stop at the first index where the frames differ (or where one stack runs out). Frames are matched **only by position**. - Emit end events (`'e'`) at `curr_t` for the frames in `prev_stack[k:]`, ordered **deepest frame first**, up to the divergence point. - Then emit start events (`'s'`) at `curr_t` for the frames in `curr_stack[k:]`, ordered from the **divergence point down to the deepest frame**. 3. **End of capture.** The capture is assumed to end at the last sample's timestamp. After all transitions, close every frame still open in the **last** stack by emitting end events, **deepest first**, all at the last sample's timestamp. ## Important details - **Duplicate names are distinct frames.** The same function name at different depths is a different frame; match frames only by position when computing the longest common prefix. - **Empty stacks are allowed** and mean no function is active at that sample. - **Identical consecutive stacks produce no events.** When two adjacent stacks are equal, `k` equals their length, so both the end and start loops are empty (an implicit compression step). - **Equal timestamps are allowed** and must be processed in the given input order. - **Empty input** (`samples` is empty) returns an empty list. ## Validation Raise `ValueError` for malformed input, specifically when: - `samples` is not a list or tuple. - A sample is not a 2-item sequence `(timestamp, stack)`. - A timestamp is not a number (note: `bool` is **not** accepted as a number). - A stack is not a `list`. - Any frame name is not a string. - Timestamps decrease (each timestamp must be **≥** the previous one; equal timestamps are fine). ## Why this works The longest common prefix is exactly the portion of the call stack still active across both samples. Everything below that prefix in the earlier sample must have ended, and everything below that prefix in the later sample must have started. Emitting ends bottom-up and starts top-down keeps every frame properly nested. > You may imagine a synthetic root frame that is always present, but do **not** emit any events for it. ## Constraints - `0 <= len(samples) <= 200000` - `0 <= len(stack_i) <= 100000`, and the sum of all stack lengths is at most `400000` - Timestamps must be non-decreasing; equal timestamps are allowed - Each stack element must be a string; malformed input must raise `ValueError`

def solution(samples):
    def parse_sample(sample):
        if not isinstance(sample, (list, tuple)) or len(sample) != 2:
            raise ValueError('Each sample must be a 2-item sequence: (timestamp, stack)')
        t, stack = sample
        if isinstance(t, bool) or not isinstance(t, (int, float)):
            raise ValueError('Timestamp must be a number')
        if not isinstance(stack, list):
            raise ValueError('Stack must be a list of strings')
        for name in stack:
            if not isinstance(name, str):
                raise ValueError('Each frame name must be a string')
        return float(t), stack

    if not isinstance(samples, (list, tuple)):
        raise ValueError('samples must be a list or tuple')

    events = []
    if not samples:
        return events

    prev_t, prev_stack = parse_sample(samples[0])

    for name in prev_stack:
        events.append((prev_t, 's', name))

    for i in range(1, len(samples)):
        curr_t, curr_stack = parse_sample(samples[i])
        if curr_t < prev_t:
            raise ValueError('Timestamps must be non-decreasing')

        lcp = 0
        limit = min(len(prev_stack), len(curr_stack))
        while lcp < limit and prev_stack[lcp] == curr_stack[lcp]:
            lcp += 1

        for j in range(len(prev_stack) - 1, lcp - 1, -1):
            events.append((curr_t, 'e', prev_stack[j]))
        for j in range(lcp, len(curr_stack)):
            events.append((curr_t, 's', curr_stack[j]))

        prev_t, prev_stack = curr_t, curr_stack

    for j in range(len(prev_stack) - 1, -1, -1):
        events.append((prev_t, 'e', prev_stack[j]))

    return events