import random
import math


def hill_climbing(M, J, get_neighbours=None):
    """
    Start at a random position and greedily search the neighbourhood.
    :param M: number of features
    :param J: cost function
    :param get_neighbours: neighbour operation
    :return: indices, score
    """

    def get_unit_neighbours(indices):
        """
        Gets neighbours at unit distance from current indices.
        :param indices: current node
        :return: next nodes
        """
        # remove left and right elements
        neighbours = [indices[1:], indices[:-1]]
        # add left element
        if indices[0] > 1:
            neighbour = [indices[0] - 1] + indices
            neighbours.append(neighbour)
        # add right element
        if indices[-1] < M - 1:
            neighbour = indices + [indices[-1] + 1]
            neighbours.append(neighbour)
        return neighbours

    if not get_neighbours:
        get_neighbours = get_unit_neighbours

    indices, next_indices = [], sorted(random.sample(list(range(M)), random.randint(0, M - 1)))
    cost, next_cost = -math.inf, J(next_indices)
    while cost < next_cost:
        cost, indices = next_cost, next_indices
        for next_indices_temp in get_neighbours(indices):
            next_cost_temp = J(next_indices_temp)
            if next_cost < next_cost_temp:
                next_cost, next_indices = next_cost_temp, next_indices_temp
    return indices, cost