Решение башен Ханоя во время компиляции

Question

Решение башен Ханоя во время компиляции

Я пытаюсь решить Towers of Hanoi во время компиляции, но я обнаружил проблему:

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;

К несчастью, вышеуказанная метапрограмма печатает только шесть ходов вместо семи:

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>’

Последний ход с 1 по 3 отсутствует. Это почему? Можно ли решить проблему?

11

c++template-meta-programming templates towers-of-hanoi

Решение

Другие решения

Я не отвечаю прямо на ваш вопрос, но это будет моя версия:

#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() {

}

Шаблоны стековых классов на самом деле являются TypeList из книги Modern C ++ Design Андрея Александреску.

1

Ваша программа верна, но вы полагаетесь на сообщения об ошибках компилятора (которые определяются реализацией), поскольку в вашем случае она не выводит ошибку во второй раз. Но в реальном коде TMP должен что-то делать, что приводит к поведению во время выполнения. Если вы только выводите (с std::cout) src а также dst в move_discсоздать и сделатьmove_disc член hanoi вместо того, чтобы заставить ошибку времени компиляции все Хорошо.

0

Источник

Accepted Answer

Я думаю это потому что hanoi<1, 1, 2, 3> уже был создан (дает первую ошибку) и не создается снова, когда позже «встречается» во время создания шаблона.

[Редактировать: чтобы сделать это, возможно, более понятным, вот «график» рекурсивных реализаций шаблона (с ошибками):

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>: уже создан на уровне 1.1 (move_disc<1, 3> ошибка не повторяется).

— конец редактирования.]

«Исправление», о котором я могу подумать, — сделать каждую специализацию уникальной, например, добавив параметр шаблона «id» (и сгенерировать уникальные новые значения во время рекурсивной реализации):

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;

Жить: http://ideone.com/0lQaXs

7