fork download
copy 
  1. import scala.collection.immutable.Queue
  2.  
  3. object MazeSolver {
  4.  
  5.     type Grid[A] = Array[Array[A]]
  6.  
  7.     type Indices = (Int, Int)
  8.  
  9.     type Opt2[A] = Option[Option[A]]
  10.  
  11.     type IndexGrid = Grid[Opt2[Indices]]
  12.  
  13.     type Predicate[A] = A => Boolean
  14.  
  15.     def validAndTraversable[A](isTraversable: Predicate[A], grid: Grid[A], xy: Indices): Boolean = {
  16.         val (x, y) = xy
  17.         val xbound = grid.length
  18.         val ybound = grid(0).length
  19.         val withinBounds = (x >= 0) && (x < xbound) && (y >= 0) && (y < ybound)
  20.         withinBounds && isTraversable(grid(x)(y))
  21.     }
  22.  
  23.     def getPath(grid: IndexGrid, end: Indices) = {
  24.  
  25.         def pathAccumulator(grid: IndexGrid, path: List[Indices], xy: Indices): List[Indices] = {
  26.             val (x, y) = xy
  27.             grid(x)(y) match {
  28.                 case Some(Some(prevXY)) => pathAccumulator(grid, xy :: path, prevXY)
  29.                 case Some(None) => xy :: path
  30.                 case None => Nil
  31.             }
  32.         }
  33.  
  34.         pathAccumulator(grid, Nil, end)
  35.     }
  36.  
  37.     def mazeSolverLoop[A](isFinish: (Indices, A) => Boolean,
  38.                           isTraversable: Predicate[A],
  39.                           grid: Grid[A],
  40.                           queue: Queue[Indices],
  41.                           indexGrid: IndexGrid): List[Indices] = if (queue.isEmpty) Nil else {
  42.         val (currentXY, rest) = queue.dequeue
  43.         val (x, y) = currentXY
  44.         if (isFinish(currentXY, grid(x)(y))) {
  45.             getPath(indexGrid, currentXY) // not really
  46.         }
  47.         else {
  48.             val neighbors = List((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1))
  49.             val unvisited = neighbors.filter { case ij @ (i, j) => validAndTraversable(isTraversable, grid, ij) && indexGrid(i)(j).isEmpty }
  50.             for ( (i, j) <- unvisited ) {
  51.                 indexGrid(i)(j) = Some(Some(currentXY))
  52.             }
  53.             val updatedQueue = rest ++ unvisited
  54.             mazeSolverLoop(isFinish, isTraversable, grid, updatedQueue, indexGrid)
  55.         }
  56.     }
  57.  
  58.     def findUnknownFinish[A](start: Indices, 
  59.                              isFinish: (Indices, A) => Boolean, 
  60.                              isTraversable: Predicate[A], 
  61.                              grid: Grid[A]) = 
  62.     if (validAndTraversable(isTraversable, grid, start)) {
  63.         val (x, y) = start
  64.         val indexGrid = Array.fill[Opt2[Indices]](grid.length, grid(0).length)(None)
  65.         indexGrid(x)(y) = Some(None)
  66.         mazeSolverLoop(isFinish, isTraversable, grid, Queue(start), indexGrid)
  67.     }
  68.     else {
  69.         Nil
  70.     }
  71.  
  72.     def findKnownFinish[A](start: Indices, 
  73.                            finish: Indices, 
  74.                            isTraversable: Predicate[A], 
  75.                            grid: Grid[A]) = findUnknownFinish(start, (xy: Indices, a: A) => (xy == finish), isTraversable, grid)
  76.  
  77.  
  78.     def escapeMaze[A](start: Indices, isTraversable: Predicate[A], grid: Grid[A]) = {
  79.         val xbound = grid.length
  80.         val ybound = grid(0).length
  81.         val boundaryPred = (xy: Indices, a: A) => {
  82.             val (x, y) = xy
  83.             ((x == 0) || (x == xbound - 1) || (y == 0) || (y == ybound - 1))
  84.         }
  85.         findUnknownFinish(start, boundaryPred, isTraversable, grid)
  86.     }
  87.  
  88.     def escapeMazeV2[A](start: Indices, isTraversable: Predicate[A], grid: Grid[A]) = {
  89.         val xbound = grid.length
  90.         val ybound = grid(0).length
  91.         val boundaryPred = (xy: Indices, a: A) => {
  92.             val (x, y) = xy
  93.             ((x == 0) || (x == xbound - 1) || (y == 0) || (y == ybound - 1)) && (xy != start)
  94.         }
  95.         findUnknownFinish(start, boundaryPred, isTraversable, grid)
  96.     }
  97.  
  98.     def printMazeGrid[A](grid: Grid[A]) = {
  99.         grid.foreach { row => println(row.mkString(" ")) };
  100.         println();
  101.     }
  102.  
  103.     def printPath(path: List[Indices]) {
  104.         path.foreach(println(_));
  105.         println();
  106.     }
  107. }
  108.  
  109. object Main extends App {
  110. 	val maze_01 = Array(Array(1,1,1,1,1,1,0),
  111.                         Array(0,0,0,0,0,0,0),
  112.                         Array(1,1,1,1,1,1,0),
  113.                         Array(0,0,0,0,0,0,0),
  114.                         Array(0,1,1,1,1,1,1),
  115.                         Array(0,0,0,0,0,0,0),
  116.                         Array(1,1,1,0,1,1,1),
  117.                         Array(0,0,0,0,0,0,0),
  118.                         Array(0,1,1,1,1,1,0))
  119.  
  120.     val maze_02 = Array("xxxxxxxxxxxxxxxxxxxxx",
  121.                         "x            x      x",
  122.                         "xx xxxx xxxxxx xxx  x",
  123.                         "x   x   x      x xx x",
  124.                         "x xxxxx xxxxxxxx  x x",
  125.                         "x x              xx x",
  126.                         "xxxxxx  xxxxx xxxx  x",
  127.                         "x    xxxx   x x     x",
  128.                         "x xx  x x x x x x xxx",
  129.                         "x  xx x   x x x x   x",
  130.                         "xx  x x x xxx xxx xxx",
  131.                         "x  xx   x           x",
  132.                         "xxxx  x xxxxxx xxxx x",
  133.                         "x    xx x x    x    x",
  134.                         "xxxxxx  x x xxxxx xxx",
  135.                         "x      xx x     x x x",
  136.                         "xxx x xx  xxx xxx x x",
  137.                         "x x x       x   x   x",
  138.                         "x x xxxxxx xxxx xxx x",
  139.                         "x      x           ox",
  140.                         "x xxxxxxxxxxxxxxxxxxx").map(_.toArray)
  141.  
  142.     val maze_03 = Array("###########",
  143.                         "#         #",
  144.                         "# ##### # #",
  145.                         "    #   # #",
  146.                         "### # ### #",
  147.                         "#     #   #",
  148.                         "# # ### ###",
  149.                         "# #   #    ",
  150.                         "# ### # # #",
  151.                         "#     #   #",
  152.                         "###########").map(_.toArray)
  153.  
  154.     val maze1_s1 = MazeSolver.findKnownFinish(start = (1,0), 
  155.                                                   finish = (8,6),
  156.                                                   isTraversable = (x: Int) => (x == 0),
  157.                                                   grid = maze_01)
  158.  
  159.         val maze2_s1 = MazeSolver.findUnknownFinish(start = (1,1),
  160.                                                     isFinish = (xy: (Int, Int), c: Char) => (c == 'o'),
  161.                                                     isTraversable = (c: Char) => (c != 'x'),
  162.                                                     grid = maze_02)
  163.  
  164.         val maze2_s2 = MazeSolver.escapeMaze(start = (1,1),
  165.                                              isTraversable = (c: Char) => (c != 'x'),
  166.                                              grid = maze_02)
  167.  
  168.         val maze3_s1 = MazeSolver.escapeMazeV2(start = (3,0),
  169.                                                isTraversable = (c: Char) => (c != '#'),
  170.                                                grid = maze_03)
  171.  
  172.         val maze3_s2 = MazeSolver.escapeMazeV2(start = (7,10),
  173.                                                isTraversable = (c: Char) => (c != '#'),
  174.                                                grid = maze_03)
  175.  
  176.         MazeSolver.printMazeGrid(maze_01)
  177.         MazeSolver.printPath(maze1_s1)
  178.         MazeSolver.printMazeGrid(maze_02)
  179.         MazeSolver.printPath(maze2_s1)
  180.         MazeSolver.printPath(maze2_s2)
  181.         MazeSolver.printMazeGrid(maze_03)
  182.         MazeSolver.printPath(maze3_s1)
  183.         MazeSolver.printPath(maze3_s2)
  184. }
