Scala朝練(2)

gistfile1.scala

package com.taroid.scala.practice

import scala.annotation.tailrec


object SlidePuzzle {

  def main(args: Array[String]) {
    val board = Board(List(3, 1, 2, 4, 0, 5, 6, 7, 8), 3, 0)
    solve(List(new History(List(board)))).boards.foreach(println)
  }

  @tailrec
  private def solve(queue: Seq[History]): History = {
    assert(!queue.isEmpty)

    val history = queue.head
    val board = history.currentBoard
    if (board.totalExpectedDistance == 0) {
      history
    } else {
      solve(board.move
        .map(history.add)
        .foldLeft(queue)((q, h) => h +: q)
        .sortBy(_.currentBoard.cost))
    }
  }
}

class History(val boards: List[Board]) {

  def add(board: Board) = {
    new History(board :: boards)
  }

  def currentBoard = boards.head
}

object Board {

  val blankCell = 0

  private case class Position(row: Int, column: Int) {
    require(0 <= row)
    require(0 <= column)

    def distance(that: Position) = {
      Math.abs(this.row - that.row) + Math.abs(this.column - that.column)
    }
  }

}

case class Board(private val cells: Seq[Int], private val width: Int, private val count: Int) {

  import com.taroid.scala.practice.Board.Position
  import com.taroid.scala.practice.Board.blankCell

  private def indexToPosition(index: Int) = new Position(index / width, index % width)

  private def positionOf(cell: Int) = indexToPosition(cells.indexOf(cell))

  private def expectedDistance(cell: Int) = positionOf(cell).distance(indexToPosition(cell))

  def totalExpectedDistance = cells.fold(0)(_ + expectedDistance(_))

  def cost = count + totalExpectedDistance

  private def swapIndex(index1: Int, index2: Int) = {
    val buffer = cells.toBuffer
    val w = buffer(index1)
    buffer(index1) = buffer(index2)
    buffer(index2) = w
    buffer.toList
  }

  private def swapCell(cell1: Int, cell2: Int) = swapIndex(cells.indexOf(cell1), cells.indexOf(cell2))

  def move = cells.map(cell => copy(cells = swapCell(blankCell, cell), count = count + 1)).
    filter(board => positionOf(blankCell).distance(board.positionOf(blankCell)) == 1)
}