def __init__(self):
    """ Initializes the data structure """
    self.target = None
    self.start = None
    self.end = None
    self.arriving_direction = Direction.NORTH
    # edges are tuples like (start, end, weight); start and end are tuples of the coordinates and the direction
    self.edges = set()  # if changed, adapt add_path for blocked paths

def add_path(self, start: Tuple[Tuple[int, int], Direction], target: Tuple[Tuple[int, int], Direction],
             weight: int):
    """
     Adds a bidirectional path defined between the start and end coordinates to the map and assigns the weight to it

    Example:
        add_path(((0, 3), Direction.NORTH), ((0, 3), Direction.WEST), 1)
    :param start: 2-Tuple
    :param target:  2-Tuple
    :param weight: Integer
    :return: void
    """

    # OWN CODE HEREAFTER
    self.edges.add((start, target, weight))
    self.edges.add((target, start, weight))  # bidirectional graph
    # if edges gets changed to not being a set, blocked paths should not get inserted twice!

def get_paths(self) -> Dict[Tuple[int, int], Dict[Direction, Tuple[Tuple[int, int], Direction, Weight]]]:
    """
    Returns all paths

    Example:
        {
            (0, 3): {
                Direction.NORTH: ((0, 3), Direction.WEST, 1),
                Direction.EAST: ((1, 3), Direction.WEST, 2)
            },
            (1, 3): {
                Direction.WEST: ((0, 3), Direction.EAST, 2),
                ...
            },
            ...
        }
    :return: Dict
    """

    # OWN CODE HEREAFTER
    all_paths = {}
    for start, target, weight in self.edges:
        # unpack start
        coordinates, direction = start
        # if not yet existent, create new dictionary
        if coordinates not in all_paths:
            all_paths[coordinates] = {}
        # add target to dictionary
        all_paths[coordinates][direction] = (target[0], target[1], weight)
    return all_paths

def shortest_path(self, start: Tuple[int, int], target: Tuple[int, int]) ->
        Optional[List[Tuple[Tuple[int, int], Direction]]]:
    """
    Returns a shortest path between two nodes

    Examples:
        shortest_path((0,0), (2,2)) returns: [((0, 0), Direction.EAST), ((1, 0), Direction.NORTH)]
        shortest_path((0,0), (1,2)) returns: None
    :param start: 2-Tuple
    :param target: 2-Tuple
    :return: 2-Tuple[List, Direction]
    """

    # OWN CODE HEREAFTER ==> DIJKSTRA
    discovered_vertices = {}
    finished_vertices = {}
    # format of tuples: (previous vertex, direction out of previous vertex, weight from start)
    # keys are coordinate-tuples
    discovered_vertices[start] = (None, None, 0)

    while len(discovered_vertices) > 0:
        # figure out discovered vertex with minimum weight as working_vertex
        min_weight = math.inf
        working_vertex = None
        for coordinates, edge in discovered_vertices.items():
            vertex_weight = edge[2]
            if vertex_weight < min_weight:
                working_vertex = (coordinates, edge)
                min_weight = vertex_weight

        # move working_vertex from discovered to finished
        finished_vertices[working_vertex[0]] = working_vertex[1]
        discovered_vertices.pop(working_vertex[0])

        # if target is finished, unfinished vertices don't matter
        if working_vertex[0] == target:
            break

        # update discovered vertices
        for direction, end in self.get_paths()[working_vertex[0]].items():
            current_coordinate = working_vertex[0]
            end_coordinates = end[0]
            current_weight = working_vertex[1][2]
            path_weight = end[2]

            # blocked path
            if path_weight <= 0:
                continue

            if end_coordinates in finished_vertices:
                pass
            elif end_coordinates not in discovered_vertices:
                discovered_vertices[end_coordinates] = (current_coordinate, direction,
                                                        current_weight + path_weight)
            else:
                if current_weight + path_weight < discovered_vertices[end_coordinates][2]:
                    discovered_vertices[end_coordinates] = (current_coordinate, direction,
                                                            current_weight + path_weight)

    # construct path
    if target not in finished_vertices:
        return None
    path = [(finished_vertices[target][0], finished_vertices[target][1])]
    while path[0][0] != start:
        current_vertex = path[0][0]
        path.insert(0, (finished_vertices[current_vertex][0], finished_vertices[current_vertex][1]))
    return path

@staticmethod
def direction_from_char(char):
    if char == "N":
        return Direction.NORTH
    elif char == "E":
        return Direction.EAST
    elif char == "S":
        return Direction.SOUTH
    elif char == "W":
        return Direction.WEST
    else:
        print("invalid character for direction")

@staticmethod
def char_from_direction(direction):
    if direction == Direction.NORTH:
        return "N"
    elif direction == Direction.EAST:
        return "E"
    elif direction == Direction.SOUTH:
        return "S"
    elif direction == Direction.WEST:
        return "W"
    else:
        print("invalid direction for character")

def rel_to_abs_direction(self, dir_rel):
    if dir_rel == "front":
        return self.arriving_direction
    elif dir_rel == "left":
        if self.arriving_direction == Direction.NORTH:
            return Direction.WEST
        elif self.arriving_direction == Direction.WEST:
            return Direction.SOUTH
        elif self.arriving_direction == Direction.SOUTH:
            return Direction.EAST
        elif self.arriving_direction == Direction.EAST:
            return Direction.NORTH
    elif dir_rel == "right":
        if self.arriving_direction == Direction.NORTH:
            return Direction.EAST
        elif self.arriving_direction == Direction.WEST:
            return Direction.NORTH
        elif self.arriving_direction == Direction.SOUTH:
            return Direction.WEST
        elif self.arriving_direction == Direction.EAST:
            return Direction.SOUTH
    elif dir_rel == "back":
        if self.arriving_direction == Direction.NORTH:
            return Direction.SOUTH
        elif self.arriving_direction == Direction.WEST:
            return Direction.EAST
        elif self.arriving_direction == Direction.SOUTH:
            return Direction.NORTH
        elif self.arriving_direction == Direction.EAST:
            return Direction.WEST

def get_next_dir_rel(self):
    current_dir = self.arriving_direction
    next_dir = self.start[1]
    if current_dir == Direction.NORTH:
        if next_dir == Direction.NORTH:
            return "front"
        elif next_dir == Direction.WEST:
            return "left"
        elif next_dir == Direction.SOUTH:
            return "back"
        elif next_dir == Direction.EAST:
            return "right"
    elif current_dir == Direction.WEST:
        if next_dir == Direction.NORTH:
            return "right"
        elif next_dir == Direction.WEST:
            return "front"
        elif next_dir == Direction.SOUTH:
            return "left"
        elif next_dir == Direction.EAST:
            return "back"
    elif current_dir == Direction.SOUTH:
        if next_dir == Direction.NORTH:
            return "back"
        elif next_dir == Direction.WEST:
            return "right"
        elif next_dir == Direction.SOUTH:
            return "front"
        elif next_dir == Direction.EAST:
            return "left"
    elif current_dir == Direction.EAST:
        if next_dir == Direction.NORTH:
            return "left"
        elif next_dir == Direction.WEST:
            return "back"
        elif next_dir == Direction.SOUTH:
            return "right"
        elif next_dir == Direction.EAST:
            return "front"