hanoi.fsx

[<RequireQualifiedAccess>]
module Hanoi =
  open System.Collections.Generic

  [<Struct>]
  type Kind = Tower1 | Tower2 | Tower3

  type Commands = seq<Kind * Kind>

  let solve n: Commands =
    if n < 0 then invalidArg (nameof n) $"should be equal to or larger than 0."
    let rec loop count k1 k2 k3 =
      if count = 0 then Seq.empty
      elif count = 1 then seq { (k1, k3) }
      else
        seq {
          yield! loop (count - 1) k1 k3 k2
          yield (k1, k3)
          yield! loop (count - 1) k2 k1 k3
        }

    loop n Tower1 Tower2 Tower3

  let init n = [ 1..n ], [], []
  let step (src, dst) state =
    let x, t1, t2, t3 =
      match src, state with
      | Tower1, (x::t1, t2, t3)
      | Tower2, (t1, x::t2, t3)
      | Tower3, (t1, t2, x::t3) -> x, t1, t2, t3
      | _ -> failwith "invalid state"

    match dst with
    | Tower1 -> (x::t1, t2, t3)
    | Tower2 -> (t1, x::t2, t3)
    | Tower3 -> (t1, t2, x::t3)

do
  let test n =
    let commands = Hanoi.solve n
    let state = Hanoi.init n
    commands
    |> Seq.fold (fun s c -> printfn "%A" c; Hanoi.step c s) state
    |> function
      | [], [], t3 when t3 = (match state with t1,_,_ -> t1) -> ()
      | _ -> failwith "test failed"

  test 4
(*
(Tower1, Tower2)
(Tower1, Tower3)
(Tower2, Tower3)
(Tower1, Tower2)
(Tower3, Tower1)
(Tower3, Tower2)
(Tower1, Tower2)
(Tower1, Tower3)
(Tower2, Tower3)
(Tower2, Tower1)
(Tower3, Tower1)
(Tower2, Tower3)
(Tower1, Tower2)
(Tower1, Tower3)
(Tower2, Tower3)
*)