BFS Maze Solver in Scala

Question

I recently got a Scala developer position, so I'd like to get more comfortable with Scala on my own. Here is a maze solver that I wrote (previously in other languages) that I translated to Scala. Any tips or suggestions on coding style is greatly appreciated.

Ideone

import scala.collection.immutable.Queue

object MazeSolver {

    type Grid[A] = Array[Array[A]]

    type Indices = (Int, Int)

    type Opt2[A] = Option[Option[A]]

    type IndexGrid = Grid[Opt2[Indices]]

    type Predicate[A] = A => Boolean

    def validAndTraversable[A](isTraversable: Predicate[A], grid: Grid[A], xy: Indices): Boolean = {
        val (x, y) = xy
        val xbound = grid.length
        val ybound = grid(0).length
        val withinBounds = (x >= 0) && (x < xbound) && (y >= 0) && (y < ybound)
        withinBounds && isTraversable(grid(x)(y))
    }

    def getPath(grid: IndexGrid, end: Indices) = {

        def pathAccumulator(grid: IndexGrid, path: List[Indices], xy: Indices): List[Indices] = {
            val (x, y) = xy
            grid(x)(y) match {
                case Some(Some(prevXY)) => pathAccumulator(grid, xy :: path, prevXY)
                case Some(None) => xy :: path
                case None => Nil
            }
        }

        pathAccumulator(grid, Nil, end)
    }

    def mazeSolverLoop[A](isFinish: (Indices, A) => Boolean,
                          isTraversable: Predicate[A],
                          grid: Grid[A],
                          queue: Queue[Indices],
                          indexGrid: IndexGrid): List[Indices] = if (queue.isEmpty) Nil else {
        val (currentXY, rest) = queue.dequeue
        val (x, y) = currentXY
        if (isFinish(currentXY, grid(x)(y))) {
            getPath(indexGrid, currentXY)
        }
        else {
            val neighbors = List((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1))
            val unvisited = neighbors.filter { case ij @ (i, j) => validAndTraversable(isTraversable, grid, ij) && indexGrid(i)(j).isEmpty }
            for ( (i, j) <- unvisited ) {
                indexGrid(i)(j) = Some(Some(currentXY))
            }
            val updatedQueue = rest ++ unvisited
            mazeSolverLoop(isFinish, isTraversable, grid, updatedQueue, indexGrid)
        }
    }

    def findUnknownFinish[A](start: Indices, 
                             isFinish: (Indices, A) => Boolean, 
                             isTraversable: Predicate[A], 
                             grid: Grid[A]) = 
    if (validAndTraversable(isTraversable, grid, start)) {
        val (x, y) = start
        val indexGrid = Array.fill[Opt2[Indices]](grid.length, grid(0).length)(None)
        indexGrid(x)(y) = Some(None)
        mazeSolverLoop(isFinish, isTraversable, grid, Queue(start), indexGrid)
    }
    else {
        Nil
    }

    def findKnownFinish[A](start: Indices, 
                           finish: Indices, 
                           isTraversable: Predicate[A], 
                           grid: Grid[A]) = findUnknownFinish(start, (xy: Indices, a: A) => (xy == finish), isTraversable, grid)


    def escapeMaze[A](start: Indices, isTraversable: Predicate[A], grid: Grid[A]) = {
        val xbound = grid.length
        val ybound = grid(0).length
        val boundaryPred = (xy: Indices, a: A) => {
            val (x, y) = xy
            ((x == 0) || (x == xbound - 1) || (y == 0) || (y == ybound - 1))
        }
        findUnknownFinish(start, boundaryPred, isTraversable, grid)
    }

    def escapeMazeV2[A](start: Indices, isTraversable: Predicate[A], grid: Grid[A]) = {
        val xbound = grid.length
        val ybound = grid(0).length
        val boundaryPred = (xy: Indices, a: A) => {
            val (x, y) = xy
            ((x == 0) || (x == xbound - 1) || (y == 0) || (y == ybound - 1)) && (xy != start)
        }
        findUnknownFinish(start, boundaryPred, isTraversable, grid)
    }

    def printMazeGrid[A](grid: Grid[A]) = {
        grid.foreach { row => println(row.mkString(" ")) };
        println();
    }

    def printPath(path: List[Indices]) {
        path.foreach(println(_));
        println();
    }
}

object Mazes {

    val maze_01 = Array(Array(1,1,1,1,1,1,0),
                        Array(0,0,0,0,0,0,0),
                        Array(1,1,1,1,1,1,0),
                        Array(0,0,0,0,0,0,0),
                        Array(0,1,1,1,1,1,1),
                        Array(0,0,0,0,0,0,0),
                        Array(1,1,1,0,1,1,1),
                        Array(0,0,0,0,0,0,0),
                        Array(0,1,1,1,1,1,0))

    val maze_02 = Array("xxxxxxxxxxxxxxxxxxxxx",
                        "x            x      x",
                        "xx xxxx xxxxxx xxx  x",
                        "x   x   x      x xx x",
                        "x xxxxx xxxxxxxx  x x",
                        "x x              xx x",
                        "xxxxxx  xxxxx xxxx  x",
                        "x    xxxx   x x     x",
                        "x xx  x x x x x x xxx",
                        "x  xx x   x x x x   x",
                        "xx  x x x xxx xxx xxx",
                        "x  xx   x           x",
                        "xxxx  x xxxxxx xxxx x",
                        "x    xx x x    x    x",
                        "xxxxxx  x x xxxxx xxx",
                        "x      xx x     x x x",
                        "xxx x xx  xxx xxx x x",
                        "x x x       x   x   x",
                        "x x xxxxxx xxxx xxx x",
                        "x      x           ox",
                        "x xxxxxxxxxxxxxxxxxxx").map(_.toArray)

