text: #!/usr/bin/env python
  # -*- coding: utf-8 -*-
  import subprocess
  from functools import reduce
  import sys
  from ast import literal_eval as make_tuple
  
  
  #
  # TRABAJO PRÁCTICO FINAL
  # GENERACION/SOLUCION Laberinto C/Python
  #
  # ALUMNO:
  #       - KASEVICH, IGNACIO
  #
  # GIT: https://github.com/IgnacioKase/prog2-tpfinal
  #
  # 28/11/2019
  #
  
  #####################################
  # LEER README.md
  #####################################
  
  ######### FUNCION PRINCIPAL #########
  
  #
  #  __main__
  # @Parametros: args[String], kargs[list]
  # @Salida: String (por consola no retorna la función)
  #
  # Recibe un archivo, y llama a __main.c para generar
  # un laberinto a partir de este, buscará el camino más
  # corto entre el punto 'I' y el punto 'X'. En caso de
  # no existir dicho camino, generará otro laberinto.
  # Retorna el camino mas corto de 'X' a 'I'
  #
  
  def main():
      graph, iniPos, endPos = generateMaze()
      path = []
      PATH_OUT = sys.argv[4]
      foutput = open(PATH_OUT, "w+", encoding="utf-8")
      solved = False
      while not solved and len(graph) > 0:
          path = BFS(graph, iniPos, endPos)
          solved = len(path) > 0
          if not solved:
              graph, iniPos, endPos = generateMaze()
  
      output = reduce(lambda x, y: x + y,
                      map(lambda v: "(%s, %s), " % (v[1] + 1, v[0] + 1), path)).strip()[:-1]
      foutput.write(output)
  
  
  ######### FUNCIONES AUXILIARES #########
  
  #
  # generateMaze:
  # @Parametros: -
  # @Salida: tuple(graph[List[string]], pair/tuple, pair/tuple)
  #
  # Ejecuta el programa en C que genera el laberinto
  # y luego lee el archivo de salida del mismo. Y
  # arma el grafo correspondiente (lista de strings)
  # e identifica la posicion de inicio y de llegada
  # en el mismo.
  #
  
  def generateMaze():
      PATH_C = sys.argv[1]
      PATH_IN = sys.argv[2]
      PATH_MAZE = sys.argv[3]
  
      response = subprocess.run([PATH_C, PATH_IN, PATH_MAZE])
  
      if response.returncode != 0:
          print("Error al generar el laberinto, mas información en:\tlog.txt")
          return []
  
      iniPos = endPos = (0, 0)
      iniFound = False
      endFound = False
      graph = []
      i = 0
  
      fMaze = open(PATH_MAZE, "r", encoding="utf-8")
  
      line = fMaze.readline()
  
      while line:
          graph.append(line.strip())
          if not iniFound:
              if 'I' in graph[-1]:
                  iniPos = (i, int(graph[-1].index('I') / 2))
                  iniFound = True
          if not endFound:
              if 'X' in graph[-1]:
                  endPos = (i, int(graph[-1].index('X')/2))
                  endFound = True
          i += 1
          line = fMaze.readline()
      fMaze.close()
      return (graph, iniPos, endPos)
  #########################################
  
  
  #
  # getTest:
  # @Parametros: filePath[string]
  # @Salida: List[pair/tuple]
  #
  # Toma la ruta de un archivo y lee los casos de
  # test en ellos siendo el formato:
  # -Primera linea input
  # -Segunda linea output esperado
  # Es decir que el archivo deberá tener una cantidad
  # de lineas pares.
  #
  
  def getTest(filePath):
      file = open(filePath, "r", encoding="utf-8")
      line1 = file.readline()
      line2 = file.readline()
      tests = [(line1.strip(), line2.strip())]
      while line1 and line2:
          line1 = file.readline()
          line2 = file.readline()
          if line1 and line2:
              tests.append((line1.strip(), line2.strip()))
      file.close()
      return tests
  #########################################
  
  
  #
  # checkBoundaries:
  # @Parametros: vertex[pair/tuple], n[int]
  # @Salida: Bool
  #
  # Toma las coordenadas (x,y) de un punto
  # y checkea que esten contenidas entre 0
  # y n, [0,n).
  #
  
  def checkBoundaries(vertex, n):
      return vertex[0] >= 0 and vertex[1] >= 0 and vertex[0] < n and vertex[1] < n
  
  
  def test_checkBoundaries():
      tests = getTest("test/checkBoundaries.txt")
      for test in tests:
          in_test = test[0].split()
          vertex = make_tuple(in_test[0])
          n = int(in_test[1])
          out = test[1] == 'True'
          assert checkBoundaries(vertex, n) == out
  #########################################
  
  
  #
  # posNeighbors:
  # @Parametros: vertex[pair/tuple], n[int]
  # @Salida: list[pair/tuple]
  #
  # Toma las coordenadas (x,y) de un punto
  # en una matriz, que representa un grafo
  # de estilo 'tablero' y devuelve las
  # coordenadas de los vecinos, checkeando
  # unicamente que estos existan en los
  # limites de la matriz.
  #
  
  def getNeighbors(vertex, n):
      posNeighbors = [
          (vertex[0] + 1, vertex[1]),
          (vertex[0] - 1, vertex[1]),
          (vertex[0], vertex[1] + 1),
          (vertex[0], vertex[1] - 1)
      ]
      return list(filter(lambda x: checkBoundaries(x, n), posNeighbors))
  
  
  def test_getNeighbors():
      tests = getTest("test/getNeighbors.txt")
      for test in tests:
          in_test = test[0].split()
          vertex = make_tuple(in_test[0])
          n = int(in_test[1])
          out = test[1][1:-1].split(';')
          neighbors = set([make_tuple(v) for v in out])
          response = set(getNeighbors(vertex, n))
          assert neighbors == response
  #########################################
  
  
  #
  # BFS:
  # @Parametros: graph[list[list[pair/tuple]],
  #              vertex[pair/tuple],
  #              end[pair/tuple]
  # @Salida: list[pair/tuple]
  #
  # Toma un grafo, representando por una lista
  # de listas, de estilo 'tablero', las coordenadas
  # de un vértice, y las coordenadas de un objetivo
  # realiza la busqueda en anchura del grafo con
  # @vertex de inicio/raíz, y guarda el camino
  # mas corto para los demás nodos. Devuelve
  # el camino mas corto de  @vertex a @end.
  #
  
  def BFS(graph, vertex, end):
      n = (len(graph))  # length of the maze (n x n maze)
      visited = [[False] * n for i in range(n)]
      parent = [[(-1, -1)] * n for i in range(n)]
      queue = []
      queue.append(vertex)
      found = False
      visited[vertex[0]][vertex[1]] = True
      while queue and not found:
          v = queue.pop(0)
          neighbors = getNeighbors(v, n)
          for u in neighbors:
              if visited[u[0]][u[1]] == False and graph[u[0]][u[1]] != '1':
                  queue.append(u)
                  found = graph[u[0]][u[1]] == 'X' or found
                  parent[u[0]][u[1]] = v
                  visited[u[0]][u[1]] = True
  
      v = parent[end[0]][end[1]]
      output = []
      while v != (-1, -1):
          output.append(v)
          v = parent[v[0]][v[1]]
      output.reverse()
      if len(output) > 0:
          output.append(end)
      return output
  
  
  def test_BFS():
      tests = getTest("test/BFS.txt")
      for test in tests:
          in_test = test[0].split()
          graph = in_test[0][1:-1].split(';')
          iniPos = make_tuple(in_test[1])
          endPos = make_tuple(in_test[2])
          out = []
          if test[1] != "[]":
              out = test[1][1:-1].split(';')
          path = []
          path = [make_tuple(v) for v in out]
  
          assert BFS(graph, iniPos, endPos) == path
  #########################################
  
  
  if __name__ == "__main__":
      main()
  