ハノイの塔をScalaで解く

ハノイの塔自体は再帰を使えば簡単に解けることは有名で、Googleれば大体すぐ出てくる。

def hanoi(height: Int, from: String, via: String, to: String): Unit = {
  if (height <= 0) {
    ()
  } else {
    // 1. スタート位置にある一番下以外のものをすべて関係のない場所に動かして
    hanoi(height - 1, from, to, via)
    // 2. スタート位置にある一番下を目的地に動かして
    println(s"Move disk ${height} from ${from} to ${to}.")
    // 3. `1`で関係のないところによけておいたものを全て目的地に移動させる。
    hanoi(height - 1, via, from, to)
  }
}

> hanoi(3, "left", "middle", "right")
Move disk 1 from left to right.
Move disk 2 from left to middle.
Move disk 1 from right to middle.
Move disk 3 from left to right.
Move disk 1 from middle to left.
Move disk 2 from middle to right.
Move disk 1 from left to right.

ただ、このままだと末尾再帰でないという理由でいつかはスタックが足りなくなるはず。 それより前に計算量が大きすぎて帰ってこなくなりそうな気もするけど。。。

ということで末尾再帰にしたい！たぶん。

関数らしくするために、値を返そう。

case class HanoiStep(height: Int, from: String, via: String, to: String)
def hanoi1(height: Int, from: String, via: String, to: String) = (HanoiStep, String, HanoiStep) = {
  val pre = HanoiStep(height - 1, from, to, via)
  val move = s"Move disk ${height} from ${from} to ${to}."
  val post = HanoiStep(height - 1, via, from, to)
  (pre, move, post)
}

Tree構造！！

自分でprintすべきものがrootにあって、左に自分より前にprintすべきものの塊、右に自分より後のがある。

左の枝、自分自身、右の枝の順で走査していけば結果になるはず！！

・・・Treeの走査って再帰でどうやるのん？？？ わからないから後で考えるとして、一番左の要素だけ展開すれば末尾再帰できるはずだからそれをやろう。

import scala.annotation.tailrec

sealed trait HanoiStep
case class MultiSteps(height: Int, from: String, via: String, to: String) extends HanoiStep
case class SingleStep(id: Int, from: String, to: String) extends HanoiStep

def expand(ms: MultiSteps): List[HanoiStep] = ms.height match {
  case n if n <= 0 => List.empty
  case 1 => List(SingleStep(1, ms.from, ms.to))
  case _ => {
    val pre = MultiSteps(ms.height - 1, ms.from, ms.to, ms.via)
    val ss = SingleStep(ms.height, ms.from, ms.to)
    val post = MultiSteps(ms.height - 1, ms.via, ms.from, ms.to)
    List(pre, ss, post)
  }
}

@tailrec
def expandHead(ss: List[HanoiStep]): List[HanoiStep] = ss match {
  case ((h: MultiSteps) :: t) => expandHead(expand(h) ++ t)
  case _ => ss
}

> val a = MultiSteps(5, "left", "middle", "right")
a: MultiSteps = MultiSteps(5,left,middle,right)

> val b = expand(a)
b: List[HanoiStep] = List(MultiSteps(4,left,right,middle), SingleStep(5,left,right), MultiSteps(4,middle,left,right))

> val c = expandHead(b)
c: List[HanoiStep] = List(SingleStep(1,left,right), SingleStep(2,left,middle), MultiSteps(1,right,left,middle), ....

これをとりあえずStreamでくるめば、それっぽくは動きそう。

def unfold[A, B](a: A)(f: A => Option[(B, A)]): Stream[B] = f(a) match {
  case Some((b, a)) => Stream.cons(b, unfold(a)(f))
  case _ => Stream.empty
}

def hanoi(height: Int, from: String, via: String, to: String): Stream[String] = {
  import scala.annotation.tailrec
  sealed trait HanoiStep
  case class MultiSteps(height: Int, from: String, via: String, to: String) extends HanoiStep
  case class SingleStep(id: Int, from: String, to: String) extends HanoiStep
  def f1(ms: MultiSteps): List[HanoiStep] = ms.height match {
    case n if n <= 0 => List.empty
    case 1 => List(SingleStep(1, ms.from, ms.to))
    case _ => {
      val pre = MultiSteps(ms.height - 1, ms.from, ms.to, ms.via)
      val ss = SingleStep(ms.height, ms.from, ms.to)
      val post = MultiSteps(ms.height - 1, ms.via, ms.from, ms.to)
      List(pre, ss, post)
    }
  }
  @tailrec
  def f2(ss: List[HanoiStep]): List[HanoiStep] = ss match {
    case ((h: MultiSteps) :: t) => f2(f1(h) ++ t)
    case _ => ss
  }
  val init = f1(MultiSteps(height, from, via, to))
  unfold(init)(a => f2(a) match {
    case (h: SingleStep) :: t => Some((s"Move disk ${h.id} from ${h.from} to ${h.to}.", t))
    case _ => None
  })
}

> val a = hanoi(3, "left", "middle", "right")
a: Stream[String] = Stream(Move disk 1 from left to right., ?)

> a.foreach(println)
Move disk 1 from left to right.
Move disk 2 from left to middle.
Move disk 1 from right to middle.
Move disk 3 from left to right.
Move disk 1 from middle to left.
Move disk 2 from middle to right.
Move disk 1 from left to right.

> val b = hanoi(4, "left", "middle", "right").zipWithIndex
b: scala.collection.immutable.Stream[(String, Int)] = Stream((Move disk 1 from left to middle.,0), ?)

> val c = b.map { case (a, b) => s"${b + 1}: ${a}" }
c: scala.collection.immutable.Stream[String] = Stream(1: Move disk 1 from left to middle., ?)

> c.foreach(println)
1: Move disk 1 from left to middle.
2: Move disk 2 from left to right.
3: Move disk 1 from middle to right.
4: Move disk 3 from left to middle.
5: Move disk 1 from right to left.
6: Move disk 2 from right to middle.
7: Move disk 1 from left to middle.
8: Move disk 4 from left to right.
9: Move disk 1 from middle to right.
10: Move disk 2 from middle to left.
11: Move disk 1 from right to left.
12: Move disk 3 from middle to right.
13: Move disk 1 from left to middle.
14: Move disk 2 from left to right.
15: Move disk 1 from middle to right.

とりあえず動いた。

ツリーを走査する簡単なやり方とか、もしくは継続？かなんかのテクニックを使えばもっとシンプルになるんだろうなぁ。

続きはまた次回。