ChunMinChang
9/18/2017 - 2:54 AM

Tower of Hanoi

Tower of Hanoi #DPfCI #dynamic_programming #recursion

``````// Compile by \$ g++ hanoi.cpp --std=c++11
//
// The standard `Tower of Hanoi` has 3 pegs and a number of disks
// of different sizes, which can slide onto any peg.
// The objective of the puzzle is to move entire stack from one peg to
// another peg, obeying the following simple rules:
//   1. The disks need to keep in ascending order of size on the peg any time.
//      That is, no disk can be placed on top of a smaller disk.
//   2. Only one disk can be moved at a time.
//   3. Each move consists of taking the upper disk from one of the stacks
//      and placing it on top of another stack.
//
// For example, if we have 5 disks, then we need to move the stack from
// source peg to target peg, while we can use spare peg as our intermediate
// storage of the disks.
//
//              |                      |
//   ^         =|=                     |                     =|=
//   |       ===|===                   |                   = =|= =
// n |     =====|=====                 |                 = = =|= = =
//   |   =======|=======               |               = = = =|= = = =
//   v =========|=========             |             = = = = =|= = = = =
// -------------+----------------------+----------------------+--------------
//        Source Peg              Spare Peg             Target Peg
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

#undef RECURSION
#undef MEMOIZATION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define MEMOIZATION 2
#define DYNAMIC_PROGRAMMING 3
// #define RUN RECURSION
#define RUN MEMOIZATION
// #define RUN DYNAMIC_PROGRAMMING

typedef unsigned int LAYER;
enum PEG
{
SOURCE,
SPARE,
TARGET,
};
std::ostream & operator<<(std::ostream & str, PEG const & p) {
std::string name[] = { "Source", "Spare", "Target" };
str << name[p];
return str;
}

class Logger
{
public:
struct Log
{
LAYER layer;
PEG from;
PEG via;
PEG to;

Log(LAYER l, PEG f, PEG v, PEG t)
: layer(l)
, from(f)
, via(v)
, to(t)
{
}

Log(const Log &other)
: layer(other.layer)
, from(other.from)
, via(other.via)
, to(other.to)
{
}
};

Logger() {}
~Logger() {}

void Print()
{
for (Log l: tracks) {
std::cout << "Move the " << l.layer << \
"th layer from " << l.from << \
" to " << l.to << std::endl;
}
}

{
tracks.push_back(l);
}

void Append(std::vector<Log> logs)
{
for (unsigned int i = 0 ; i < logs.size() ; ++i) {
tracks.push_back(logs[i]);
}
}

unsigned int Records()
{
return tracks.size();
}

std::vector<Log> GetMoves(LAYER n, PEG src, PEG spa, PEG tar)
{
bool found = false;
unsigned int top;
for (unsigned int i = 0 ; i < tracks.size() ; ++i) {
if (tracks[i].layer == n &&
tracks[i].from == src &&
tracks[i].via == spa &&
tracks[i].to == tar) {
top = i;
found = true;
break;
}
}
assert(found);

unsigned int d = (pow(2, n) - 2) / 2;
unsigned int first = top - d;
unsigned int end = top + d;
assert(tracks[first].layer == 1 && tracks[first].from == src);
assert(tracks[end].layer == 1 && tracks[end].to == tar);

std::vector<Log> logs;
for (unsigned int i = first ; i <= end ; ++i) {
logs.push_back(Log(tracks[i]));
}

return logs;
}

private:
std::vector<Log> tracks;
};

Logger logger;

#if RUN == RECURSION

// Move n disks from source peg to target peg via spare peg.
unsigned int Move(LAYER n, PEG source, PEG spare, PEG target)
{
if (!n) {
return 0;
}

unsigned int moves = 0;

// Move the first n-1 disks from source to spare via target.
moves += Move(n - 1, source, target, spare);

// Move the bottommost layer from source to target directly.
moves += 1;

// Move the first n-1 disks from spare to target via source.
moves += Move(n - 1, spare, source, target);

return moves;
}

#elif RUN == MEMOIZATION

