#include <vector>
#include <cstdio>
using namespace std;
#define _countof(array) (sizeof(array) / sizeof(array[0]))
typedef unsigned char uchar;
typedef struct {
uchar src, dst, work, discs;
} hanoi;
vector<uchar> pegs[3];
int hanoi_init(hanoi h)
{
if(h.src > 2) return 1;
if(h.dst > 2) return 2;
if(h.work > 2) return 3;
if(h.discs > 15) return 4;
if(h.src == h.dst || h.dst == h.work || h.work == h.src) return 5;
for(int i = (int)h.discs; i > 0; --i) pegs[h.src].push_back(i);
return 0;
}
int hanoi_stat()
{
fprintf(stdout, "Pegs\n");
for(int j = 0; j < _countof(pegs); ++j){
fprintf(stdout, " [%d]:", j);
for(vector<uchar>::iterator it=pegs[j].begin(); it != pegs[j].end(); ++it)
fprintf(stdout, " %d", (int)*it);
fprintf(stdout, "\n");
}
return 0;
}
int hanoi_move(hanoi m)
{
pegs[m.dst].push_back(pegs[m.src].back());
pegs[m.src].pop_back();
hanoi_stat();
return 0;
}
hanoi hanoi_next(hanoi h)
{
if(!h.discs) return h;
hanoi m = hanoi_next(hanoi{h.src, h.work, h.dst, (uchar)(h.discs - 1)});
if(m.discs) hanoi_move(m);
hanoi_move(h);
m = hanoi_next(hanoi{h.work, h.dst, h.src, (uchar)(h.discs - 1)});
if(m.discs) hanoi_move(m);
return hanoi{0, 0, 0, 0}; // discs = 0 for stop recursion
}
int main(int ac, char **av)
{
hanoi h = {0, 1, 2, 4};
int r = hanoi_init(h);
if(r){
fprintf(stderr, "illeagal parameter: error %d\n", r);
}else{
hanoi_stat();
hanoi_next(h);
}
return 0;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNzdGRpbz4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIF9jb3VudG9mKGFycmF5KSAoc2l6ZW9mKGFycmF5KSAvIHNpemVvZihhcnJheVswXSkpCnR5cGVkZWYgdW5zaWduZWQgY2hhciB1Y2hhcjsKdHlwZWRlZiBzdHJ1Y3QgewogIHVjaGFyIHNyYywgZHN0LCB3b3JrLCBkaXNjczsKfSBoYW5vaTsKdmVjdG9yPHVjaGFyPiBwZWdzWzNdOwoKaW50IGhhbm9pX2luaXQoaGFub2kgaCkKewogIGlmKGguc3JjID4gMikgcmV0dXJuIDE7CiAgaWYoaC5kc3QgPiAyKSByZXR1cm4gMjsKICBpZihoLndvcmsgPiAyKSByZXR1cm4gMzsKICBpZihoLmRpc2NzID4gMTUpIHJldHVybiA0OwogIGlmKGguc3JjID09IGguZHN0IHx8IGguZHN0ID09IGgud29yayB8fCBoLndvcmsgPT0gaC5zcmMpIHJldHVybiA1OwogIGZvcihpbnQgaSA9IChpbnQpaC5kaXNjczsgaSA+IDA7IC0taSkgcGVnc1toLnNyY10ucHVzaF9iYWNrKGkpOwogIHJldHVybiAwOwp9CgppbnQgaGFub2lfc3RhdCgpCnsKICBmcHJpbnRmKHN0ZG91dCwgIlBlZ3NcbiIpOwogIGZvcihpbnQgaiA9IDA7IGogPCBfY291bnRvZihwZWdzKTsgKytqKXsKICAgIGZwcmludGYoc3Rkb3V0LCAiIFslZF06Iiwgaik7CiAgICBmb3IodmVjdG9yPHVjaGFyPjo6aXRlcmF0b3IgaXQ9cGVnc1tqXS5iZWdpbigpOyBpdCAhPSBwZWdzW2pdLmVuZCgpOyArK2l0KQogICAgICBmcHJpbnRmKHN0ZG91dCwgIiAlZCIsIChpbnQpKml0KTsKICAgIGZwcmludGYoc3Rkb3V0LCAiXG4iKTsKICB9CiAgcmV0dXJuIDA7Cn0KCmludCBoYW5vaV9tb3ZlKGhhbm9pIG0pCnsKICBwZWdzW20uZHN0XS5wdXNoX2JhY2socGVnc1ttLnNyY10uYmFjaygpKTsKICBwZWdzW20uc3JjXS5wb3BfYmFjaygpOwogIGhhbm9pX3N0YXQoKTsKICByZXR1cm4gMDsKfQoKaGFub2kgaGFub2lfbmV4dChoYW5vaSBoKQp7CiAgaWYoIWguZGlzY3MpIHJldHVybiBoOwogIGhhbm9pIG0gPSBoYW5vaV9uZXh0KGhhbm9pe2guc3JjLCBoLndvcmssIGguZHN0LCAodWNoYXIpKGguZGlzY3MgLSAxKX0pOwogIGlmKG0uZGlzY3MpIGhhbm9pX21vdmUobSk7CiAgaGFub2lfbW92ZShoKTsKICBtID0gaGFub2lfbmV4dChoYW5vaXtoLndvcmssIGguZHN0LCBoLnNyYywgKHVjaGFyKShoLmRpc2NzIC0gMSl9KTsKICBpZihtLmRpc2NzKSBoYW5vaV9tb3ZlKG0pOwogIHJldHVybiBoYW5vaXswLCAwLCAwLCAwfTsgLy8gZGlzY3MgPSAwIGZvciBzdG9wIHJlY3Vyc2lvbgp9CgppbnQgbWFpbihpbnQgYWMsIGNoYXIgKiphdikKewogIGhhbm9pIGggPSB7MCwgMSwgMiwgNH07CiAgaW50IHIgPSBoYW5vaV9pbml0KGgpOwogIGlmKHIpewogICAgZnByaW50ZihzdGRlcnIsICJpbGxlYWdhbCBwYXJhbWV0ZXI6IGVycm9yICVkXG4iLCByKTsKICB9ZWxzZXsKICAgIGhhbm9pX3N0YXQoKTsKICAgIGhhbm9pX25leHQoaCk7CiAgfQogIHJldHVybiAwOwp9