# Thread: towers of Hanoi variation

1. ## towers of Hanoi variation

Does the following seem right? (problem description in comments) What concerns me is that the number of instructions gets out of hand horribly fast--so either that's part of the learning experience for the exercise or else I'm not seeing a better solution ... Code:
```/** @file
*	cf. Sedgewick-Wayne, Intro to Programming in Java, p. 283, ex. 2.3.25:
*	There are 2n discs of increasing size stored on 3 poles.
*	Initially all of the discs with odd size (1, 3, ... 2n-1) are piled
*	on the left pole from top to bottom in increasing order of size;
*	all of the discs with even size (2, 4, ..., 2n) are piled on the right
*	pole. This program should provide instructions for moving the odd
*	discs to the right pole and the even discs to the left pole,
*	obeying the same rules as for towers of Hanoi.
*
*	My instructions (as in Sedgewick-Wayne) will view the towers as
*	a cyclic group, where tower 1 is to the right of tower 3
*	@author Marshall Farrier
*	@date 6/7/10
*/

#include <iostream>
using std::cout;
using std::endl;

/**
class towers of Hanoi
@param n
height
@param move_to_left
true iff instructions are to move the tower
to the left
*/
void move_tower(int n, bool move_left);

/**
recursive function giving instructions for interleaving
both towers into 1 correct tower on the empty peg
function makes use of move_tower() function
@param n
height of each tower
note that this is for a total of 2n discs
@param odd_on_right
true iff odd tower is to the right of the even tower
(as is the case in the starting set up with odd on peg 1 and
even on peg 3)
*/
void interleave(int n, bool odd_on_right);

/**
once the 2 towers are consolidated
this function gives instructions for
distributing the odd and even disks
from a single tower
@param n
tower height
@param odd_on_right
whether the instructions should distribute the disks
with the odd disks on the right side (true)
or left side (false) of the originial tower
*/
void distribute(int n, bool odd_on_right);

/**
combines the above functions into instructions
for swapping 2 towers
*/
void swap_towers(int n, bool odd_on_right = true);

int main()
{
using std::cin;
int height;

cout << "Enter height for each tower: ";
cin >> height;
//distribute(2 * height, true); // distributes odd tower to right of orig
// interleave(height, true);
swap_towers(height, false);
return 0;
}

void move_tower(int n, bool move_left)
{
// base case: n == 0
if (!n) return;
move_tower(n - 1, !move_left);
cout << n;
if (move_left) cout << " left\n";
else cout << " right\n";
move_tower(n - 1, !move_left);
}

void interleave(int n, bool odd_on_right)
{
if (!n) return;
// interleave for respective tower heights using n - 1
interleave(n - 1, odd_on_right);
// move the tower just created onto the base disc of the odd tower
move_tower(2 * n - 2, odd_on_right);
// move disc 2n to the empty peg
cout << 2 * n;
if (odd_on_right) cout << " left\n";
else cout << " right\n";
// move the tower atop the biggest odd disk back to the empty peg
move_tower(2 * n - 1, !odd_on_right);
}

void distribute(int n, bool odd_on_right)
{
// <= 0 at least prevents infinite loop in case of incorrect input for n (which is assumed to be even)
if (n <= 0) return;
// move the tower, except for bottom even disc, to
// where we want the bottom odd disk
// i.e., if odd_on_right (we want odd tower on the right)
// move_tower should also have its move_left variable set to false
move_tower(n - 1, !odd_on_right);
// move the base disk onto the empty peg:
cout << n;
if (odd_on_right) cout << " left\n";
else cout << " right\n";
// move the n - 2 tower back to the empty peg
move_tower(n - 2, odd_on_right);
// run distribute() on n - 2 discs:
distribute(n - 2, odd_on_right);
}

void swap_towers(int n, bool odd_on_right)
{
interleave(n, odd_on_right);
distribute(2 * n, odd_on_right);
}``` 2. P.S.: The approach in Sedgewick-Wayne is to generate instructions of the form "3 left" or "2 right" for moving the disc of size n in the appropriate direction. Popular pages Recent additions 