Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Towers of hanoi
// Challenge set here...
// https://blog.svpino.com/2015/06/07/programming-challenge-towers-of-hanoi
import UIKit
// convenience for printing
func moveRing(ring : Int, currentPole: Int, targetPole: Int) {
println("Move ring \(ring) from pole \(currentPole) to pole \(targetPole)")
}
// recursive function
func towersOfHanoi(rings : [Int], currentPole: Int, targetPole: Int) {
// only one ring. Just move it to target
if rings.count == 1 {
moveRing(rings[0], currentPole, targetPole)
return
}
// get all but the bottom ring
let topRings : [Int] = Array(rings[0..<rings.count - 1])
// set new target to "empty" pole
let newTarget = [1, 2, 3].filter{
$0 != currentPole && $0 != targetPole
}[0]
// move them to the new target
towersOfHanoi(topRings, currentPole, newTarget)
// move bottom pole to target
moveRing(rings[rings.count - 1], currentPole, targetPole)
// move other rings to target
towersOfHanoi(topRings, newTarget, targetPole)
}
let rings = [1, 2, 3, 4]
println("Number of moves = \(Int(pow(2.0, Double(rings.count))) - 1)")
towersOfHanoi(rings, 1, 3)
@oliverfoggin

This comment has been minimized.

Copy link
Owner Author

oliverfoggin commented Jun 7, 2015

Output...

Number of moves = 15
Move ring 1 from pole 1 to pole 2
Move ring 2 from pole 1 to pole 3
Move ring 1 from pole 2 to pole 3
Move ring 3 from pole 1 to pole 2
Move ring 1 from pole 3 to pole 1
Move ring 2 from pole 3 to pole 2
Move ring 1 from pole 1 to pole 2
Move ring 4 from pole 1 to pole 3
Move ring 1 from pole 2 to pole 3
Move ring 2 from pole 2 to pole 1
Move ring 1 from pole 3 to pole 1
Move ring 3 from pole 2 to pole 3
Move ring 1 from pole 1 to pole 2
Move ring 2 from pole 1 to pole 3
Move ring 1 from pole 2 to pole 3

@svpino

This comment has been minimized.

Copy link

svpino commented Jun 8, 2015

Awesome!

@oliverfoggin

This comment has been minimized.

Copy link
Owner Author

oliverfoggin commented Jun 8, 2015

Updated to use a better (shorter) "new target" method.

@oliverfoggin

This comment has been minimized.

Copy link
Owner Author

oliverfoggin commented Jun 8, 2015

Further improved

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.