Skip to content

Instantly share code, notes, and snippets.

@jcmvbkbc jcmvbkbc/h.c
Last active Dec 13, 2018

Embed
What would you like to do?
Hanoi towers with unsorted source.
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
typedef std::deque<int> stack;
void move_top1(stack& from, stack& to, stack& spare);
int top(const stack& o)
{
if (o.empty())
return INT_MAX;
else
return o.front();
}
void dump(const stack& o)
{
printf("%p:\n", &o);
for (stack::const_iterator it = o.begin(); it != o.end(); ++it)
printf("\t%d\n", *it);
}
void move(stack& from, stack& to)
{
printf("%d: %p -> %p\n", from.front(), &from, &to);
assert(top(from) < top(to));
to.push_front(from.front());
from.pop_front();
}
void move_top(int cut, stack& from, stack& to, stack& spare)
{
int sz = -1;
for (stack::iterator it = from.begin(); it != from.end() && *it < cut; ++it)
sz = *it;
if (sz == -1)
return;
move_top(sz, from, spare, to);
move_top1(from, to, spare);
move_top(sz, spare, to, from);
}
void move_top1(stack& from, stack& to, stack& spare)
{
if (from.empty())
return;
if (top(from) < top(to))
move(from, to);
else {
move_top(top(from), to, spare, from);
move(from, to);
}
}
void move_all(stack& from, stack& to, stack& spare)
{
while (!from.empty())
move_top1(from, to, spare);
if (!spare.empty())
move_top(spare.back() + 1, spare, to, from);
}
int main()
{
const int N = 6;
int o[N];
int s[N];
for (int i = 0; i < N; ++i)
o[i] = s[i] = i + 1;
do {
stack from(s, s + N), to, spare;
printf("==================================\n");
move_all(from, to, spare);
assert(from.empty());
assert(spare.empty());
assert(std::equal(o, o + N, to.begin()));
dump(from);
dump(to);
dump(spare);
} while (std::next_permutation(s, s + N));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.