#! /usr/bin/env python3

"""Note: unlike the course slides, the rows and columns (ranks and
files) of the puzzle are counted as {0, ..., N - 1} here (rather than
starting from 1) because this is the more common convention in
programming.

This is not an efficient implementation, as it is meant to be easy to
understand.

The code does not follow the pseudo-code in the lecture 100% due to
the need to gather statistics.

Note that the code is not fully generic in the way that state-space
search code is. Some of the assumptions about the problem are baked
directly into the algorithms, for example the fact that we are dealing
with a minimization problem.
"""

import random


def get_random_candidate(board_size):
    return [random.randrange(board_size) for _ in range(board_size)]


def get_minimum(choices):
    # Ties are broken uniformly randomly. Note that tie-breaking can
    # have a large impact on performance in COPs.
    min_h = min(h(candidate) for candidate in choices)
    return random.choice([candidate for candidate in choices
                          if h(candidate) == min_h])


def get_number_of_conflicts(candidate):
    num_conflicts = 0
    size = len(candidate)
    for index1, row1 in enumerate(candidate):
        for index2 in range(index1 + 1, size):
            row2 = candidate[index2]
            if row1 == row2 or abs(row2 - row1) == index2 - index1:
                num_conflicts += 1
    return num_conflicts


def is_solution(candidate):
    return get_number_of_conflicts(candidate) == 0


def get_neighbors(candidate):
    neighbors = []
    size = len(candidate)
    for index, row in enumerate(candidate):
        for new_row in range(size):
            if row != new_row:
                neighbor = list(candidate)
                neighbor[index] = new_row
                neighbors.append(neighbor)
    return neighbors


def h(candidate):
    return get_number_of_conflicts(candidate)


def simple_hill_climbing_with_stagnation(board_size, max_steps):
    current = get_random_candidate(board_size)
    num_steps = 0
    best = current
    for _ in range(max_steps):
        next = get_minimum(get_neighbors(current))
        current = next
        num_steps += 1
        if h(current) < h(best):
            best = current
        if h(current) == 0:
            break
    solved = is_solution(best)
    return solved, num_steps


def main(board_size, num_trials, max_steps):
    num_solved = 0
    total_steps = 0
    for trial in range(1, num_trials + 1):
        if trial % 100 == 0:
            print("trial {} out of {}...".format(trial, num_trials))
        solved, num_steps = simple_hill_climbing_with_stagnation(
            board_size=board_size, max_steps=max_steps)
        num_solved += int(solved)
        total_steps += num_steps
    print("{} out of {} trials solved ({}%)".format(
        num_solved, num_trials, 100.0 * num_solved / num_trials))
    print("average number of steps: {}".format(
        total_steps / num_trials))


if __name__ == "__main__":
    main(board_size=8, num_trials=10000, max_steps=100)