lab1

#  4, 8, 1,       1, 2, 3,
#  0, 3, 6,  ->   8, 0, 4,
#  2, 7, 5        7, 6, 5

import sys
import enum
import psutil
import os
from time import process_time

START_TIME = 0  # время запуска программы
TIME_STOP = 0 # время окончания программы
TREE = None  # дерево решения
DEBUG = False
''' Если True, то каждый шаг придётся нажимать enter'''

class Tree:
    ''' Класс представления дерева '''
    # Все его методы - статические, т.к. дерево - единственное
    __nodes = None
    '''Все узлы'''

    def __init__(self):
        node = Node(get_initial_state(), None, None, 0, 0)
        self.__nodes = {0: [node]}

    def add_node(self, level: int, new_node: "Node"):
        ''' Добавить узел в дерево '''
        if level not in self.__nodes:
            self.__nodes[level] = [new_node]
        else:
            self.__nodes[level].append(new_node)

    def getNode(self, node: int) -> list["Node"]:
        '''Получить список узлов по глубине'''
        return list(self.__nodes[node])

    def print_node(self, node: "Node"):
        ''' Вывод узла на экран '''
        parent_id: int = 0
        if(node.parent_node):
            parent_id = node.parent_node.node_id
        node_prev_action: str = None
        if(node.previous_action):
            node_prev_action = node.previous_action.name
        print(f"id = {node.node_id}, parent_id = {parent_id}, " +
            f"action = {node_prev_action}, \ndepth = {node.depth}, " +
            f"cost = {node.path_cost}, state: ")
        self.print_state(node.current_state)
        print("")

    def print_state(self, state: list):
        ''' Вывод состояния в три ряда'''
        for i in range(9):
            if (i % 3 == 0 and i != 0):
                 print("")
            print(state[i] if state[i] != 0 else " ", end=" ")

    def print_path(self, node: "Node", isReversed = False):
        ''' Вывод пути на экран '''
        path = []
        current_node = node

        while current_node.parent_node:
            path.append(current_node)
            current_node = current_node.parent_node
        path.append(current_node)
        if (isReversed):
            path = path[::-1]
        for path_node in path:
            self.print_node(path_node)
            print("\t^\n\t|\n")


class Action(enum.Enum):
    ''' Перечисление действий над полем '''
    UP = 1
    DOWN = 2
    RIGHT = 3
    LEFT = 4

class Node:
    ''' Класс представления узла '''
    current_state: list = None
    ''' Начальное состояние'''
    parent_node: "Node" = None
    ''' Указатель на родительский узел'''
    previous_action: Action = None
    '''Действие, которое было применено к родительскому узлу для формирования данного узла'''
    path_cost: int = 0
    '''Стоимость пути от начального состояния до данного узла g(n)'''
    depth: int = 0
    '''Количество этапов пути от начального состояния (глубина)'''
    node_id: int = 0

    nodes_count = 0

    def __init__(self, state: list, parent: "Node", action: Action, cost: int, depth: int):
        self.current_state = state
        self.parent_node = parent
        self.previous_action = action
        self.path_cost = cost
        self.depth = depth
        self.node_id = Node.nodes_count
        Node.nodes_count += 1

    @classmethod
    def get_nodes_count(cls) -> int:
        ''' Статический метод класса, возвращающий количество узлов '''
        return cls.nodes_count + 1

def get_initial_state() -> list:
    ''' Получение начального состояния игры (Вариант 7) '''
    return [4, 8, 1,
            0, 3, 6,
            2, 7, 5 ]

def get_finish_state() -> list:
    ''' Получение конечного состояния игры (Вариант 7) '''
    return [1, 2, 3,
            8, 0, 4,
            7, 6, 5 ]

def check_final(current_state: list) -> bool:
    ''' Проверка, является ли данное состояние конечным '''
    return current_state == get_finish_state()

def state_hash(state: list) -> int:
    ''' Хэширование состояния (листа)'''
    hash = 7
    for i in state:
        hash = 31*hash + i
    return hash

def print_info(iterations: int, time: float):
    print(f"Итого узлов: {Node.get_nodes_count()}")
    print(f"Итого итераций: {iterations}")
    print(f"Потраченное время процессора: {time*1000} миллисекунд")
    print(f"Памяти использовано: {psutil.Process(os.getpid()).memory_info().rss} байтов")

def state_swap(new_states: dict, current_state: list, i: int, j: int, action: Action):
    state = list(current_state)
    state[i], state[j] = state[j], state[i]
    new_states[action] = state

def get_new_states(current_state: list) -> dict[Action, list[Node]]:
    ''' Получение новых состояний поля '''
    #В словаре ключ - действие для получения состояния, значение - само состояние
    new_states = {}
    pos = current_state.index(0)
    # up
    if pos not in (0, 1, 2):
        state_swap(new_states, current_state, pos, pos-3, Action.UP)
    # down
    if pos not in (6, 7, 8):
        state_swap(new_states, current_state, pos, pos+3, Action.DOWN)
    # right
    if pos not in (2, 5, 8):
        state_swap(new_states, current_state, pos, pos+1, Action.RIGHT)
    # left
    if pos not in (0, 3, 6):
        state_swap(new_states, current_state, pos, pos-1, Action.LEFT)
    return new_states

