127 lines
4.0 KiB
Python
127 lines
4.0 KiB
Python
from typing import List
|
|
from num_map import num_matrix
|
|
|
|
MAX_ROWS = 15
|
|
MAX_COLS = 25
|
|
|
|
|
|
class State:
|
|
"""
|
|
Directions
|
|
UP: 0
|
|
RIGHT: 1
|
|
DOWN: 2
|
|
LEFT: 3
|
|
"""
|
|
def __init__(self, row, column, direction):
|
|
self.direction = direction
|
|
self.row = row
|
|
self.column = column
|
|
|
|
def rotate_left(self):
|
|
return (self.direction - 1) % 4
|
|
|
|
def rotate_right(self):
|
|
return (self.direction + 1) % 4
|
|
|
|
|
|
class Node:
|
|
def __init__(self, state: "State", parent=None, action=None):
|
|
self.state = state
|
|
self.parent = parent
|
|
self.action = action
|
|
|
|
|
|
def is_valid_move(num_map, target_row, target_column):
|
|
if 0 <= target_row < MAX_ROWS and 0 < target_column < MAX_COLS:
|
|
return True
|
|
return False
|
|
|
|
|
|
def get_successor(state: "State", num_matrix):
|
|
successors = list()
|
|
direction = state.direction
|
|
row = state.row
|
|
col = state.column
|
|
|
|
rotate_left = State(row=state.row, column=state.column, direction=state.rotate_left())
|
|
rotate_right = State(row=state.row, column=state.column, direction=state.rotate_right())
|
|
|
|
successors.append(('rotate_left', rotate_left))
|
|
successors.append(('rotate_right', rotate_right))
|
|
|
|
if direction == 0:
|
|
if is_valid_move(num_map=num_matrix, target_row=row-1, target_column=col):
|
|
forward = State(row=row-1, column=col, direction=direction)
|
|
successors.append(('go', forward))
|
|
elif direction == 1:
|
|
if is_valid_move(num_map=num_matrix, target_row=row, target_column=col+1):
|
|
forward = State(row=row, column=col+1, direction=direction)
|
|
successors.append(('go', forward))
|
|
elif direction == 2:
|
|
if is_valid_move(num_map=num_matrix, target_row=row+1, target_column=col):
|
|
forward = State(row=row+1, column=col, direction=direction)
|
|
successors.append(('go', forward))
|
|
elif direction == 3:
|
|
if is_valid_move(num_map=num_matrix, target_row=row, target_column=col-1):
|
|
forward = State(row=row, column=col-1, direction=direction)
|
|
successors.append(('go', forward))
|
|
|
|
return successors
|
|
|
|
|
|
def graphsearch(initial_state: State, mp=num_matrix, goal_list=(6, 1), fringe: List[Node] = None, explored: List[Node] = None):
|
|
if fringe is None:
|
|
fringe = list()
|
|
if explored is None:
|
|
explored = list()
|
|
explored_states = set()
|
|
fringe_states = set()
|
|
|
|
fringe.append(Node(initial_state))
|
|
fringe_states.add((initial_state.row, initial_state.column, initial_state.direction))
|
|
|
|
while True:
|
|
if not any(fringe):
|
|
return []
|
|
|
|
element = fringe.pop(0)
|
|
fringe_states.remove((element.state.row, element.state.column, element.state.direction))
|
|
|
|
if is_reached(goal_list, element.state):
|
|
actions_sequence = [element.action]
|
|
parent = element.parent
|
|
|
|
while parent is not None:
|
|
if parent.action is not None:
|
|
actions_sequence.append(parent.action)
|
|
parent = parent.parent
|
|
|
|
actions_sequence.reverse()
|
|
return actions_sequence
|
|
|
|
explored.append(element)
|
|
explored_states.add((element.state.row, element.state.column, element.state.direction))
|
|
|
|
for successor in get_successor(element.state, num_matrix=mp):
|
|
successor_state = (successor[1].row, successor[1].column, successor[1].direction)
|
|
|
|
if successor_state not in fringe_states and successor_state not in explored_states:
|
|
new_node = Node(state=successor[1],
|
|
parent=element,
|
|
action=successor[0])
|
|
fringe.append(new_node)
|
|
fringe_states.add((new_node.state.row, new_node.state.column, new_node.state.direction))
|
|
|
|
|
|
def is_reached(goal_list, state: State):
|
|
comp = (state.row, state.column)
|
|
if comp == goal_list:
|
|
return True
|
|
return False
|
|
|
|
|
|
if __name__ == "__main__":
|
|
initial_state = State(row=7, column=1, direction=1)
|
|
print(graphsearch(initial_state=initial_state))
|