# How idiomatic is this Scala 36 Cube Solver?

I've written a short program to find solutions to the 36 Cube puzzle.

I'm trying to break away from my normal Java / imperative style, and would like some feedback on how I'm doing.

Puzzle.scala

package cube36

/**
* An immutable class representing the state of a 36 Cube puzzle
*/
case class CubePuzzle(val board: Board, val availablePieces: List[Piece]) {

/**
* Add a piece to this puzzle, to create new instance of the puzzle
* @param rowNum row to add piece to
* @param colNum column to add piece to
* @param piece piece to add
* @param checkSuitable check if the position will accept this piece (default true if omitted)
* @return a new puzzle instance, with the specified piece added
*/
def addPiece(rowNum: Int, colNum: Int, piece: Piece, checkSuitable: Boolean = true): CubePuzzle = {
val newBoard = board.addPiece(rowNum, colNum, piece,checkSuitable)
CubePuzzle(newBoard, availablePieces.filterNot(_ == piece))
}

/**
* Find solutions to the puzzle which satisfy the rules
* @param solutionsSoFar
* @return a list of all valid solutions
*/
def solve(solutionsSoFar: List[Board]=List[Board]()): List[Board] = {
if (this.availablePieces.size == 0) this.board :: solutionsSoFar
else {
val nextPiece = availablePieces.head
val availableSpots = board.spaces.filter(space => board.suitable(space, nextPiece))
val sols = for (spot <- availableSpots) yield addPiece(spot._1, spot._2, nextPiece,false).solve(solutionsSoFar)
sols.flatten.toList
}
}

}

object CubePuzzle {
// Have to put two pieces in 'special' positions, where they wouldn't be expected to fit.
// No solution otherwise.
private val startingBoard = Board().addPiece(1, 2, Piece(Yellow, 5),false).addPiece(3, 2, Piece(Orange, 6),false)
private val availablePieces = (List[Piece]() ++
getPieces(Yellow, 6) ++
getPieces(Red, 6) ++
getPieces(Purple, 6) ++
getPieces(Blue, 6) ++
getPieces(Green, 6) ++
getPieces(Orange, 6)).
filterNot(_ == Piece(Yellow, 5)).
filterNot(_ == Piece(Orange, 6))

private def getPieces(colour: Colour, maxSize: Int): Set[Piece] = (for (x <- 1 to 6) yield Piece(colour, x)).toSet

def apply() = new CubePuzzle(startingBoard, availablePieces)

}

sealed trait Colour;
case object Red extends Colour;
case object Purple extends Colour;
case object Blue extends Colour;
case object Green extends Colour;
case object Yellow extends Colour;
case object Orange extends Colour;

case class Piece(val colour: Colour, val size: Int) {
require(size <= 6 && size >= 1,"Piece size out of range")

override def toString: String = colour.toString().head.toString + size.toString
}


Board.scala

package cube36

case class Board(val placedPieces: IndexedSeq[IndexedSeq[Option[Piece]]] /*rows of cols*/ ) {

val row1Heights = List[Int](1, 3, 4, 5, 2, 0)
val row2Heights = List[Int](2, 5, 0, 4, 1, 3)
val row3Heights = List[Int](0, 1, 3, 2, 5, 4)
val row4Heights = List[Int](5, 4, 1, 3, 0, 2)
val row5Heights = List[Int](4, 2, 5, 0, 3, 1)
val row6Heights = List[Int](3, 0, 2, 1, 4, 5)
val contours = List[List[Int]](row1Heights, row2Heights, row3Heights, row4Heights, row5Heights, row6Heights)

private[cube36] def spaces: Seq[(Int, Int)] = for (row <- 0 to 5; col <- 0 to 5; if (placedPieces(row)(col)).isEmpty) yield (row, col)

private[cube36] def suitable(space: (Int, Int), piece: Piece): Boolean = {
lazy val spaceEmpty = placedPieces(space._1)(space._2).isEmpty

lazy val height = contours(space._1)(space._2)
lazy val rightHeight = height + piece.size == 6

lazy val colour = piece.colour
lazy val cl = placedPieces.map(row => row(space._2))
lazy val matches = cl.map(x => x.map(p => p.colour == colour))
lazy val colourAlreadyInCol = matches.contains(Some(true))

lazy val rw = placedPieces(space._1)
lazy val rmatches = rw.map(x => x.map(p => p.colour == colour))
lazy val colourAlreadyInRow = rmatches.contains(Some(true))

val unsuitable = (!spaceEmpty) || (!rightHeight) || colourAlreadyInCol || colourAlreadyInRow
!unsuitable
}

private[cube36] def addPiece(rowNum: Int, colNum: Int, piece: Piece, checkSuitable: Boolean = true): Board = {
if (checkSuitable && !suitable((rowNum, colNum), piece)) throw new IllegalArgumentException("Not suitable for this poition")

val newRow = placedPieces(rowNum).updated(colNum, Some(piece))
Board(placedPieces.updated(rowNum, newRow))
}

private[this] def rowString(row:IndexedSeq[Option[Piece]]):String = {
val r=for(p<-row) yield p match {
case Some(pc) => "|" + pc
case None => " _ "
}
r.foldLeft("")((a,b)=>a+b) + "|"
}

override def toString: String = {
val border = "==================="
val content = for (row <- placedPieces) yield rowString(row)

val folded=content.foldLeft(border)((a,b)=> a +"\n" +  b)
folded + "\n" + border
}

}

object Board {
def apply(): Board = {
val emptyRow = IndexedSeq[Option[Piece]](None, None, None, None, None, None)
val emptyPieces = IndexedSeq(emptyRow, emptyRow, emptyRow, emptyRow, emptyRow, emptyRow)
Board(emptyPieces)
}
}

-

## Puzzle.scala

case class CubePuzzle(val board: Board, val availablePieces: List[Piece])


Case classes don't need "val" before field names.

def solve(solutionsSoFar: List[Board]=List[Board]()): List[Board] =


More idiomatic is Nil instead of List[Board](). Although sometimes I use List.empty[Board] in case I change the collection type (Nil is only available on List)

if (this.availablePieces.size == 0) this.board :: solutionsSoFar


Instead, how about

availablePieces match {
case Nil => board :: solutionsSoFar
case nextPiece :: tail => ...


Also, I suspect the for loop in solve() can be rewritten so that you do not need to call flatten.

## Board.scala

val unsuitable = ...


This seems backward, why not just return

spaceEmpty && rightHeight && !colourAlreadyInCol && !colourAlreadyInRow

-
Thanks (and sorry for the slow accept). – jb77 May 16 '13 at 12:07
Agree on the case class vals, Nil and pattern matching. The "val unsuitable =..." was an attempt to use lazy evaluation to avoid doing all the checks every time - does that make sense? – jb77 May 16 '13 at 12:08

A more scala idiomatic-way to write the for loop in your solve(...) method such that it is unnecessary to call flatten:

    val sols =
availableSpots flatMap (spot =>
addPiece(spot._1, spot._2, nextPiece, false).solve(solutionsSoFar))
sols.toList


Essentially what flatMap is doing is traversing through availableSpots applying some function to each of its values, and concatenating the results.

-