Solving the Towers of Hanoi at compile-time

Question

I am trying to solve the Towers of Hanoi at compile-time, but I have discovered a problem:

template<int src, int dst>
struct move_disc
{
    // member access will print src and dst
};

template<int n, int src, int tmp, int dst>
struct hanoi
{
    hanoi<n-1, src, dst, tmp> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst> after;
};

template<int src, int tmp, int dst>
struct hanoi<0, src, tmp, dst>
{
    // recursive base case
};

hanoi<3, 1, 2, 3> go;

Unfortunately, the above meta program only prints six moves instead of seven:

prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<3, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 1>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 3>’

The final move from 1 to 3 is missing. Why is that? Can the problem be solved?

Note that for `hanoi<4, 1, 2, 3> go;` it only prints 9 moves instead of 15, for `hanoi<5, 1, 2, 3> go;` it only prints 12 moves instead of 31, ... — gx_, Nov 08 '13 at 18:36

gx_ · Accepted Answer · 2013-11-08T19:51:51.923

I think that's because hanoi<1, 1, 2, 3> has already been instantiated (giving the first error) and is not instantiated again when later "encountered" during template instantiation.

[Edit: To make it maybe clearer, here's a "graph" of recursive template instantiations (with errors):

hanoi<3, 1, 2, 3>:
- 1: hanoi<2, 1, 3, 2>:
  - 1.1: hanoi<1, 1, 2, 3>:
    - 1.1.1: hanoi<0, 1, 3, 2>.
    - (move_disc<1, 3>)
    - 1.1.2: hanoi<0, 2, 1, 3>.
  - (move_disc<1, 2>)
  - 1.2: hanoi<1, 3, 1, 2>:
    - 1.2.1: hanoi<0, 3, 2, 1>.
    - (move_disc<3, 2>)
    - 1.2.2: hanoi<0, 1, 3, 2>.
- (move_disc<1, 3>)
- 2: hanoi<2, 2, 1, 3>:
  - 2.1: hanoi<1, 2, 3, 1>:
    - 2.1.1: hanoi<0, 2, 1, 3>.
    - (move_disc<2, 1>)
    - 2.1.2: hanoi<0, 3, 2, 1>.
  - (move_disc<2, 3>)
  - 2.2: hanoi<1, 1, 2, 3>: already instantiated at 1.1 (move_disc<1, 3> error not repeated).

-- end edit.]

A "fix" I can think of is to make every specialization unique, e.g. by adding an "id" template parameter (and generate unique new values during recursive instantiation):

template<int n, int src, int tmp, int dst, int id>
struct hanoi
{
    hanoi<n-1, src, dst, tmp, id*2> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst, id*2+1> after;
};

template<int src, int tmp, int dst, int id>
struct hanoi<0, src, tmp, dst, id>
{
    // recursive base case
};

hanoi<3, 1, 2, 3, 1> go;

Live: http://ideone.com/0lQaXs

Note: Of course you can add an indirection (or a default value) to avoid having to specify the initial `1` (`0` won't do) for `id` when defining `go`. Also, that "fixes" the problem for values of `n` greater than `3` too. — gx_, Nov 08 '13 at 18:46
Also it's worth noting that this simple id generation limits `n` to `30` or so (integer overflow of `id`). One can go up to `62` or `63` with a 64-bits `unsigned long long` but it's still kind of limited... — gx_, Nov 08 '13 at 21:25
That's fine, I wasn't planning on going higher than 9 or something. Thanks very much for your insight :) — fredoverflow, Nov 09 '13 at 09:27

Benji Mizrahi · Answer 2 · 2014-12-01T11:30:19.040

I am not directly answering your question but, this would be my version:

#include <type_traits>

using namespace std;

template <typename T> class TD;

struct NullType {};

template <int N, typename S>
struct Stack {
    static const int Head = N;
    typedef S Tail;
};

#define STACK_0() NullType
#define STACK_1(D1) Stack<D1, NullType>
#define STACK_2(D1, D2) Stack<D1, STACK_1(D2)>
#define STACK_3(D1, D2, D3) Stack<D1, STACK_2(D2, D3)>
#define STACK_4(D1, D2, D3, D4) Stack<D1, STACK_3(D2, D3, D4)>

template <typename S>
struct Pop;

template <int N, typename R>
struct Pop<Stack<N, R>> {
    typedef Stack<N, typename Pop<R>::result> result;
};

template<int N>
struct Pop<Stack<N, NullType>> {
    typedef NullType result;
};

template <typename S>
struct Top;

template <int N, typename R>
struct Top<Stack<N, R>> {
    static const int result = Top<R>::result;
};

template <int N>
struct Top<Stack<N, NullType>> {
    static const int result = N;
};

template <typename S, int D>
struct Push;

template <int N, typename S, int D>
struct Push<Stack<N, S>, D> {
    typedef Stack<N, typename Push<S, D>::result> result;
};

template <int M>
struct Push<NullType, M> {
    typedef Stack<M, NullType> result;
};

template <typename S>
struct SizeOf;

template <int N, typename R>
struct SizeOf<Stack<N, R>> {
    static const int value = SizeOf<R>::value + 1;
};

template <>
struct SizeOf<NullType> {
    static const int value = 0;
};

template <typename S1, typename S2, typename S3>
struct Hanoi {
    typedef S1 Stack1;
    typedef S2 Stack2;
    typedef S3 Stack3;

    template <int I, int J, int unused=0>
    struct MoveDisc;

