You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

87 lines
1.9 KiB

#include <iostream>
#include <vector>
#include <limits>
struct hanoi {
uint n; // number of discs
std::vector<uint> towers[3]; // radii of discs
// init: all discs on towers[0]
hanoi(uint n) : n(n) {
for (auto &tower : towers)
tower.reserve(n);
for (uint i = 0; i < n; ++i)
towers[0].push_back(n - i);
}
// display all three towers
void display() const {
for (uint i = n / 2; i != -1U; --i) {
for (const auto &tower : towers) {
const uint topr = (tower.size() > 2*i + 1) ? tower[2*i + 1] : 0;
const uint botr = (tower.size() > 2*i) ? tower[2*i] : 0;
for (uint j = botr; j < n; ++j)
std::cout << ' ';
for (uint j = topr; j < botr; ++j)
std::cout << "";
for (uint j = 0; j < topr; ++j)
std::cout << "";
std::cout << "";
for (uint j = 0; j < topr; ++j)
std::cout << "";
for (uint j = topr; j < botr; ++j)
std::cout << "";
for (uint j = botr; j < n; ++j)
std::cout << ' ';
std::cout << ' ';
}
std::cout << '\n';
}
}
// returns the tower which isn't a or b
static uint third(uint a, uint b) {
return a ^ b ^ 3;
}
// moves topmost disc
void move1(uint from, uint to) {
towers[to].push_back(towers[from].back());
towers[from].pop_back();
display();
std::cout << '\n';
}
// moves top `depth` discs recursively
void move(uint depth, uint from, uint to) {
if (depth == 1)
return move1(from, to);
uint tmp = third(from, to);
move(depth - 1, from, tmp);
move1(from, to);
move(depth - 1, tmp, to);
}
void solve() {
display();
move(n, 0, 2);
}
};
int main(int argc, char *argv[]) {
if (argc < 2) {
std::cerr << "You need to specify the disc count!\n";
return 1;
}
const auto height = std::strtoul(argv[1], nullptr, 10);
if (height == 0 || height == std::numeric_limits<decltype(height)>::max()) {
std::cerr << "Invalid disc count!\n";
return 1;
}
hanoi(height).solve();
return 0;
}