読者です 読者をやめる 読者になる 読者になる

ハノイの塔をHaskellで書いた

さっきまで理解してなかったので書いてみた。Wikipediaの書き方もわかりづらいし検索上位にわりと酷いのばっかりひっかかるんですがそれは…

import Debug.Trace

moveAtoC :: ([Int], [Int], [Int]) -> ([Int], [Int], [Int])
moveAtoC ((a:as), bs, cs) = (as, bs, a:cs)

solveHanoi n = solveHanoi' n ([1..n], [], [])

solveHanoi' :: Int -> ([Int], [Int], [Int]) -> ([Int], [Int], [Int])

-- Aにある円盤n個を、Bを使いながらCに移動する
solveHanoi' 1 t = moveAtoC t
solveHanoi' n (as, bs, cs) = (as''', bs''', cs''')
  where (as'  , cs'  , bs'  ) = solveHanoi' (n - 1) (as, cs, bs)
        (as'' , bs'' , cs'' ) = moveAtoC (as', bs', cs')
        (bs''', as''', cs''') = solveHanoi' (n - 1) (bs'', as'', cs'')

A → Bに一番下を除いて移動させて、一番下をA→Cに移動させた上で、B→Cの移動をする。これを再帰的に定義する。
コードに落とす時は、棒を入れ替えたとして考えるのがポイントらしい。