Isolation Path Length

Compute the path length of a point in one random isolation 'tree' (as used by Isolation Forest). Start with the interval [lo, hi]; repeatedly draw a random split uniformly inside it with rng.uniform(lo, hi), count one level, and keep the side containing x (x <= split keeps the left side). Stop when the interval is empty (lo >= hi) or after max_depth splits.

Implement solve(x, lo, hi, max_depth, rng).

Returns. Return the number of splits performed as an int. rng is a numpy.random.Generator.

Examples

Example 1

Input:

solve(3.0, 0.0, 10.0, 5, np.random.default_rng(0))

Output:

5

Example 2

Input:

solve(0.0, 5.0, 5.0, 10, np.random.default_rng(1))

Output:

0