A Scala Maze Generator in Functional Style

Question

I'm wondering if there is more I can do to incorporate more idiomatic scala and functional programming principles. I know the maze itself is mutable but i didn't see an easy solution to making it immutable. Also, if there is anything I can do to improve my algorithm, that would be great too. The reason I have the trait is so that I can implement more mazes: Prim's, Kruskal's, ... and get the functionality of the trait.

trait Maze {
  val height: Int
  val length: Int 
  var maz: Array[Array[Int]]

  def maze: Maze 

  override def toString() = {
    val strBuilder = new StringBuilder()
    for (i <- 0 until height) {
      for (j <- 0 until length) {
        strBuilder.append(maz(i)(j))
      }
      strBuilder.append("\n")
    }
    strBuilder.toString()
  }
}

class DepthFirstSearch(val height: Int, val length: Int, var maz: Array[Array[Int]]) extends Maze {

  def this(height: Int, length: Int) {
    this(height, length, Array.ofDim[Int](height, length))
  }

  override def maze = {
    maz(0)(0) = 1
    val stack = List[(Int, Int)]()
    mazify((0, 0) :: stack, (0, 0))
  }

  private def mazify(stack: List[(Int, Int)], currentCell: (Int, Int)): DepthFirstSearch = {
    if (stack.nonEmpty) {
      val unvisitedNeighbor = getRandomUnvisitedNeighbor(maz, currentCell)
      if (unvisitedNeighbor._1) {
        val newCurrentCell = unvisitedNeighbor._2
        maz(newCurrentCell._1)(newCurrentCell._2) = 1
        mazify(currentCell :: stack, newCurrentCell)
      } else if (stack.nonEmpty) {
        val newCurrentCell = stack.head
        mazify(stack.tail, newCurrentCell)
      }
    }
    new DepthFirstSearch(height, length, maz)
  }

  private def neighbors(cell: (Int, Int)) = {
    List((cell._1 - 1, cell._2), (cell._1 + 1, cell._2), (cell._1, cell._2 + 1), (cell._1, cell._2 - 1))
  }

  private def insideMaze(cell: (Int, Int)) = {
    cell._1 >= 0 && cell._1 < height && cell._2 >= 0 && cell._2 < length
  }

  private def notOriginalCell(cell: (Int, Int), originalCell: (Int, Int)) = {
    cell._1 != originalCell._1 && cell._2 != originalCell._2
  }

  private def cellVisited(cell: (Int, Int)) = {
    maz(cell._1)(cell._2) == DepthFirstSearch.Visited
  }

  private def hasValidNeighbors(cell: (Int, Int), originalCell: (Int, Int)) = {
    val neighboringCells = neighbors(cell)
    val filteredNeighbors = neighboringCells.filter(c => insideMaze(c) && cellVisited(c) && notOriginalCell(c, originalCell))
    val isValidCell = filteredNeighbors.isEmpty
    isValidCell
  }

  private def getUnvisitedNeighbors(maze: Array[Array[Int]], cell: (Int, Int)) = {
    val neighboringCells = neighbors(cell)
    val filteredNeighbors = neighboringCells.filter(c => c._1 >= 0 && c._1 < height && c._2 >= 0 && c._2 < length && maze(c._1)(c._2) != 1 && hasValidNeighbors(c, cell))
    filteredNeighbors
  }

  private def getRandomUnvisitedNeighbor(maze: Array[Array[Int]], cell: (Int, Int)): (Boolean, (Int, Int)) = {
    val neighbors = getUnvisitedNeighbors(maze, cell)
    if (neighbors.length > 0)
      (true, neighbors(Random.nextInt(neighbors.size)))
    else
      (false, (-1, -1))
  }
}

object DepthFirstSearch { 
  private val Visited = 1

  def apply(height: Int, length: Int) = new DepthFirstSearch(height, length)
}

Answer 1

Prefer Classes to Multiple Tuples

There are lots of usages of cell: (Int, Int), with multiple occurrences of cell._1 and cell._2. Tuples are nice and suitable for various situations, but when there are too many of them, it reduces readability and increases risks of bugs. And you need to remember that _1 is x and _2 is y. Or vice versa. Or both.

So a simple way to improve it is just create an ad-hoc class

private class Cell(val x: Int, val y: Int)

It might also be a case class, if necessary.

Use Options

The method signature

private def getRandomUnvisitedNeighbor(maze: Array[Array[Int]], cell: (Int, Int)): (Boolean, (Int, Int))

is suspicious.

Not only it returns a tuple containing another tuple, but also it looks like the purpose of the Boolean is to show if the return object contains data or marks a missing value, according to mazify: if (unvisitedNeighbor._1) { ... }.

Scala has a dedicated Option[T] type for that:

private def getRandomUnvisitedNeighbor(maze: Array[Array[Int]], cell: (Int, Int)): Option[(Int, Int)] = {
  val neighbors = getUnvisitedNeighbors(maze, cell)
  if (neighbors.length > 0)
    Some(neighbors(Random.nextInt(neighbors.size))))
  else
    None
}

In mazify:

...
getRandomUnvisitedNeighbor(maz, currentCell) match {
  case cell: Some[(Int, Int)] => {
    val newCurrentCell = cell.get
    maz(newCurrentCell._1)(newCurrentCell._2) = 1
    mazify(currentCell :: stack, newCurrentCell)
  }
  case None => {
    val newCurrentCell = stack.head
    mazify(stack.tail, newCurrentCell)
  }
}

