Towers of Hanoi

A Roc solution for the popular Towers of Hanoi problem.

Code

module [
    hanoi,
]

## Solves the Tower of Hanoi problem using recursion. Returns a list of moves
## which represent the solution.
hanoi :
    {
        numDisks : U32, # number of disks in the Tower of Hanoi problem
        from : Str, # identifier of the source rod
        to : Str, # identifier of the target rod
        using : Str, # identifier of the auxiliary rod
        moves : List (Str, Str), # list of moves accumulated so far
    }
    -> List (Str, Str)
hanoi = \{ numDisks, from, to, using, moves } ->
    if numDisks == 1 then
        List.concat moves [(from, to)]
    else
        moves1 = hanoi {
            numDisks: (numDisks - 1),
            from,
            to: using,
            using: to,
            moves,
        }

        moves2 = List.concat moves1 [(from, to)]

        hanoi {
            numDisks: (numDisks - 1),
            from: using,
            to,
            using: from,
            moves: moves2,
        }

start = { numDisks: 0, from: "A", to: "B", using: "C", moves: [] }

## Test Case 1: Tower of Hanoi with 1 disk
expect hanoi { start & numDisks: 1 } == [("A", "B")]

## Test Case 2: Tower of Hanoi with 2 disks
expect hanoi { start & numDisks: 2 } == [("A", "C"), ("A", "B"), ("C", "B")]

## Test Case 3: Tower of Hanoi with 3 disks
expect hanoi { start & numDisks: 3 } == [("A", "B"), ("A", "C"), ("B", "C"), ("A", "B"), ("C", "A"), ("C", "B"), ("A", "B")]

Output

Run this from the directory that has Hanoi.roc in it:

$ roc test Hanoi.roc

0 failed and 3 passed in 662 ms.