import os, argparse

def solve_task(lines):
    start = None
    goal = None
    tiles = [[Vertex() for j in range(len(lines[0]))] for i in range(len(lines))]

    for y, line in enumerate(lines):
        for x, char in enumerate(line):
            value = char
            if value == 'S':
                value = 'a'
                start = tiles[y][x]
            elif value == 'E':
                value = 'z'
                goal = tiles[y][x]
            tiles[y][x].value = ord(value)
    
    for y, row in enumerate(tiles):
        for x, vert in enumerate(row):
            if x > 0:
                conditional_add_neighbour(vert, tiles[y][x-1])
            if x < (len(row)-1):
                conditional_add_neighbour(vert, tiles[y][x+1])
            if y > 0:
                conditional_add_neighbour(vert, tiles[y-1][x])
            if y < (len(tiles)-1):
                conditional_add_neighbour(vert, tiles[y+1][x])
    
    distance = BFS(start, goal)
    print(f"The shortest path is {distance}")

def BFS(start, goal):
    nodes_to_search = [start]
    start.distance = 0
    while len(nodes_to_search) > 0:
        current_node = nodes_to_search.pop(0)
        if current_node.visited:
            continue
        current_node.visited = True
        if current_node is goal:
            return current_node.distance
        for n in current_node.neighbours:
            if not n.visited:
                n.distance = current_node.distance + 1
                nodes_to_search.append(n)
    return "No path"


def conditional_add_neighbour(src, dest):
    if dest.value <= (src.value + 1):
        src.add_neighbour(dest)
        

class Vertex:
    def __init__(self, value = None) -> None:
        self.neighbours = []
        self.value = value
        self.visited = False

    def add_neighbour(self, other_vertex):
        #n = Edge(self, other_vertex)
        self.neighbours.append(other_vertex)

class Edge:
    def __init__(self, src, dest) -> None:
        self.src = src
        self.dest = dest
        pass

def read_lines(filename):
    lines = []
    with open(filename) as infile:
        for raw_line in infile:
            line = raw_line.rstrip()
            lines.append(line)
    return lines

def parse_arguments():
    parser = argparse.ArgumentParser(description="Script that solves the case",epilog="Have a nice day!")
    parser.add_argument('filename', nargs='?', default="example.txt", help='Input file')
    args = parser.parse_args()
    return args

def main():
    args = parse_arguments()
    lines = read_lines(args.filename)
    solve_task(lines)

if __name__ == "__main__":
    main()