    template <int unused>
    struct MoveDisc<1, 2, unused> {
        typedef Hanoi<
            typename Pop<Stack1>::result,
            typename Push<Stack2, Top<Stack1>::result>::result,
            Stack3
        > result;
    };

    template <int unused>
    struct MoveDisc<2, 1, unused> {
        typedef Hanoi<
            typename Push<Stack1, Top<Stack2>::result>::result,
            typename Pop<Stack2>::result,
            Stack3
        > result;
    };

    template <int unused>
    struct MoveDisc<1, 3, unused> {
        typedef Hanoi<
            typename Pop<Stack1>::result,
            Stack2,
            typename Push<Stack3, Top<Stack1>::result>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<3, 1, unused> {
        typedef Hanoi<
            typename Push<Stack1, Top<Stack3>::result>::result,
            Stack2,
            typename Pop<Stack3>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<2, 3, unused> {
        typedef Hanoi<
            Stack1,
            typename Pop<Stack2>::result,
            typename Push<Stack3, Top<Stack2>::result>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<3, 2, unused> {
        typedef Hanoi<
            Stack1,
            typename Push<Stack2, Top<Stack3>::result>::result,
            typename Pop<Stack3>::result
        > result;
    };
};

static_assert(
    is_same<
        Pop<STACK_1(1)>::result,
        NullType
    >::value, "Pop<> not working."
);

static_assert(Top<STACK_2(2, 1)>::result == 1, "Top<> not working.");

static_assert(
    is_same<
        Push<STACK_1(2), 1>::result,
        STACK_2(2, 1)
    >::value, "Push<> not working."
);

static_assert(
    SizeOf<STACK_4(4, 3, 2, 1)>::value == 4, "SizeOf<> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_4(4, 3, 2, 1),
            STACK_0(),
            STACK_0()>::MoveDisc<1,2>::result,
        Hanoi<
            STACK_3(4, 3, 2),
            STACK_1(1),
            STACK_0()>
    >::value, "MoveDisc<1,2> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_3(4, 3, 2),
            STACK_1(1),
            STACK_0()>::MoveDisc<2,1>::result,
        Hanoi<
            STACK_4(4, 3, 2, 1),
            STACK_0(),
            STACK_0()>
    >::value, "MoveDisc<2,1> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_1(4),
            STACK_0(),
            STACK_0()>::MoveDisc<1,3>::result,
        Hanoi<
            STACK_0(),
            STACK_0(),
            STACK_1(4)>
    >::value, "MoveDisc<1,3> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_2(3, 2),
            STACK_0(),
            STACK_2(4, 1)>::MoveDisc<3,1>::result,
        Hanoi<
            STACK_3(3, 2, 1),
            STACK_0(),
            STACK_1(4)>
    >::value, "MoveDisc<3,1> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_1(1),
            STACK_2(3, 2),
            STACK_1(4)>::MoveDisc<2,3>::result,
        Hanoi<
            STACK_1(1),
            STACK_1(3),
            STACK_2(4, 2)>
    >::value, "MoveDisc<2,3> not working."
);

template <typename H, int D, int F, int T, int V>
struct Solve {
    typedef typename Solve<
        typename Solve<H, D-1, F, V, T>::result::template MoveDisc<F, T>::result, D-1, V, T, F
    >::result result;
};

template <typename H, int F, int T, int V>
struct Solve<H, 1, F, T, V> {
    typedef typename H::template MoveDisc<F, T>::result result;
};

template <typename H>
struct Solution {
    typedef typename Solve<H, SizeOf<typename H::Stack1>::value, 1, 3, 2>::result result;
};

static_assert(
    is_same<
        Solution<
            Hanoi<
                STACK_4(4, 3, 2, 1),
                STACK_0(),
                STACK_0()
            >
        >::result,
        Hanoi<
            STACK_0(),
            STACK_0(),
            STACK_4(4, 3, 2, 1)
        >
    >::value, "Solution<> is not working."
);

int main() {

}

Stack class templates are actually TypeList's from Modern C++ Design book by Andrei Alexandrescu

score 0 · Answer 3 · answered Nov 08 '13 at 19:39

0

Your program is correct but you are relying on compiler error messages (which is implementation defined) in in your case it doesn't print the error a second time. But in real code TMP has to do something which results in runtime behaviour. If you only output (with std::cout) src and dst in move_discconstrcutor and makemove_disc a member of hanoi instead forcing a compile time error everything is ok.

answered Nov 08 '13 at 19:39

Jan Herrmann

2,717
17
21

1

Actually the [first known meta-program](http://www.erwin-unruh.de/primorig.html) (by Erwin Unruh) used compilation error messages too (see also [this](http://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming#History_of_TMP) that links to [this](http://aszt.inf.elte.hu/~gsd/halado_cpp/ch06s04.html#Static-metaprogramming)). But it's indeed implementation-dependent (for example MSVC prints each unique error only once, so here it only prints five moves, even after the "fix" from my answer, which must then be extended so that `move_disc` also takes an `id` parameter). – gx_ Nov 08 '13 at 21:19
1

@gx_ Yes I know this. But TMP is not an end in itself. Beside `static_assert` its goal is not to trigger *any* compiler error but to make better programms. The example from Erwin Unruh demonstrated TMP is possible. The error messages shows that the compiler solved the problem. But today it isn't enough, we have to solve problems at compile time which result in better runtime codem which I do in my example. But nevertheless if somebody has deal with effect of memoization in TMP Appendix C of "C++ Template Metaprogramming" deals with these aspects, too. – Jan Herrmann Nov 08 '13 at 21:59

Solving the Towers of Hanoi at compile-time

3 Answers3