import numpy as np


def select_signs(candidates, residual, descent, rho=0.05):
    """Select +/- signs minimizing infinity norm under a descent constraint.

    Parameters
    ----------
    candidates : (n, m) array
        Candidate residual updates.
    residual : (m,) array
        Accumulated residual state before this round.
    descent : (m,) array
        Desired descent direction (the experiment uses the mean candidate).
    rho : float
        Required projection coefficient.

    Returns
    -------
    signs : (n,) array of +/-1
    feasible : bool
        Whether the returned signs satisfy the projection constraint.

    Exhaustive search is used for n <= 8. For larger n, a coordinate-flip
    local search is used, as proposed in the implementation plan.
    """
    candidates = np.asarray(candidates, dtype=float)
    residual = np.asarray(residual, dtype=float)
    descent = np.asarray(descent, dtype=float)
    n = candidates.shape[0]
    threshold = rho * float(descent @ descent)

    def update(s):
        return residual + s @ candidates

    def feasible(s):
        return float(descent @ (s @ candidates)) >= threshold - 1e-12

    def objective(s):
        return float(np.max(np.abs(update(s))))

    if n <= 8:
        best = None
        for mask in range(1 << n):
            s = np.array([1.0 if mask & (1 << j) else -1.0
                          for j in range(n)])
            if feasible(s):
                candidate = (objective(s), s)
                if best is None or candidate[0] < best[0]:
                    best = candidate
        if best is not None:
            return best[1], True
        return np.ones(n), False

    signs = np.ones(n)
    if not feasible(signs):
        return signs, False
    value = objective(signs)
    for _ in range(3):
        changed = False
        for j in range(n):
            trial = signs.copy()
            trial[j] *= -1
            trial_value = objective(trial)
            if feasible(trial) and trial_value < value - 1e-12:
                signs, value = trial, trial_value
                changed = True
        if not changed:
            break
    return signs, feasible(signs)


def infinity_norm(x):
    """Coordinatewise maximum norm used by the discrepancy objective."""
    return float(np.max(np.abs(np.asarray(x))))