#!/usr/bin/env python3

# TP1 info601
# NOM : Alan Turing
# groupe L3-info-00101101


from typing import List, Tuple, Dict, Any, TextIO
import re
import sys


import random
from getopt import gnu_getopt as getopt, GetoptError


Maze = List[List[str]]


def find_path_fixed(M: Maze) -> List[Tuple[int, int]]:
    """cherche une solution de durée minimale pour sortir du labyrinthe `M`
    `M` est un tableau à 2 dimension, et `M[i][j]` donne le j-ème caractère de
    la i-ème ligne.
    Par exemple, pour
        #@#####
        #...x.#
        #.....#
        #####$#
    on a `M[0][3]` donne le caractère `x`.
    ATTENTION : l'entrée et la sortie ne sont pas dans le tableau !

    La fonction doit renvoyer un tableau avec les positions du personnage aux temps 0, 1, ..., t
    """
    ...
    return []


def find_path(M: Maze) -> List[Tuple[int, int]]:
    """cherche une solution de durée minimale pour sortir du labyrinthe `M`
    `M` est un tableau à 2 dimension, et `M[i][j]` donne le j-ème caractère de
    la i-ème ligne.
    Par exemple, pour
        #@#####
        #...x.#
        #.....#
        #####$#
    on a `M[0][3]` donne le caractère `x`.
    ATTENTION : l'entrée et la sortie ne sont pas dans le tableau !

    La fonction doit renvoyer un tableau avec les positions du personnage aux temps 0, 1, ..., t
    """
    ...
    return []


def show_path(M: Maze, C: List[Tuple[int, int]]) -> None:
    """affiche toutes les étapes de la solution `C` pour le labyrinthe `M`"""
    """Attention, la version fournie affiche la solution, sans mettre le labyrinthe à jours."""
    for i in range(len(C)):
        print(f"t = {i}")
        print_maze(M, pos=C[i], strict=False)
        print()


def main_test(*args: str) -> int:
    """fonction de test appelée depuis la ligne de commande avec l'option -T / --test
    `args[0]`, `args[1]`, etc. contiennent les chaines données sur la ligne de
    commande.
    Par exemple,
        $ python3 obstacle-ALAN.py -T pomme poire
    appellera cette fonction avec `args=["pomme", "poire"]`.
    """
    # test de la fonction print_maze: on récupère un labyrinthe dans le
    # fichier args[0], et les coordonnées d'une case dans args[1] et args[2]
    M = read_maze(args[0])
    i = int(args[1])
    j = int(args[2])
    print_maze(M, pos=(i, j), strict=True)
    return 0


#########################################
# NE MODIFIEZ PAS LA SUITE DU PROGRAMME #
#########################################


def random_maze(width: int, height: int, obstacle_probability: float = 0.8,
                obstacles: str = "<>v^x") -> None:
    M = []
    for _ in range(height):
        L = []
        for _ in range(width):
            if random.uniform(0, 1) > obstacle_probability:
                L.append('.')
            else:
                L.append(random.choice(obstacles))
        M.append(L)
    print_maze(M)


def error(*args: Any, **kwargs: Any) -> None:
    kwargs["file"] = sys.stderr
    print(*args, **kwargs)


def read_maze(filename: str) -> Maze:
    """read the maze from given file into a 2 dimensional array M
    M[i][j] gives the j-th character from the i-th line in the maze.
    Walls '#' are stripped, so that only the inner cells are in M.
    """

    if filename != '-':
        f: TextIO = open(filename)
    else:
        f = sys.stdin

    i = 1
    line = f.readline()
    if not re.match("^#[ @]#*$", line):
        error(f"Line {i} from {filename} is invalid: '{line}'.")
        sys.exit(1)

    width = len(line) - 2

    M = []
    for line in f:
        i += 1

        # check for last line of maze
        if re.match("^#*[S $]#$", line):
            if len(line) != width + 2:
                error(f"Line {i} from {filename} is invalid: '{line}'.")
                error(f"Expected {width+2} characters, got {len(line)}.")
                sys.exit(1)
            break

        # check validity of the (inner) line
        if not re.match("^#[.><v^x]*#$", line):
            error(f"Line {i} from {filename} is invalid: '{line}'.")
            sys.exit(1)

        if len(line) != width + 2:
            error(f"Line {i} from {filename} is invalid: '{line}'.")
            error(f"Expected {width+2} characters, got {len(line)}.")
            sys.exit(1)

        # add the line to the array, stripping away the first / last
        # characters (they are the left / right walls '#')
        M.append(list(line[1:-2]))

    else:
        # if we reach this, it means EOF has been reached without finding the
        # last line of the maze.
        error("The maze is unfinished!")
        sys.exit(1)

    return M