    val maze_03 = Array("###########",
                        "#         #",
                        "# ##### # #",
                        "    #   # #",
                        "### # ### #",
                        "#     #   #",
                        "# # ### ###",
                        "# #   #    ",
                        "# ### # # #",
                        "#     #   #",
                        "###########").map(_.toArray)

    def main(args: Array[String]) {
        val maze1_s1 = MazeSolver.findKnownFinish(start = (1,0), 
                                                  finish = (8,6),
                                                  isTraversable = (x: Int) => (x == 0),
                                                  grid = maze_01)

        val maze2_s1 = MazeSolver.findUnknownFinish(start = (1,1),
                                                    isFinish = (xy: (Int, Int), c: Char) => (c == 'o'),
                                                    isTraversable = (c: Char) => (c != 'x'),
                                                    grid = maze_02)

        val maze2_s2 = MazeSolver.escapeMaze(start = (1,1),
                                             isTraversable = (c: Char) => (c != 'x'),
                                             grid = maze_02)

        val maze3_s1 = MazeSolver.escapeMazeV2(start = (3,0),
                                               isTraversable = (c: Char) => (c != '#'),
                                               grid = maze_03)

        val maze3_s2 = MazeSolver.escapeMazeV2(start = (7,10),
                                               isTraversable = (c: Char) => (c != '#'),
                                               grid = maze_03)

        MazeSolver.printMazeGrid(maze_01)
        MazeSolver.printPath(maze1_s1)
        MazeSolver.printMazeGrid(maze_02)
        MazeSolver.printPath(maze2_s1)
        MazeSolver.printPath(maze2_s2)
        MazeSolver.printMazeGrid(maze_03)
        MazeSolver.printPath(maze3_s1)
        MazeSolver.printPath(maze3_s2)
    }
}

Answer 1

Scala Idioms

I am not a member of the Secretariat for the Purity of Scala Programs. I am pragmatic. In my opinion what makes a good program is vastly more important than whether something is good or bad Scala. Scala is designed to meet programmers where they are. It has mutuation. It has objects. It has pattern matching and list comprehensions and higher level functions. It is delibrately multi-paradigm and debates about the merit of functional style versus procedural style are orthogonal to it. Scala the language isn't Haskell the language.

Code Smell

Lines 7 - 11 are a concern:

  type Indices = (Int, Int)

  type Opt2[A] = Option[Option[A]]

  type IndexGrid = Grid[Opt2[Indices]]

Opt2 is always Some[something] because something is either Some[somethingElse] or None. An Opt2 can't be None because Option[A] is always an Option. More importantly, none of this makes it any easier to reason about how the code represents or solves mazes at the high level of abstraction or about how the code works at the level of Options and tuples of Ints at the lower level.

Readability

Structural decisions and the choice of abstractions make the code difficult to read. Writing zero comments should not be considered a feature.

Modularity

The absence of any modularity makes the code difficult to follow. Simply breaking out the tests would significantly improve readability. Scala has a common idiom for modularizing code: SBT. There are practical alternatives available from other JVM language communities.

Leaking Abstractions

A maze declartion should be purely declarative. It should define the geometry of the maze in terms of walls, levels, chutes, ladders, dragons, etc.

A maze object should have an API that answers two questions: 1. Where am I? 2. What do I see?

It should initialize with a maze definition and a goal location.

A maze solver should intialize with a start location and a maze object. It should reach a solution state based upon querying the API of the maze object. It should not have knowledge of the maze geometry, the goal location, or the solvability of the maze given the start location. It's supposed to figure all that out. This means a maze solver should build an internal representation of a maze based on what it finds.

It has to do so anyway to maintain its search space, so even though it sounds like more work, it isn't. Decoupling the solver from the maze declaration and an instantiation via a maze object makes it more general - e.g. it could operate over the wire to a RESTful endpoint.

Specification

There needs to be a specification for maze declarations. The important issues are: 1. How many degrees of freedom exist for movement? A 2d rectangular grid might allow four or 8 depending on whether moving diagonally constitues one move or two. A 2d hexagonal grid would allow 6 directions of movement. 3d grids allow additional options. 2. What is the language used for maze declarations?

Names

Variables and constants should be named to reflect the business logic of mazes. The model should be tied to the language of mazes:

• xbound should be east
• ybound should be north
• south should be zero
• west should be zero

Making these assumptions explicit allows those reading the code to reason about it more clearly. It makes it easier to extend the code to three or more dimensions [there's no reason a computer can't solve an n-dimensional maze] or to handle hexagonal grids in ways that make sense.

Answer 2

val unvisited = neighbors.filter { case ij @ (i, j) => validAndTraversable(isTraversable, grid, ij) && indexGrid(i)(j).isEmpty }
            for ( (i, j) <- unvisited ) {
                indexGrid(i)(j) = Some(Some(currentXY))
            }

I would prefer a chained map operation following the filter. That would be more of a functional, Scala design.