import logging


def hillclimb(init_function, move_operator, objective_function, max_evaluations):

    # hillclimb until either max_evaluations is reached or we are at a local optima

    best = init_function()
    best_score = objective_function(best)

    num_evaluations = 1

    logging.info('hillclimb started: score=%f', best_score)

    while num_evaluations < max_evaluations:
        # examine moves around our current position
        move_made = False
        for next in move_operator(best):
            if num_evaluations >= max_evaluations:
                break

            # see if this move is better than the current
            next_score = objective_function(next)
            num_evaluations += 1
            if next_score > best_score:
                best = next
                best_score = next_score
                move_made = True
                break  # depth first search

        if not move_made:
            break  # we couldn't find a better move (must be at a local maximum)

    logging.info('hillclimb finished: num_evaluations=%d, best_score=%f', num_evaluations, best_score)
    return num_evaluations, best_score, best


def hillclimb_and_restart(init_function, move_operator, objective_function, max_evaluations):
    # repeatedly hillclimb until max_evaluations is reached
    best = None
    best_score = 0

    num_evaluations = 0
    while num_evaluations < max_evaluations:
        remaining_evaluations = max_evaluations - num_evaluations

        logging.info('(re)starting hillclimb %d/%d remaining', remaining_evaluations, max_evaluations)
        evaluated, score, found = hillclimb(init_function, move_operator, objective_function, remaining_evaluations)

        num_evaluations += evaluated
        if score > best_score or best is None:
            best_score = score
            best = found

    return num_evaluations, best_score, best