def print_maze(M: Maze, pos: None | Tuple[int, int] | str = None, strict: bool = False) -> None:
    """print the maze in ASCII, possibly adding a '@' at position `pos`
    The position must be of the form
      - (x, y) for an inner cell
      - (0,-1) or '@' for the entrance
      - (WIDTH-1, HEIGHT) or '$' for the exit
    If `pos` is on an obstacle, a message is printed on the corresponding
    line and the `@` is replaced by a `!`.
    If `strict` is True when `pos` is on an obstacle, the function prints an
    error message and aborts the program.
    """
    height = len(M)
    width = len(M[0])
    if pos == (0, -1) or pos == '@':
        print("#@" + '#'*width)
    else:
        print("# " + '#'*width)
    for i, L in enumerate(M):
        print('#', end="")
        msg = ""
        for j, c in enumerate(L):
            if (j, i) == pos:
                if c == '.':
                    print('@', end="")
                else:
                    print('!', end="")
                    msg = "    PROBLEM!!!"
            else:
                print(c, end="")
        print('#' + msg)
        if strict and msg:
            error("Invalid position!")
            sys.exit(2)
    if pos == (width-1, height) or pos == '$':
        print('#'*width + "@#")
    else:
        print('#'*width + "$#")


def help(exe: str) -> None:
    print(f"""usage: {exe} [OPTIONS] ARGUMENTS
    where the options are
        -h  /  --help           display this message
        -F  /  --fixed          assume the maze contains only fixed obstacles
        -S  /  --show-solution  show the full solution if found
        -T  /  --test           run the test function instead of the main function
        --random-maze           generate a random maze to STDOUT

    In standard mode (default), ARGS should be a single filename.
    In random mode (--random-maze), ARGS should contain WIDTH and HEIGHT
    arguments, and an optional OBSTACLES_PROBA. (Note: there is no guarantee that the maze is
    solvable.)
    In test mode (-T / --test), ARGS are passed to the main_test function.
    """)


def main(argv: List[str]) -> None:

    if len(argv) == 1:
        help(argv[0])
        exit(2)

    short_options = "ThRSFj"
    long_options = ["test", "help", "random-maze", "show-solution", "fixed"]

    try:
        opts, args = getopt(argv[1:], short_options, long_options)
    except GetoptError as err:
        error(err)
        help(argv[0])
        exit(2)

    show_sol = False
    fixed = False
    random = False
    for o, a in opts:
        if o in ["-h", "--help"]:
            help(argv[0])
            exit(0)
        elif o in ["-S", "--show-solution"]:
            show_sol = True
        elif o in ["-F", "--fixed"]:
            fixed = True
        elif o in ["-T", "--test"]:
            sys.exit(main_test(*args))
        elif o in ["-R", "--random-maze"]:
            random = True

    if random:
        if len(args) not in [2, 3, 4]:
            error(
                f"expected WIDTH HEIGHT [PROBABILITY [OBSTACLES]] arguments, got {len(args)} arguments instead")
            exit(3)
        width = int(args[0])
        height = int(args[1])
        if len(args) == 2:
            obstacle_proba = 0.8
            obstacles = "<>v^x"
        elif len(args) == 3:
            obstacle_proba = float(args[2])
            obstacles = "<>v^x"
        else:
            obstacle_proba = float(args[2])
            obstacles = args[3]
            for c in obstacles:
                if c not in "<>v^x":
                    error(
                        f"OBSTACLES argument can only contain < > v ^ x, got '{c}'")
                    exit(3)
        random_maze(width, height, obstacle_proba, obstacles)

    else:
        if len(args) > 1:
            error(f"expected a single file argument, got {len(args)}")
            help(argv[0])
            exit(3)
        if len(args) == 0:
            filename = "-"      # stdin
        else:
            filename = args[0]
        M = read_maze(filename)

        if fixed:
            C = find_path_fixed(M)
        else:
            C = find_path(M)
        t = len(C) - 1

        if t < 0:
            print("*** NO SOLUTION FOUND!")
            return

        assert t > 0 and C

        if show_sol:
            show_path(M, C)
        else:
            print(f">>> solution found in {t} steps")


if __name__ == "__main__":
    main(sys.argv)

# vim: textwidth=100 foldmethod=indent