First Climb in Elevation Samples, Strict and With a Tolerated Partial Descent

Elevation is sampled at regular intervals along a route. Given the samples as a list of integers, find the first climb and return its start and end indices as `[start, end]`, or `[]` if the samples contain no climb. The function supports two versions of the climb rules, chosen by a flag: - `tolerate_descent = False`, the **strict climb** (Part 1): once a climb starts, the elevation may rise or stay flat but may not go down. - `tolerate_descent = True`, the **climb with partial descent** (Part 2): a climb may dip temporarily and then continue, as long as the dip is small relative to the elevation gained so far and the route later rises above the climb's previous high point. ### Function Signature ```python def first_climb(elevations: list[int], tolerate_descent: bool) -> list[int]: ``` ### Rules **Start (both versions).** The first climb starts at the smallest index `s` such that `elevations[s + 1] > elevations[s]`, that is, at the sample immediately before the first increase. Flat samples before that increase are not part of the climb. If no such index exists, return `[]`. **End (both versions).** Let `P` be the highest elevation reached so far in the climb. The climb ends at the index where its final highest elevation is first reached; flat samples at that same elevation after it are not included. A climb always contains at least one increase, so `start < end`. **Strict climb.** From `s`, the climb continues through every sample that is greater than or equal to the previous sample. It stops at the first sample that is lower than the previous one, or at the end of the list. **Climb with partial descent.** The climb proceeds as in the strict version until a sample is lower than `P`. That sample starts a descent. The descent consists of that sample and every following sample up to, but not including, the first later sample whose elevation is strictly greater than `P`. Inside the descent the elevation may move up and down, and may return to exactly `P`, without ending the descent. Let `gain = P - elevations[s]` be the net elevation gained so far, and `loss = P - m`, where `m` is the lowest elevation inside the descent. The descent is tolerated only if both conditions hold: 1. some sample after the start of the descent is strictly greater than `P` (the route eventually rises above the previous maximum); and 2. `loss` is at most 20% of `gain`, evaluated exactly with integers as `5 * loss <= gain`. If the descent is tolerated, the climb continues from the first sample above `P`, which becomes the new high point; any later descent is judged the same way against the updated `P` and `gain`. If the descent is not tolerated, the climb ends at the index where `P` was first reached. ### Constraints - `0 <= len(elevations) <= 100000` - `-100000 <= elevations[i] <= 100000` for every `i` - The result is either `[]` or `[start, end]` with `0 <= start < end < len(elevations)`. ### Examples **Example 1** ```text Input: elevations = [3, 2, 1, 0, 0, 1, 2, 2, 3, 5, 10, 10, 7, 15], tolerate_descent = False Output: [4, 10] ``` The first increase is from index 4 (elevation 0) to index 5 (elevation 1), so the climb starts at index 4; index 3 has the same elevation but is not immediately before the rise. The elevation never decreases until index 12, and the highest elevation, 10, is first reached at index 10. With `tolerate_descent = True` the output is also `[4, 10]`: the drop from 10 to 7 has `loss = 3` against `gain = 10 - 0 = 10`, and `5 * 3 = 15 > 10`, so the descent is not tolerated even though the route later rises to 15. **Example 2** ```text Input: elevations = [5, 5, 6, 10, 20, 25, 24, 26, 30, 28], tolerate_descent = True Output: [1, 8] ``` The climb starts at index 1. The high point 25 is reached at index 5, with `gain = 25 - 5 = 20`. The dip to 24 has `loss = 1`, and `5 * 1 = 5 <= 20`; index 7 (elevation 26) rises above 25, so the descent is tolerated. The new high point 30 is reached at index 8. The drop to 28 at index 9 is never followed by a sample above 30, so that descent is not tolerated and the climb ends at index 8. With `tolerate_descent = False` the output is `[1, 5]`. **Example 3** ```text Input: elevations = [0, 10, 8, 11, 11, 9, 10], tolerate_descent = True Output: [0, 3] ``` The dip from 10 to 8 loses exactly 20% of the gain (`5 * 2 = 10 <= 10`), and index 3 (elevation 11) rises above 10, so it is tolerated. The high point 11 is first reached at index 3; the flat sample at index 4 is not included. The later dip to 9 is small enough (`5 * 2 = 10 <= 11`), but the route only returns to 10 and never rises above 11, so it is not tolerated and the climb ends at index 3. With `tolerate_descent = False` the output is `[0, 1]`.