Sometimes it’s fun to visit a classic CS problem when you’re learning a new language. Since I’m new to Swift, I wanted to tackle a pretty classic recursion problem, using unit tests. The Tower of Hanoi problem is a great introduction to recursion and once you get it.. it really demonstrates how recursion is really about breaking a larger problem down into smaller pieces.

The goal of the puzzle is to move all the disks from the leftmost peg to the rightmost peg, adhering to the following rules: Move only one disk at a time. A larger disk may not be placed ontop of a smaller disk.

Tackle by breaking the problem down

Often the problem is introduced for moving 3-5 disks. Consider the problem of moving 2 disks first.

You’re going to first move the top disk off to the middle tower, here called the buffer. Considering one tower to be a buffer is intrinsic to the solution so keep that idea in mind!

You’ll move the second, larger disk disk off to the final or destination tower.

You’ll finally move the original disk on top of the larger disk which is now on the destination tower.

A Unit Test

Unit Tests are obviously great because they let you know when you’ve finished. It makes validating an expected outcome so much easier. In this example, I’m using Quick and Nimble to unit test my Hanoi Tower problem

class HanoiTowerSpec: QuickSpec {
    override func spec() {
        describe("Hanoi tower") {
            
            it("should move 5 disks from tower A to tower C") {
                
                var towerA = Stack(name: "Tower A")
                var towerB = Stack(name: "Tower B")
                var towerC = Stack(name: "Tower C")
                
                //put the disks on the first tower
                for index in 1...5 {
                    towerA.push(index)
                }
                
                let hanoi = HanoiTower()
                hanoi.transfer(numDisks: 5,
                               origin: &towerA,
                               destination: &towerC,
                               buffer: &towerB)
                
                expect(towerC.contents.count).to(equal(5))
                expect(hanoi.numMoves).to(equal(31)). // a hanoi tower solution should be (2^n - 1) moves where n is the number of disks
            }
        }
    }
}

Solution Review

The key to turning this into a recursive code solution is to keep in mind that first move is really a buffer, on the way to the target of moving two disks from tower 1 to tower 3. Also, all towers can and should be used as buffers towers as the problem is broken down.

But, let’s first look at some psuedo code for the two disk problem.

Source tower: Tower 1

Target tower: Tower 3

Buffer tower: Tower 2

  1. Move disk count - 1 from source to the buffer.
  2. Move 1 disk from source to the destination.
  3. Move disk count - 1 from buffer to the destination.

Now, recursion always involves a function that calls itself until it has reached the end of it’s execution.. then returning from the inside calls to the earlier ones.. allowing any remaining executions to occur after the recursive call returns.

Let’s design our function.

class HanoiTower {    
    func transfer(numDisks: Int, origin: Stack, destination: Stack, buffer: Stack) {
        
    }   
}

This will serve our needs outlined above.. for each move of n number of disks.. we’ll need to specify an origin tower (here called Stack as these are essentially the data type Stack), a destination and a buffer.

Just for code completion. The Stack looks something like the following:

struct Stack {
    var name: String
    var contents: Array<Int>
    
    init(name: String, contents: Array<Int> = Array<Int>()) {
        self.name = name
        self.contents = contents
    }
    
    mutating func push(_ val: Int) {
        self.contents.append(val)
    }
    
    mutating func pop() -> Int {
        return self.contents.removeLast()
    }
}

Now let’s fill it out the transfer function to handle n number of disks.

class HanoiTower {    
    var numMoves = 0

    func transfer(numDisks: Int, origin: inout Stack, destination: inout Stack, buffer: inout Stack) {
        
        if numDisks > 1 {
            print("Transferring \(numDisks) from \(origin.name) to \(destination.name) with \(buffer.name) as buffer.")
            let nextDisks = numDisks - 1
            
            transfer(numDisks: nextDisks,
                     origin: &origin,
                     destination: &buffer,
                     buffer: &destination)
            
            transfer(numDisks: 1, origin: &origin, destination: &destination, buffer: &buffer)
            transfer(numDisks: nextDisks, origin: &buffer, destination: &destination, buffer: &origin)
        } else if numDisks == 1 {
            print("Moving single disk from \(origin.name) to \(destination.name)")
            numMoves += 1
            let disk = origin.pop()
            destination.push(disk)
        }
    }
}

Summing Up

Hope this all makes sense. Again, the key to to break the problem down. The print statements in the solution above help to realize that you may be starting out calling the function to move n=5 disks.. but it starts making calls to move n-1 disks and disks don’t really start moving until a call to move the first disk off the origin, which is many calls into the solution, upon which you return out to all the earlier method calls to move disks from your buffer to whatever the destination is.

Also, what’s essential conceptually is to consider that the buffer is shifting for each call.

Check out my solution for this in this Github repository.

Swift - Child of the LLVM

Exploring what Swift achieves on LLVM that Obj-C could not. Continue reading

Understanding The LLVM - Introduction

Published on June 18, 2017

Developing for Hardware & Visibility

Published on May 24, 2017