// Move n disks from peg s to peg t via peg v can be represented
// by `(n, x)`, where `x` = f(s, t) and f(a, b) will return a unique value.
// For example, Move 4 disks from source(0) to target(2) via spare(1) can be
// represented by (4, f(0, 2)).
//
// We can define f(a, b) = `ab` (base 3) = 3*a + b. (Ternary number system)
// For example, moving disks from peg 0 to peg 2 is f(0, 2) = `02`(base 3) = 2,
// moving disks from peg 2 to peg 1 = `21`(base 3) = 7.
//
// As a result, we can use an 2d array(n, f(s, t)) to record:
// moving n disks from peg s to peg t.
// Since s != t, we only have 3*2 possibilites for f(s, t) here.
unsigned int Col(PEG a, PEG b)
{
assert(a != b);
unsigned int k = 3 * a + b;
unsigned int map[9] = {
static_cast<unsigned int>(-1), // `00` = 0, 0(Source) to 0(Source) is not allowed.
0,  // `01` = 1, 0(Source) to 1(Spare)
1,  // `02` = 2, 0(Source) to 2(Target)
2,  // `10` = 3, 1(Spare) to 0(Source)
static_cast<unsigned int>(-1), // `11` = 4, 1(Spare) to 1(Spare) is not allowed.
3,  // `12` = 5, 1(Spare) to 2(Target)
4,  // `20` = 6, 2(Target) to 0(Source)
5,  // `21` = 7, 2(Target) to 1(Spare)
static_cast<unsigned int>(-1), // `22` = 8, 2(Target) to 2(Target) is not allowed.
};
assert(map[k] != static_cast<unsigned int>(-1));
return map[k];
}

unsigned int MoveHelper(LAYER n, PEG source, PEG spare, PEG target,
std::vector< std::vector<unsigned int> >& memo)
{
if (!n) {
return 0;
}

unsigned int c = Col(source, target);
unsigned int r = n - 1;

if (!memo[r][c]) {
unsigned int moves = 0;

// Move the first n-1 disks from source to spare via target.
moves += MoveHelper(n - 1, source, target, spare, memo);

// Move the bottommost layer from source to target directly.
moves += 1;

// Move the first n-1 disks from spare to target via source.
moves += MoveHelper(n - 1, spare, source, target, memo);

memo[r][c] = moves;
} else {
logger.Append(logger.GetMoves(n, source, spare, target));
}

return memo[r][c];
}

unsigned int Move(LAYER n, PEG source, PEG spare, PEG target)
{
assert(n);
const unsigned int cols = 6;
std::vector<std::vector<unsigned int>>
memo(n, std::vector<unsigned int>(cols, 0));

return MoveHelper(n, source, spare, target, memo);
}

#else // RUN == DYNAMIC_PROGRAMMING

assert(false);

#endif

int main()
{
LAYER layers = 10;
unsigned int total = Move(layers, SOURCE, SPARE, TARGET);
std::cout << "records: " << logger.Records() << ", total: " << total << std::endl;
assert(logger.Records() == total);
logger.Print();
return 0;
}

// The `logger` will be destroyed after `main` has been executed.``````
``````// Compile by \$ g++ hanoi.cpp --std=c++11
//
// The standard `Tower of Hanoi` has 3 pegs and a number of disks
// of different sizes, which can slide onto any peg.
// The objective of the puzzle is to move entire stack from one peg to
// another peg, obeying the following simple rules:
//   1. The disks need to keep in ascending order of size on the peg any time.
//      That is, no disk can be placed on top of a smaller disk.
//   2. Only one disk can be moved at a time.
//   3. Each move consists of taking the upper disk from one of the stacks
//      and placing it on top of another stack.
//
// For example, if we have 5 disks, then we need to move the stack from
// source peg to target peg, while we can use spare peg as our intermediate
// storage of the disks.
//
//              |                      |
//   ^         =|=                     |                     =|=
//   |       ===|===                   |                   = =|= =
// n |     =====|=====                 |                 = = =|= = =
//   |   =======|=======               |               = = = =|= = = =
//   v =========|=========             |             = = = = =|= = = = =
// -------------+----------------------+----------------------+--------------
//        Source Peg              Spare Peg             Target Peg
//
//
// Move n disks from peg A to peg B via peg C =
//   1) Move disk from peg A to peg B directly, if n = 1
//   2) Move n-1 disks from peg A to peg C via peg B then
//      move the nth disk from peg A to peg B directly then
//      move n-1 disks from peg C to peg B via peg A
// Thus, if M(n, A, B, C) is defined as the total steps
// to move n disks from peg A to peg B via peg C, then
// M(n, A, B, C) = M(n-1, A, C, B) + 1 + M(n-1, C, B, A)
//
// There are same-type subproblems in the original problem,
// so it could be solved recursively.
// Moreover, there are overlapping substructures, so it could be
// solved by dynamic programming!
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

