TowerOfHanoiSolver.kt

/**
 * Solves Tower of Hanoi (https://en.wikipedia.org/wiki/Tower_of_Hanoi) problem and returns
 * the steps to solve the problem. Use the steps to visualize the puzzle.
 *
 * Usage    : TowerOfHanoiSolver().solve(disk_count)
 * Returns  : List of moves - `List<Pair<Int, Int>>` where each `Pair` represents a move from
 *            `Pair.first` tower to `Pair.second` tower.
 */

class TowerOfHanoiSolver {

    private data class Tower(
        val id: Int,
        var count: Int = 0, // Could use a Stack/DQ here to simulate.
    ) {
        fun push() = count++
        fun pop() = count--
        val size get() = count
    }

    private lateinit var tower1: Tower
    private lateinit var tower2: Tower
    private lateinit var tower3: Tower

    private lateinit var moves: MutableList<Pair<Int, Int>>

    private fun setup(count: Int) {

        tower1 = Tower(1, count)
        tower2 = Tower(2)
        tower3 = Tower(3)

        moves = mutableListOf()

    }

    fun solve(count: Int): List<Pair<Int, Int>> {

        setup(count)

        // Move items from T1 to T3, use T2 as a temporary tower
        move(tower1, tower3, tower2, tower1.size)

        return moves
    }

    private fun move(from: Tower, to: Tower, temp: Tower, count: Int) {

        // Only one item? Move directly from source to destination.
        if (count == 1) {

            from.pop()
            to.push()
            moves.add(from.id to to.id)

        } else {

            // Move N-1 from source to temp. Use the destination tower as a temp tower for this step.
            move(from, temp, to, count - 1)

            // Move Nth item from source to destination.
            from.pop()
            to.push()
            moves.add(from.id to to.id)

            // Move N-1 from temp to destination. Use the source tower as a temp tower for this step.
            move(temp, to, from, count - 1)
        }

    }

}


fun main() {

    val towerOfHanoiSolver = TowerOfHanoiSolver()

    println("Moves for 3 disks:")

    towerOfHanoiSolver
        .solve(3)
        .forEach {
            println("Move disk from ${it.first} to ${it.second}")
        }

}