Scalaの練習

Slidepuzzle.scala

object Main {
  def main(args: Array[String]) {
    val puzzle = new SlidePuzzle(3, List(3, 1, 2, 4, 7, 5, 6, 0, 8), 0)
    val solvedPuzzleHistory = SlidePuzzle.solve(puzzle)

    assert(solvedPuzzleHistory(3).cells == List(3, 1, 2, 4, 7, 5, 6, 0, 8))
    assert(solvedPuzzleHistory(2).cells == List(3, 1, 2, 4, 0, 5, 6, 7, 8))
    assert(solvedPuzzleHistory(1).cells == List(3, 1, 2, 0, 4, 5, 6, 7, 8))
    assert(solvedPuzzleHistory(0).cells == List(0, 1, 2, 3, 4, 5, 6, 7, 8))
  }
}

object SlidePuzzle {
  private def distance(cell1: (Int, Int), cell2: (Int, Int)): Int =
    (cell1._1 - cell2._1).abs + (cell1._2 - cell2._2).abs

  def solve(p: SlidePuzzle): List[SlidePuzzle] = {
    def solve(queue: List[List[SlidePuzzle]]): List[SlidePuzzle] = {
      val current = queue.head
      val currentPuzzle = current.head
      return if(currentPuzzle.cost() == 0) current
        else solve((queue ++ currentPuzzle.move().map(_ :: current)).sortWith {
          (o1, o2) => o1.head <= o2.head
        })
    }

    return solve(List(List(p)))
  }
}

class SlidePuzzle(
                   val width: Int,
                   val cells: List[Int],
                   val count: Int) extends Ordered[SlidePuzzle] {

  private def position(cell: Int): (Int, Int) = {
    def indexToPosition(index: Int): (Int, Int) = (index % width, index / width)
    return indexToPosition(cells.indexOf(cell))
  }

  def winDistance(cell: Int): Int =
    SlidePuzzle.distance(
      position(cell),
      new SlidePuzzle(width, 0.to(cells.size - 1).toList, 0).position(cell)
    )

  private def totalWinDistance(): Int = cells.map(winDistance _).sum

  private def cost(): Int = count + totalWinDistance()

  override def compare(that: SlidePuzzle): Int = cost - that.cost

  def swap(cell1: Int, cell2: Int): SlidePuzzle = {
    def swapByIndex(index1: Int, index2: Int): List[Int] = {
      val buf = cells.toBuffer
      buf(index1) = cells(index2)
      buf(index2) = cells(index1)
      return buf.toList
    }

    return new SlidePuzzle(width , swapByIndex(cells.indexOf(cell1), cells.indexOf(cell2)), count)
  }

  def move(): List[SlidePuzzle] = {
    cells.map(swap(0, _)).filter(p => SlidePuzzle.distance(position(0), p.position(0)) == 1)
  }
}