Success #stdin #stdout 0.46s 322176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 1 1 1 1 0
0 0 0 0 0 0 0
1 1 1 1 1 1 0
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0

(1,0)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(2,6)
(3,6)
(3,5)
(3,4)
(3,3)
(3,2)
(3,1)
(3,0)
(4,0)
(5,0)
(5,1)
(5,2)
(5,3)
(6,3)
(7,3)
(7,4)
(7,5)
(7,6)
(8,6)

x x x x x x x x x x x x x x x x x x x x x
x                         x             x
x x   x x x x   x x x x x x   x x x     x
x       x       x             x   x x   x
x   x x x x x   x x x x x x x x     x   x
x   x                             x x   x
x x x x x x     x x x x x   x x x x     x
x         x x x x       x   x           x
x   x x     x   x   x   x   x   x   x x x
x     x x   x       x   x   x   x       x
x x     x   x   x   x x x   x x x   x x x
x     x x       x                       x
x x x x     x   x x x x x x   x x x x   x
x         x x   x   x         x         x
x x x x x x     x   x   x x x x x   x x x
x             x x   x           x   x   x
x x x   x   x x     x x x   x x x   x   x
x   x   x               x       x       x
x   x   x x x x x x   x x x x   x x x   x
x             x                       o x
x   x x x x x x x x x x x x x x x x x x x