#undef RECURSION
#undef MEMOIZATION
#undef DYNAMIC_PROGRAMMING
#undef RUN

#define RECURSION 1
#define MEMOIZATION 2
#define DYNAMIC_PROGRAMMING 3
// #define RUN RECURSION
// #define RUN MEMOIZATION
#define RUN DYNAMIC_PROGRAMMING

enum PEG
{
SOURCE,
SPARE,
TARGET,
};

#if RUN == RECURSION

// Move n disks from source peg to target peg via spare peg.
unsigned int Move(unsigned int n, PEG source, PEG spare, PEG target)
{
if (!n) {
return 0;
}

unsigned int moves = 0;

// Move the first n-1 disks from source to spare via target.
moves += Move(n - 1, source, target, spare);
// Move the bottommost layer from source to target directly.
moves += 1;
// Move the first n-1 disks from spare to target via source.
moves += Move(n - 1, spare, source, target);

return moves;
}

#elif RUN == MEMOIZATION

// Move n disks from peg s to peg t via peg v can be represented
// by `(n, x)`, where `x` = f(s, t) and f(a, b) will return a unique value.
// For example, Move 4 disks from source(0) to target(2) via spare(1) can be
// represented by (4, f(0, 2)).
//
// We can define f(a, b) = `ab` (base 3) = 3*a + b. (Ternary number system)
// For example, moving disks from peg 0 to peg 2 is f(0, 2) = `02`(base 3) = 2,
// moving disks from peg 2 to peg 1 = `21`(base 3) = 7.
//
// As a result, we can use an 2d array(n, f(s, t)) to record:
// moving n disks from peg s to peg t.
// Since s != t, we only have 3*2 possibilites for f(s, t) here.
unsigned int Col(PEG a, PEG b)
{
assert(a != b);
unsigned int k = 3 * a + b;
int map[9] = {
-1, // `00` = 0, 0(Source) to 0(Source) is not allowed.
0,  // `01` = 1, 0(Source) to 1(Spare)
1,  // `02` = 2, 0(Source) to 2(Target)
2,  // `10` = 3, 1(Spare) to 0(Source)
-1, // `11` = 4, 1(Spare) to 1(Spare) is not allowed.
3,  // `12` = 5, 1(Spare) to 2(Target)
4,  // `20` = 6, 2(Target) to 0(Source)
5,  // `21` = 7, 2(Target) to 1(Spare)
-1, // `22` = 8, 2(Target) to 2(Target) is not allowed.
};
assert(map[k] != -1);
return map[k];
}

unsigned int MoveWithMemo(unsigned int n, PEG source, PEG spare, PEG target,
std::vector< std::vector<unsigned int> >& memo)
{
if (!n) {
return 0;
}

unsigned int c = Col(source, target);
unsigned int r = n - 1;

if (!memo[r][c]) {
unsigned int moves = 0;

// Move the first n-1 disks from source to spare via target.
moves += MoveWithMemo(n - 1, source, target, spare, memo);

// Move the bottommost layer from source to target directly.
moves += 1;

// Move the first n-1 disks from spare to target via source.
moves += MoveWithMemo(n - 1, spare, source, target, memo);

memo[r][c] = moves;
}

return memo[r][c];
}

unsigned int Move(unsigned int n, PEG source, PEG spare, PEG target)
{
assert(n);
const unsigned int cols = 6;
std::vector<std::vector<unsigned int>>
memo(n, std::vector<unsigned int>(cols, 0));

return MoveWithMemo(n, source, spare, target, memo);
}

#else // RUN == DYNAMIC_PROGRAMMING