Nested fors

The nested for loops in Maze.toString look too imperative-style.

The nesting can be avoided with

for {
  i <- 0 until height
  j <- 0 until length
} {
  strBuilder.append(maz(i)(j))
  if (j == length - 1) strBuilder.append("\n")
}

@jwill's question 2. What is the benefit of the for comprehensions? It looks like the same mutability as a double for loop.

Yes, there is no magic and it is equivalent to double/nested for loops. As I already mentioned, when we have

for (bla-bla-bla_1) {
  for (bla-bla-bla_2) {
    // very clean code here
  }
}

It looks like the good/bad old imperative style. In Scala, foreach and others are functional style replacements for traditional for. The for-comprehension is a sort of shortcut allowing to iterate, filter and map (with yield). For example:

for {
  i <- 0 until height
  if i % 2 == 0
  j <- 0 until length
  if j % 2 == 0
} yield {
  (i, j)
}

Will produce tuples of even values of i and j. It is completely equivalent to

(0 until height).filter(_ % 2 == 0).flatMap(i => {
   (0 until length).filter(_ % 2 == 0).map(j => (i, j))
})

But clearly more readable with for. And the nesting is not visible.

@jwill's question 5. Is the stringbuilder frowned upon?

StringBuilder (either from java.lang or scala.collection) is THE object to use when you need to dynamically construct a String from numerous concatenations.

Readability

getUnvisitedNeighbors contains a terribly complex filtering condition and unnecessary vals. Slightly changed:

private def getUnvisitedNeighbors(maze: Array[Array[Int]], cell: (Int, Int)) = {
  def xInBounds(x: Int) = x >= 0 && x < length
  def yInBounds(y: Int) = y >= 0 && y < height
  neighbors(cell).filter(c => {
    xInBounds(c._2) &&
    yInBounds(c._1) &&
    maze(c._1)(c._2) != 1 &&
    hasValidNeighbors(c, cell)
  })
}

@jwill's question 3. In getUnvisitedNeighbors, why did you write those intermediary calculations as defs rather than vals?

Briefly speaking, because def is a function that is invoked when necessary. val is a constant reference, calculated only once on first invocation. If vals were used here instead of defs, we would not be able to check the condition from within the filter method for each particular cell.

@jwill's question 4. You also didn't mention anything about nesting the private defs inside the main override def maze function. Is that important at all, or a scala idiom to do so?

If you mean that def maze invokes private def mazify, that is absolutely OK and mazify should remain as a private function. Nesting defs within each other should not be overused. I would recommend it only when the nested function is 1) really short; 2) simplifies the readability of the parent one; 3) never needs to be invoked from other functions or itself; 4) does not call other functions of this entity. For def mazify most these conditions are not met.

Mutability

@jwill's question 1. You didn't mention any adjustments for the mutations of the maze. How come? Does it follow under the principle of, "Keep your mutations in small, select locations"?

Indeed, I didn't cover it in the initial answer.

var is not necessary for maz field, it can and should be transformed to val. The reference is never changed throughout the code, but only the contents of the array changes. And I also think that there is no need to expose the array with public access at all.

The def maze in DepthFirstSearch also seems disturbing, because it recalculates the maze on each call and returns a new different instance of DepthFirstSearch. Was it really the intention?

It would be more logical to remove both var maz and def maze from trait Maze and define an accessor for cell values at the trait level:

trait Maze {
  val height: Int
  val length: Int
  def valueAtCell(x: Int, y: Int): Int
}

The implementing class will encapsulate the Array with cells values:

class DepthFirstSearch(override val height: Int,
                       override val length: Int) extends Maze {

  private val maze: Array[Array[Int]] = {
    val maz = Array.ofDim[Int](height, length)
    maz(0)(0) = 1
    mazify(List(), (0, 0))
    maz
  }

  override def valueAtCell(x: Int, y: Int): Int = maze(y)(x)

  private def mazify(stack: List[(Int, Int)], currentCell: (Int, Int)): Unit = {
    val unvisitedNeighbor = getRandomUnvisitedNeighbor(maze, currentCell)
    if (unvisitedNeighbor._1) {
      val newCurrentCell = unvisitedNeighbor._2
      maze(newCurrentCell._1)(newCurrentCell._2) = 1
      mazify(currentCell :: stack, newCurrentCell)
    } else if (stack.nonEmpty) {
      val newCurrentCell = stack.head
      mazify(stack.tail, newCurrentCell)
    }
  }
...
}

Answer 2

Use mkStringto convert a Seqeunce to a String

override def toString() = {
  val strBuilder = new StringBuilder()
  for (i <- 0 until height) {
    for (j <- 0 until length) {
      strBuilder.append(maz(i)(j))
    }
    strBuilder.append("\n")
  }
  strBuilder.toString()
}

Is better written like this:

maz.map(_.mkString).mkString("\n")

There are three overloads for mkString:

Seq(1, 2, 3).mkString                //123
Seq(1, 2, 3).mkString("|")           //1|2|3
Seq(1, 2, 3).mkString("[", "|", "]") //[1|2|3]

Remember that you can always consult the api reference http://www.scala-lang.org/api/2.11.8/index.html#scala.collection.GenTraversableOnce@mkString:String