Recurcive and (simple) Iterative solution to the Tower of Hanoi

hanoi.fsx

/// builds 3 towers with the given number of disks in the first tower
let towers diskNumber = [| [1 .. diskNumber]; []; [] |]

//-------------------------------------------------------------------------------------------------
// RECURSIVE SOLUTION

/// moves the top disks in fromTower onto toTower
/// displays the move and the result 
/// checks if the move is legal
let move (towers:_[]) fromTower toTower =
   match towers.[fromTower], towers.[toTower] with 
   | [], _ -> 
      sprintf "nothing to move in tower %d" fromTower |> failwith
   | tf::qf, tt::qt when tf > tt -> 
      sprintf "illegal move, %d > %d" tf tt |> failwith
   | tf::qf, l -> 
      towers.[toTower] <- tf :: l
      towers.[fromTower] <- qf
      printfn "moving %d from %d to %d : %A %A %A" tf fromTower toTower towers.[0] towers.[1] towers.[2]

/// uses recursivity to move n towers from fromTower to toTower (using spareTower as a transition zone)
let rec hanoi towers n fromTower toTower spareTower = 
   if n = 0 then () else 
      hanoi towers (n-1) fromTower spareTower toTower 
      move towers fromTower toTower
      hanoi towers (n-1) spareTower toTower fromTower

//-------------------------------------------------------------------------------------------------
// ITERATIVE SOLUTION
// https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution

/// returns true if there are pieces left out of toTower
let notFinished (towers:_[]) fromTower toTower spareTower = (towers.[fromTower] <> []) || (towers.[spareTower] <> [])

/// moves the top disks in fromTower onto toTower
/// displays the move and the result 
/// checks if the move is legal, moves from toTower onto fromTower if required to legalized the move
let rec legalMove (towers:_[]) fromTower toTower =
   match towers.[fromTower], towers.[toTower] with 
   | [], [] -> 
      sprintf "nothing to move in tower %d and %d" fromTower toTower |> failwith
   | [], _ -> 
      legalMove towers toTower fromTower
   | tf::qf, tt::qt when tf > tt -> 
      legalMove towers toTower fromTower
   | tf::qf, lt -> 
      towers.[toTower] <- tf :: lt
      towers.[fromTower] <- qf
      printfn "moving %d from %d to %d : %A %A %A" tf fromTower toTower towers.[0] towers.[1] towers.[2]

/// iteratively moves n towers from fromTower to toTower (using spareTower as a transition zone)
let hanoiIter towers n fromTower toTower spareTower = 
   let rec moveIter smalest nonSmalest1 nonSmalest2 shouldMoveSmalest =
      if notFinished towers fromTower toTower spareTower then 
         if shouldMoveSmalest then 
            move towers smalest nonSmalest1
            moveIter nonSmalest1 nonSmalest2 smalest (not shouldMoveSmalest)
         else 
            legalMove towers nonSmalest1 nonSmalest2
            moveIter smalest nonSmalest1 nonSmalest2 (not shouldMoveSmalest)
   if n%2 = 0 then moveIter fromTower spareTower toTower true 
              else moveIter fromTower toTower spareTower true

//-------------------------------------------------------------------------------------------------
// TEST

let diskNumber = 5

printfn "Recursive solution :"
hanoi (towers diskNumber) diskNumber 0 2 1

printfn "Iterative solution :"
hanoiIter (towers diskNumber) diskNumber 0 2 1