Permalink
Browse files

Meta-hanoi using constexpr only

  • Loading branch information...
rom1v committed Mar 27, 2015
1 parent 0ae0c5a commit 8423f1ed83d2b83255749d9da8b28459cb7be1f7
Showing with 54 additions and 1 deletion.
  1. +1 −0 .gitignore
  2. +6 −1 Makefile
  3. +47 −0 metahanoi.cpp
@@ -1 +1,2 @@
/hanoi
/metahanoi
@@ -1,8 +1,13 @@
CXXFLAGS += -std=c++11
CXXFLAGS += -Wall -Werror

all: hanoi metahanoi

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

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

clean:
rm -f hanoi
rm -f hanoi metahanoi
@@ -0,0 +1,47 @@
#include <iostream>

using state = unsigned long long;
using tower = unsigned int;
using size = unsigned int;

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

constexpr state move(state s, tower src, tower target) {
return s % 3 == src
? s / 3 * 3 + target
: move(s / 3, src, target) * 3 + s % 3;
}

// disk 1 is the smallest, 0 does not exist (is "above" the smallest)
constexpr tower getTower(state s, size disk) {
return disk == 1
? s % 3
: getTower(s / 3, disk - 1);
}

constexpr state solve(size disks, state s, tower target) {
return disks == 0
? s
: getTower(s, disks) == target
? solve(disks - 1, s, target)
: solve(disks - 1,
move(solve(disks - 1,
s,
other(getTower(s, disks), target)),
getTower(s, disks),
target),
target);
}

std::ostream &print_state(std::ostream &os, size ndisks, state s) {
return ndisks ? print_state(os, ndisks - 1, s / 3) << s % 3 : os;
}

int main() {
constexpr int disks = 5;
constexpr state result = solve(disks, 0, 2);
print_state(std::cout, disks, result) << std::endl;
return 0;
}

0 comments on commit 8423f1e

Please sign in to comment.