// Move n disks from peg s to peg t via peg v can be represented
// by `(n, x)`, where `x` = f(s, t) and f(a, b) will return a unique value.
// For example, Move 4 disks from source(0) to target(2) via spare(1) can be
// represented by (4, f(0, 2)).
//
// If we define f(a, b) as
//   from Source to Spare via Target: f(0, 1) = 0
//   from Source to Target via Spare: f(0, 2) = 1
//   from Spare to Source via Target: f(1, 0) = 2
//   from Spare to Target via Source: f(1, 2) = 3
//   from Target to Source via Spare: f(2, 0) = 4
//   from Target to Spare via Source: f(2, 1) = 5
// then we can use a table to record all the moves like:
//
// From  0   0   1   1   2   2
// To    1   2   0   2   0   1
//     | 0 | 1 | 2 | 3 | 4 | 5
//   --+---+---+---+---+---+---
//   0 | 1   1   1   1   1   1   <- Move 1 disk
//   1 | 3   3   3   3   3   3   <- Move 2 disks
//   2 | .   .   .   .   .   .   <- Move ...
//   3 | .   .   .   .   .   .
//   . | .   .   .   .   .   .
//   . | .   .   .   .   .   .
// n-1 | .   .   .   .   .   .   <- Move n disks
//
// where table[d][f(x, y)] is defined as:
//   to move `d-1` disks from x to y via z,
//   and x, y, z are respectively and arbitrarily mapped to 0, 1, 2.
//
// As a result, we can calculate table[n-1][f(a, b)] =
//   table[n-2][f(a, c)] + 1 + table[n-2][f(c, b)]
//
// Since moving n disks from a to b via c is same as
//   moving n-1 disks from a to c via b then
//   moving nth disk from a to b directly then
//   moving n-1 disks from c to b via a.
const unsigned int POSSIBILITIES = 6;

typedef struct
{
PEG from;
PEG to;
PEG via;
} Movement;

Movement ToMovement(unsigned int m)
{
assert(m < POSSIBILITIES);
Movement map[POSSIBILITIES] = {
{ SOURCE, SPARE, TARGET },
{ SOURCE, TARGET, SPARE },
{ SPARE, SOURCE, TARGET },
{ SPARE, TARGET, SOURCE },
{ TARGET, SOURCE, SPARE },
{ TARGET, SPARE, SOURCE }
};
return map[m];
}

unsigned int ToCol(PEG from, PEG to)
{
assert(from != to);
unsigned int k = 3 * from + to;
int map[9] = {
-1, // `00` = 0, 0(Source) to 0(Source) is not allowed.
0,  // `01` = 1, 0(Source) to 1(Spare)
1,  // `02` = 2, 0(Source) to 2(Target)
2,  // `10` = 3, 1(Spare) to 0(Source)
-1, // `11` = 4, 1(Spare) to 1(Spare) is not allowed.
3,  // `12` = 5, 1(Spare) to 2(Target)
4,  // `20` = 6, 2(Target) to 0(Source)
5,  // `21` = 7, 2(Target) to 1(Spare)
-1, // `22` = 8, 2(Target) to 2(Target) is not allowed.
};
assert(map[k] != -1);
return map[k];
}

unsigned int Move(unsigned int n, PEG source, PEG spare, PEG target)
{
assert(n);
std::vector<std::vector<unsigned int>>
moves(n, std::vector<unsigned int>(POSSIBILITIES, 0));

// When there is one disk on the peg, it needs only 1 move.
// Note that i = l - 1, where l is the number of disks.
for (unsigned int i = 0 ; i < moves[0].size() ; ++i) {
moves[0][i] = 1;
}

for (unsigned int i = 1 ; i < moves.size() ; ++i) { // From 2, 3, ..., to n layers.
for (unsigned int j = 0 ; j < moves[i].size() ; ++j) { // For all moves.
Movement m = ToMovement(j);
// Move `i+1` disks from `m.from` to `m.to` via `m.via` =
// Move `i` disks from `m.from` to `m.via` via `m.to` +
// Move `i+1`th disk from `m.from` to `m.to` directly +
// Move `i` disks from `m.via` to `m.to` via `m.from`
moves[i][j] = moves[i-1][ToCol(m.from, m.via)] + 1 +
moves[i-1][ToCol(m.via, m.to)];
// Actually, We only need to save two pegs. The other peg
// can be calculated by 0+1+2-pegA-pegB,
// e.g., m.via = 3 - m.from - m.to.
}
}

return moves[n-1][ToCol(source, target)];
}

#endif

int main()
{
unsigned int layers = 10;
unsigned int total = Move(layers, SOURCE, SPARE, TARGET);
std::cout << "total: " << total << std::endl;
return 0;
}
``````