Scalaプログラミング5 MapとStackを使ってみる

Beginning Scala programing5

初心者ぺちぱーがGitHubでScalaレッスンを始めたぞ。5回目はコレクションクラスのMapとStackを使ってみよう。

引き続き、練習問題はここのページだ。今回はハノイの塔を攻略してみようと思う。

Lessen 5: Tower of Hanoi

再帰関数を使ったアルゴリズムで有名な問題。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。

最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。

円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

円盤が1枚の場合はA->Cと移動しておしまい。

円盤が2枚の場合は

1をA->B
2をA->C
1をB->C

円盤が3枚の場合は

1をA->C
2をA->B
1をC->B
3をA->C
1をB->A
2をB->C
1をA->C

と移動すればいい。ポイントとなるのは、

Aにある1からn-1までの円盤をAからBに移動
円盤nをA->Cに移動させる
Bにある1からn-1までの円盤をBからCに移動

手順となるところだ。円盤nを、AからBを経由してCに移動させる、という操作をmove(n, a, b, c)で定義できるのであれば、上記の操作は次のように書けるはずだ。

def move(n: Int, a: String, b: String, c: String) {
  move(n-1, a, c, b)
  println("move disk %d from %s to %s".format(n, a, c))
  move(n-1, b, a, c)
}

n=2の場合、1の操作が、n=3の場合、1-3の操作がmove(n-1, a, c, b)（Aにある1からn-1までの円盤をAからBに移動）に相当する。n=2の場合、3の操作が、n=3の場合、5-7の操作がmove(n-1, b, a, c)（Bにある1からn-1までの円盤をBからCに移動）に相当するわけだ。

というわけで、最初はこんなクラスを書いてみた。

class SimpleHanoiSolver {
  /**
   * Solve tower of Hanoi.
   *
   * @param n Number of disks.
   */
  def solve(n: Int) {
    move(n, "A", "B", "C")
  }
 
  /**
   * Move disk from peg a to peg c through peg b.
   *
   * @param n Number of disks.
   * @param a Peg name from.
   * @param b Peg name through.
   * @param c Peg name to.
   */
  private
  def move(n: Int, a: String, b: String, c: String) {
    if (n > 0) {
      move(n-1, a, c, b)
      println("move disk %d from %s to %s".format(n, a, c))
      move(n-1, b, a, c)
    }
  }
}

n=2の場合。

n=2の場合の実行結果

move disk 1 from A to B
move disk 2 from A to C
move disk 1 from B to C
 
Process finished with exit code 0

n=3の場合。

n=3の場合の実行結果

move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to C
 
Process finished with exit code 0

よし。できてそうだな。

Visualize pegs state using Map and Stack

次は、移動中の円盤の状態を可視化するために、杭をStackと見立てて、状態をもたせてみよう。

Stack

円盤の出し入れは、first in last outなので、杭の状態はStackで表現してみよう。円盤の出し入れをするために、今回はmutable.Stackを使う。円盤の大きさは番号で表現するので、Intにしておく。

import scala.collection.mutable
 
val pegA = mutable.Stack[Int]()
val pegB = mutable.Stack[Int]()
val pegC = mutable.Stack[Int]()

Map

次は、杭のラベルとStackを関連づけるために、Mapを使ってみよう。

val pegs = Map[String, mutable.Stack]("A" -> pegA, "B" -> pegB, "C" -> pegC)

Constructor

今までは、objectで宣言してシングルトンにしていたけれど、杭の状態を保持するために、円盤の枚数を与えられると、その枚数の円盤をStackにpushできるクラスを作ってみよう。

class State(val num: Int, val pegs: Map[String, mutable.Stack]) {
  // I won't hoge
}

Scalaのコンストラクタは、クラス定義の先頭に書くことになっている。このコンストラクタをprimary constructor（基本コンストラクタ）という。こう書いた場合、numとpegsがクラスメンバーとして定義され、コンストラクタ引数が自動的にメンバーにセットされるようになる。メンバーはvalとなっているため、setterアクセスはできず、getterのみアクセス可能となる。private val pegsと書くと、外部からのアクセスはできなくなる。setter/getterは、わざわざ定義しなくても、メンバーにアクセスできるようになっている。

val state = new State(3, Map("A" -> mutable.Stack()))
println(state.num) // => 3
// valなのでこれはできない
// state.num = 5

Constructor overload

pegsは内部で生成するようにしたいので、別のコンストラクタも定義しておこう。コンストラクタはthis()で定義する。基本コンストラクタ以外に定義したコンストラクタはauxiliary constructor（補助コンストラクタ）という。

class State(val num: Int, val pegs: Map[String, mutable.Stack]) {
  def this(num: Int) {
    this(num, Map("A" -> mutable.Stack[Int](), "B" -> mutable.Stack[Int](), "C" -> mutable.Stack[Int]()))
  }
}

コンストラクタをオーバーロードする場合、基本コンストラクタ、または定義済みの補助コンストラクタを最初に実行しなけらばいけない。コップ本のp.111-p.116に記載がある。この辺は、Scala referenceの5.3 Class Definitionsの方が詳しい記載があるかもしれない。~~今でしょ！~~あとで読もう。

Implementation

Initial disks

インスタンス生成時に、pegsに円盤を追加しておこう。

