Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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)
  }
} 
share|improve this question

2 Answers 2

up vote 3 down vote accepted

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
share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.