ハノイの塔

OCaml で手続き的に書いてみる．
ハノイの塔

hanoi' が実質計算します．型合わせていったらできたけどぐちゃぐちゃになりました．
あまり説明する気も，かといって綺麗に書き直す気もおきません．

解き方はセオリーどうり
1. n-1個を a から c を使って b に移す．
2. a に残った 1 個を c に移す
3. n-1個を b から a を使って c に移す

hanoi' がこれをやっています．

let move x y =

  let (xs, ys) = (fst x, fst y) in

    match xs with

      z::zs -> 

	Printf.printf "%d: %s -> %s\n" z (snd x) (snd y); 

	( (zs, snd x), (z::ys, snd y) )
let rec hanoi' n a b c =

  if n = 1 then 

    let (a, c) = move a c in

      (a , b , c)

  else 

    let (a, c, b) = hanoi' (n-1) a c b in

    let (a, c) = move a c in

    let (b, a, c) = hanoi' (n-1) b a c in

      (a, b, c)
let hanoi a b c = 

  let (a, b, c) = hanoi' (List.length a) (a, "a") (b, "b") (c, "c")

  in (fst a, fst b, fst c)

実行結果

# hanoi [1;2;3] [] [];;

1: a -> c

2: a -> b

1: c -> b

3: a -> c

1: b -> a

2: b -> c

1: a -> c

 - : int list * int list * int list = ([ ], [ ], [1; 2; 3])

#