LAB4

import time
from collections import deque

## The Class that Represents the Puzzle

class PuzzleState(object):
    """PuzzleState class"""
    def __init__(self, config, n, parent=None, action="Initial"):
        if n*n != len(config) or n < 2:
            raise Exception("the length of config is not correct!")
        self.n = n
        self.parent = parent
        self.action = action
        self.config = config
        self.children = []
        self.cost = self.calculate_total_cost()
        for i, item in enumerate(self.config):
            if item == 0:
                self.blank_row = int( i / self.n )
                self.blank_col = i % self.n
                break

    def get_history(self):
        self.history = []
        self.next = self
        #print(self.next)
        while self.next.parent is not None:
            self.history.append(self.next)
            self.next = self.next.parent
        self.history.reverse()
        return self.history
        """
    def calculate_manhattan_dist(self):
        self.dist = 0
        for i in range(self.n**2):
            self.dist += abs(self.config[i]-i)
        return self.dist
        """
    def calculate_manhattan_dist(self):
        result = 0
        true_state = [0,1,2,3,4,5,6,7,8]
        for i in range(len(self.config)):
            x = (abs(true_state.index(self.config[i]))) // 3
            y = (abs(true_state.index(self.config[i]))) % 3
            x1 = i // 3
            y1 = i % 3
            result += (abs(x - x1) + abs(y-y1))
        return result


    def calculate_cost(self):
        return len(self.get_history())

    def calculate_total_cost(self):
        return self.calculate_manhattan_dist() + self.calculate_cost()


    def display(self):
        for i in range(self.n):
            line = []
            offset = i * self.n
            for j in range(self.n):
                line.append(self.config[offset + j])
            print(line)

    def move_left(self):
        if self.blank_col == 0:
            return None
        else:
            blank_index = int(self.blank_row * self.n + self.blank_col)
            target = blank_index - 1
            new_config = list(self.config)
            new_config[blank_index], new_config[target] = new_config[target], new_config[blank_index]
            return PuzzleState(tuple(new_config), self.n, parent=self, action="Left")

    def move_right(self):
        if self.blank_col == self.n - 1:
            return None
        else:
            blank_index = int(self.blank_row * self.n + self.blank_col)
            target = blank_index + 1
            new_config = list(self.config)
            new_config[blank_index], new_config[target] = new_config[target], new_config[blank_index]
            return PuzzleState(tuple(new_config), self.n, parent=self, action="Right")

    def move_up(self):
        if self.blank_row == 0:
            return None
        else:
            blank_index = int(self.blank_row * self.n + self.blank_col)
            target = blank_index - self.n
            new_config = list(self.config)
            new_config[blank_index], new_config[target] = new_config[target], new_config[blank_index]
            return PuzzleState(tuple(new_config), self.n, parent=self, action="Up")

    def move_down(self):
        if self.blank_row == self.n - 1:
            return None
        else:
            blank_index = int(self.blank_row * self.n + self.blank_col)
            target = blank_index + self.n
            new_config = list(self.config)
            new_config[blank_index], new_config[target] = new_config[target], new_config[blank_index]
            return PuzzleState(tuple(new_config), self.n, parent=self, action="Down")

    def expand(self):
        """expand the node"""
        # add child nodes in order of UDLR
        if len(self.children) == 0:
            up_child = self.move_up()
            if up_child is not None:
                self.children.append(up_child)

            down_child = self.move_down()
            if down_child is not None:
                self.children.append(down_child)

            left_child = self.move_left()
            if left_child is not None:
                self.children.append(left_child)

            right_child = self.move_right()
            if right_child is not None:
                self.children.append(right_child)

        return self.children

    def state(self):
        return self.config

    def test_goal(self):
        return self.config == (0,1,2,3,4,5,6,7,8)


### STUDENT CODE GOES HERE ###

def get_history(state):
    history = []
    while state.parent is not None:
        history.append(state)
        state = state.parent
    history.reverse()
    return history

def display(state):
    config = state.state()
    return "{} {} {}\n{} {} {}\n{} {} {}".format(config[0],config[1],config[2],config[3],config[4],config[5],config[6],config[7],config[8])


def bfs_search(initial_state):
    """BFS search"""

    queue = deque()
    queue.append(initial_state)
    explored = set()

    while (len(queue) != 0):

        state = queue.popleft()
        explored.add(state.state())

        if state.test_goal():
            q = len(list(elem.state() for elem in queue))
            e = len(explored)
            return state, q, e

        for neighbour in state.expand():
           if ((neighbour.state() not in queue) and (neighbour.state() not in explored)):
               queue.append(neighbour)

    return False


def dfs_search(initial_state):

    queue = []
    queue.append(initial_state)
    explored = set()

    while (len(queue) != 0):

        state = queue.pop()
        explored.add(state.state())

        if state.test_goal():
            q = len(list(elem.state() for elem in queue))
            e = len(explored)
            return state, q, e

        for neighbour in state.expand():
           if ((neighbour.state() not in queue) and (neighbour.state() not in explored)):
               queue.append(neighbour)

    return False

"""
def calculate_manhattan_dist(state,n):
    dist = 0
    for i in range(n**2):
        dist += abs(state[i]-i)
    return dist

def calculate_cost(state):
    return len(get_history(state))

def calculate_total_cost(state,n):
    return calculate_manhattan_dist(state.config,n) + calculate_cost(state)
"""

def a_star_search(initial_state):
    queue = []
    queue.append(initial_state)
    explored = set()

    while (len(queue) != 0):
        queue.sort(key=lambda x: x.cost, reverse=False)

        #input()
        state = queue.pop(0)
        explored.add(state.state())

        if state.test_goal():
            q = len(list(elem.state() for elem in queue))
            e = len(explored)
            return state, q, e

        for neighbour in state.expand():
           if ((neighbour.state() not in queue) and (neighbour.state() not in explored)):
               queue.append(neighbour)

    return False

def main():
    start_state = PuzzleState((8,6,4,2,1,3,5,7,0),3)
    #print(start_state.calculate_manhattan_dist())
    state,q,e = a_star_search(start_state)
    history = state.get_history()

    for elem in history:
        print("-----------")
        print(display(elem))
    print("-----------")
    print("Total moves: ",len(history))
    print("Total nodes explored: ", e)
    print("Total nodes opened: ", q)

if __name__ == '__main__':
    start_time = time.time()
    main()
    running_time = time.time() - start_time
    print('running time:', running_time)