(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(2,7)
(3,7)
(4,7)
(5,7)
(5,8)
(5,9)
(5,10)
(5,11)
(5,12)
(5,13)
(6,13)
(7,13)
(8,13)
(9,13)
(10,13)
(11,13)
(11,14)
(11,15)
(11,16)
(11,17)
(11,18)
(11,19)
(12,19)
(13,19)
(13,18)
(13,17)
(14,17)
(15,17)
(16,17)
(17,17)
(17,18)
(17,19)
(18,19)
(19,19)

(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(2,7)
(3,7)
(4,7)
(5,7)
(5,8)
(5,9)
(5,10)
(5,11)
(5,12)
(5,13)
(6,13)
(7,13)
(8,13)
(9,13)
(10,13)
(11,13)
(11,12)
(11,11)
(11,10)
(11,9)
(10,9)
(9,9)
(9,8)
(9,7)
(10,7)
(11,7)
(12,7)
(13,7)
(14,7)
(14,6)
(15,6)
(15,5)
(15,4)
(15,3)
(16,3)
(17,3)
(18,3)
(19,3)
(19,2)
(19,1)
(20,1)

# # # # # # # # # # #
#                   #
#   # # # # #   #   #
        #       #   #
# # #   #   # # #   #
#           #       #
#   #   # # #   # # #
#   #       #        
#   # # #   #   #   #
#           #       #
# # # # # # # # # # #

(3,0)
(3,1)
(2,1)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(1,8)
(1,9)
(2,9)
(3,9)
(4,9)
(5,9)
(5,8)
(5,7)
(6,7)
(7,7)
(7,8)
(7,9)
(7,10)

(7,10)
(7,9)
(7,8)
(7,7)
(6,7)
(5,7)
(5,8)
(5,9)
(4,9)
(3,9)
(2,9)
(1,9)
(1,8)
(1,7)
(1,6)
(1,5)
(1,4)
(1,3)
(1,2)
(1,1)
(2,1)
(3,1)
(3,0)
https://ideone.com/KIwrpc
language:
Scala (scala 2.12.8)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!