def bfs():
    '''Поиск в ширину'''
    cur_lvl: int = 0
    hashes = set()
    step_i: int = 1
    iteration_count: int = 0
    while(True):
        nodes_previous_lvl = TREE.getNode(cur_lvl)
        cur_lvl+=1
        if(DEBUG): print(f"Глубина = {cur_lvl}")
        for node_i in nodes_previous_lvl:
            if(DEBUG):
                print("\nТекущий узел:")
                TREE.print_node(node_i)
            new_states_dict = get_new_states(node_i.current_state)
            new_nodes: list[Node] = []
            if(DEBUG): print("\nЕго дети:")
            for new_action in new_states_dict:
                new_state = new_states_dict[new_action]
                new_state_hash: int = hash(tuple(new_state))
                if (new_state_hash in hashes):
                    if(DEBUG):
                        print("Вывод состояния: ")
                        TREE.print_state(new_state)
                    continue
                new_node = Node(new_state, node_i, new_action, cur_lvl, cur_lvl) 
                # Поиск в ширину - это частный случай поиска по критерию стоимости, когда стоимость равна глубине.
                new_nodes.append(new_node)
                hashes.add(new_state_hash)
                TREE.add_node(cur_lvl, new_node)
                if(DEBUG): TREE.print_node(new_node)
            for new_node_i in new_nodes:
                iteration_count+=1
                if(check_final(new_node_i.current_state)):
                    if(DEBUG):
                        print("Ответ найден!")
                        TREE.print_node(new_node_i)
                    TIME_STOP = process_time()
                    TREE.print_path(new_node_i)
                    print_info(iteration_count, TIME_STOP - START_TIME)
                    exit(0)
        if(DEBUG):
            print(f"Текущий шаг: {step_i}. Нажмите Enter... ")
            input()
        step_i += 1

def bnode_idirectional_search():
    ''' Двунаправленный поиск '''
    start = Node(get_initial_state(), None, None, 0, 0)
    goal = Node(get_finish_state(), None, None, 0, 0)
    #came_from[i] - словарь узлов из [i] дерева
    #queue1[i] - очереди непосещенных вершин со стороны [i] дерева
    #visited[i] - множество вершин, посещенных из [i] дерева
    queue1, queue2 = list([start]), list([goal])
    visited1, visited2 = set([state_hash(start.current_state)]), set([state_hash(goal.current_state)])
    came_from1, came_from2 = {start: None}, {goal: None}
    found = False
    meet: Node = None
    iterations: int = 0
    step_i: int = 1
    
    while not found and (len(queue1) or len(queue2)):
        iterations += 1
        if len(queue1):#для стартового узла
            current1 = queue1.pop()
            if(DEBUG):
                print("\nТекущий узел (из левого дерева):")
                TREE.print_node(current1)
                print("\t\tЕго дети: ")
            if state_hash(current1.current_state) in visited2:
                meet = current1; 
                found = True; 
                break
            for action, nodeState in get_new_states(current1.current_state).items():
                node = Node(nodeState, current1, action, current1.depth + 1, current1.depth + 1)
                # Поиск в ширину - это частный случай поиска по критерию стоимости, когда стоимость равна глубине.
                if state_hash(node.current_state) not in visited1:
                    if (DEBUG): TREE.print_node(node)
                    visited1.add(state_hash(node.current_state))
                    queue1.insert(0, node)
                    came_from1[node] = current1
        if len(queue2):
            current2 = queue2.pop()
            if(DEBUG):
                print("\nТекущий узел (из правого дерева):")
                TREE.print_node(current2)
                print("\t\tЕго дети: ")
            if state_hash(current2.current_state) in visited1: 
                meet = current2; 
                found = True; 
                break
            for action, nodeState in get_new_states(current2.current_state).items():
                node = Node(nodeState, current2, action, current2.depth + 1, current2.depth + 1)
                if state_hash(node.current_state) not in visited2:
                    if (DEBUG): TREE.print_node(node)
                    visited2.add(state_hash(node.current_state)); 
                    queue2.insert(0, node); 
                    came_from2[node] = current2
        if (DEBUG):
            print(f"Текущий шаг: {step_i}. Нажмите Enter... ")
            input()
        step_i += 1
    if found:
        TIME_STOP = process_time()
        if (DEBUG):
            print("Найденный узел:")
            TREE.print_node(meet)
        #meet == current2, поэтому, в данном случае, выводим current1
        TREE.print_path(meet, True)
        if (meet == current2):
            TREE.print_path(current1)
        else: TREE.print_path(current2)
        print_info(iterations, TIME_STOP - START_TIME)
    else: 
        print('Нет пути между {} и {}'.format(start.current_state, goal.current_state))

if __name__ == '__main__':
    START_TIME = process_time()
    TREE = Tree()

    if len(sys.argv) == 2:
        if sys.argv[1] == '--bfs':
            bfs()
        elif sys.argv[1] == '--bds':
            bnode_idirectional_search()
        elif sys.argv[1] == '-h':
            print(f"{sys.argv[0]} --bfs - breadth-first search algorithm")
            print(f"{sys.argv[0]} --bds - BiDirectional Search algorithm")
        else:
            print(
                f"Ошибка! Неверный параметр. \nВведите {sys.argv[0]} -h  \n")
    else:
        print(
            f"Ошибка! Неверное кол-во параметров. \nВведите {sys.argv[0]} -h \n")