object Maze extends App{


  def solveMaze(maze: List[String]): Option[String] = {
    //list of tuple of index that is walkable.
    //(row, col)

    def walkableHelper(maze: List[Char],returnList: List[(Int, Int)], row: Int, col: Int): List[(Int, Int)] = maze match {
      case h::t => {
        if (h.equals('x')) walkableHelper(t, (-1,-1)::returnList, row, col+1)
        else walkableHelper(t, (row, col)::returnList, row, col+1)
      }
      case _ => returnList
    }
    def getWalkable(maze: List[String], returnList: List[(Int, Int)], row: Int): List[(Int,Int)] = maze match {
      case h::t => getWalkable(t, walkableHelper(h.toList, List(), row, 0)++returnList, row+1)
      case _ => returnList
    }

    def getSpecialCharacter(maze: List[String], row: Int, specialChara: String): (Int, Int) = maze match {
      case h::t => {
        val pos = h.indexOf(specialChara)
        if (pos != -1) (row, pos)
        else getSpecialCharacter(t, row+1, specialChara)
      }
    }

    def helperCreateMap(submaze: List[Char], returnList: Map[(Int, Int), Set[(Int,Int)]], row: Int, col: Int, valid: List[(Int, Int)]): Map[(Int,Int), Set[(Int,Int)]] = submaze match {
      case h::t => {
        if (valid.contains((row,col))) {
          helperCreateMap(t, Map((row,col) -> Set((row-1, col), (row+1,col), (row,col+1), (row,col-1)).filter(valid.contains(_))) ++ returnList, row, col+1, valid)
        }
        else {
          helperCreateMap(t, returnList, row, col+1, valid)
        }
      }
      case _ => returnList
    }

    def createMap(maze: List[String], returnList: Map[(Int, Int), Set[(Int, Int)]], valid: List[(Int, Int)], row: Int): Map[(Int, Int), Set[(Int,Int)]] = maze match {
      case h::t => {
       createMap(t, helperCreateMap(h.toList, Map(), row, 0, valid) ++ returnList, valid, row+1)
      }
      case _ => returnList
    }

    def translate(point1: (Int, Int), point2: (Int, Int)): String = {
      val direction = (point1._1-point2._1, point1._2-point2._2)
      direction match {
        case (0, -1) => "r"
        case (0, 1) => "l"
        case (-1, 0) => "d"
        case (1, 0) => "u"
        case _ => ""
      }
    }

    def finder(returnList: List[String], current: (Int, Int), target: (Int, Int), parents: Map[(Int, Int), (Int, Int)], count: Int): Option[String] = {
      if (current.equals(target)) {
        Some(returnList.reverse.mkString)
      }
      else {
        val next = parents.get(current)
        next match {
          case Some(w) => {
            finder( translate(current,w)::returnList, w, target, parents, count+1)
          }
          case None => None
        }
      }
    }

    val walkablePath = getWalkable(maze, List(), 0)
    val start = getSpecialCharacter(maze, 0, "s")
    val end = getSpecialCharacter(maze, 0 , "e")
    val validPath = createMap(maze, Map(), walkablePath, 0)

    val (parent, distance) = GraphBFS.bfs[(Int, Int)](validPath, end)

    finder(List(), start, end, parent, 0)
  }


  val maze = List(
  "xxxxxxxxxxxxxxxxxx",
  "x    x      x   ex",
  "x    x   x  x xxxx",
  "x    x   x  x    x",
  "xs   x   x       x",
  "xxxxxxxxxxxxxxxxxx"
  )

  def time[R](block: => R): R = {
    val t0 = System.currentTimeMillis()
    val result = block    // call-by-name
    val t1 = System.currentTimeMillis()
    println("Elapsed time: " + (t1 - t0) + "ms")
    result
  }

//  println(solveMaze(maze))

  val maze250 = List("x" * 250):::List("xs" + " " * 247 + "x"):::List.fill(246)("x"+" " * 248+"x"):::List("x" + " " * 247 + "ex"):::List("x" * 250)


  time(println(solveMaze(maze250)))
}