Permalink
Browse files

Hanoi runtime

Classical implementation for the resolution of the Tower of Hanoi
(generalized) problem.
  • Loading branch information...
rom1v committed Mar 27, 2015
1 parent 5249cc5 commit 0ae0c5a8535d3e62890d6cfbe1210b9c89ff47cf
Showing with 64 additions and 0 deletions.
  1. +1 −0 .gitignore
  2. +8 −0 Makefile
  3. +55 −0 hanoi.cpp
@@ -0,0 +1 @@
/hanoi
@@ -0,0 +1,8 @@
CXXFLAGS += -std=c++11
CXXFLAGS += -Wall -Werror

hanoi: hanoi.cpp
$(CXX) $(CXXFLAGS) hanoi.cpp -o hanoi

clean:
rm -f hanoi
@@ -0,0 +1,55 @@
#include <iterator>
#include <iostream>
#include <vector>

class Hanoi {
using tower = unsigned int;
using size = unsigned int;

std::vector<tower> state; // disk number i is on tower state[i]

public:
Hanoi(std::initializer_list<tower> init) : state(init) {}

void solve(tower target) {
printState(); // initial state
solveRec(state.size(), target);
}

private:
void solveRec(size disks, tower target) {
if (disks == 0) {
return;
}
// the tower of the largest disk at this depth of recursion
tower &largest = state[state.size() - disks];
if (largest == target) {
// the largest disk is already on the target tower
solveRec(disks - 1, target);
} else {
// move disks above the largest to the intermediate tower
solveRec(disks - 1, other(largest, target));
// move the largest disk to the target
largest = target;
printState();
// move back the disks on the largest
solveRec(disks - 1, target);
}
}

void printState() {
std::copy(state.cbegin(), state.cend(),
std::ostream_iterator<tower>(std::cout));
std::cout << std::endl;
}

static inline tower other(tower t1, tower t2) {
return 3 - t1 - t2;
}

};

int main() {
Hanoi{ 0, 0, 0, 0, 0 }.solve(2);
return 0;
}

0 comments on commit 0ae0c5a

Please sign in to comment.