Decision Stump

Train a depth-1 decision tree (a stump) on one numeric feature. Choose the split x <= t / x > t with the smallest weighted Gini impurity (first minimum, so the smallest threshold wins ties), then predict the majority class on each side; a tied majority goes to the smaller class label.

Implement solve(x, y).

Returns. Return a tuple (threshold, left_class, right_class). If x has fewer than two distinct values there is nothing to split and ValueError is raised.

Examples

Example 1

Input:

solve([1.0, 2.0, 3.0, 4.0], [0, 0, 1, 1])

Output:

(2.0, 0, 1)

Example 2

Input:

solve([1.0, 2.0, 3.0, 4.0, 5.0], [1, 1, 1, 0, 0])

Output:

(3.0, 1, 0)

Example 3

Input:

solve([3.0, 3.0], [0, 1])

Output: Raises ValueError.