def this(num: Int) {
    this(num, Map("A" -> mutable.Stack[Int](), "B" -> mutable.Stack[Int](), "C" -> mutable.Stack[Int]()))
    clear(num)
  }
 
  def clear(num: Int) {
    foreachPegName(pegs(_).clear())
 
    // fill initial disks to peg "A"
    (1 to num).reverse.foreach(pegs("A").push(_))
  }
 
  private
  def foreachPegName(func: String => Unit) { List("A", "B", "C").foreach(func) }

Disk operation

円盤を移動する操作は、Stackのpush()とpop()メソッドで行う。ハノイの塔のルールでは、小さい円盤の上に大きい円盤を乗せることはできないので、違反した場合には例外を投げるようにしてみた。IllegalArgumentExceptionでいいのかな。どうなんだろ。

def move(a: String, b: String) = moveDisk(pegs(a), pegs(b))
 
  private
  def moveDisk(from: mutable.Stack[Int], to: mutable.Stack[Int]) =
    if (to.isEmpty || from.head < to.head) {
      to.push(from.pop()).head
    }
    else throw new IllegalArgumentException

Print Stack status

状態の表示はこんな感じ。

def printResult(disk: Int, a: String, b: String) {
    println("move disk %d from %s to %s".format(disk, a, b))
    printState()
  }
 
  def printState() {
    foreachPegName(name => println("%s: %s".format(name, pegs(name))))
    println("")
  }

State class

全体としてはこんな感じになった。

State.scala

class State(val num: Int, val pegs: Map[String, mutable.Stack[Int]]) {
 
  def this(num: Int) {
    this(num, Map("A" -> mutable.Stack[Int](), "B" -> mutable.Stack[Int](), "C" -> mutable.Stack[Int]()))
    clear(num)
  }
 
  def clear(num: Int) {
    foreachPegName(pegs(_).clear())
 
    // fill initial disks to peg "A"
    (1 to num).reverse.foreach(pegs("A").push(_))
  }
 
  def move(a: String, b: String) = moveDisk(pegs(a), pegs(b))
 
  private
  def moveDisk(from: mutable.Stack[Int], to: mutable.Stack[Int]) =
    if (to.isEmpty || from.head < to.head) {
      to.push(from.pop()).head
    }
    else throw new IllegalArgumentException
 
  def printResult(disk: Int, a: String, b: String) {
    println("move disk %d from %s to %s".format(disk, a, b))
    printState()
  }
 
  def printState() {
    foreachPegName(name => println("%s: %s".format(name, pegs(name))))
    println("")
  }
 
  private
  def foreachPegName(func: String => Unit) { List("A", "B", "C").foreach(func) }
}

Solver

Stateクラスを使って、SimpleHanoiSolverを修正したクラスはこんな感じ

HanoiSolver.scala

class HanoiSolver {
  def solve(n: Int) {
    val state = new State(n)
 
    state.printState()
    move(state, n, "A", "B", "C")
  }
 
  private
  def move(state: State, n: Int, a: String, b: String, c: String) {
    if (n > 0) {
      move(state, n-1, a, c, b)
      val disk = state.move(a, c)
      state.printResult(disk, a, c)
      move(state, n-1, b, a, c)
    }
  }
}

Results

実行してみると、こんな感じで出力できた。ふむふむ。いい感じなんじゃないか！？お絵描きできるともっと分かりやすくなるのかなと考えると、出力部分は、別のPrinterHogeHogeクラスにした方が良かったかもしれない。

n=2の場合。

n=2の場合の実行結果

A: Stack(1, 2)
B: Stack()
C: Stack()
 
move disk 1 from A to B
A: Stack(2)
B: Stack(1)
C: Stack()
 
move disk 2 from A to C
A: Stack()
B: Stack(1)
C: Stack(2)
 
move disk 1 from B to C
A: Stack()
B: Stack()
C: Stack(1, 2)
 
 
Process finished with exit code 0

n=3の場合。

n=3の場合の実行結果

A: Stack(1, 2, 3)
B: Stack()
C: Stack()
 
move disk 1 from A to C
A: Stack(2, 3)
B: Stack()
C: Stack(1)
 
move disk 2 from A to B
A: Stack(3)
B: Stack(2)
C: Stack(1)
 
move disk 1 from C to B
A: Stack(3)
B: Stack(1, 2)
C: Stack()
 
move disk 3 from A to C
A: Stack()
B: Stack(1, 2)
C: Stack(3)
 
move disk 1 from B to A
A: Stack(1)
B: Stack(2)
C: Stack(3)
 
move disk 2 from B to C
A: Stack(1)
B: Stack()
C: Stack(2, 3)
 
move disk 1 from A to C
A: Stack()
B: Stack()
C: Stack(1, 2, 3)

Conclusion

5回目のレッスンもGitHubに上げてある。今回はクラスを作ってみたり、StackとMapを使ってみたりした。まとめ！

classの作り方
コンストラクタの使い方。基本コンストラクタと補助コンストラクタ
StackとMapの基本的な操作

Reference

Scala Reference

Scalaスケーラブルプログラミング第2版
作者: Martin Odersky; Lex Spoon; Bill Venners
出版社: インプレスジャパン
発売日: 2011-09-27
メディア: 単行本（ソフトカバー）
価格: ￥ 4,968