## Description

csce350 — Data Structures and Algorithms

Project 1: The Tower of Huger

The purpose of this assignment is to give you some practice translating a pseudocode description of a recursive algorithm

into working software.

The Problem Most computer scientists are familiar with the Tower of Hanoi problem, but not many are

familiar with its close cousin, the Tower of Huger problem. In the Tower of Huger, each disk has a color —

either garnet or black— in addition to its size. The disks come in pairs, with one disk of each color in each

size. We measure the input size n as the number of pairs of disks. Here’s what the starting state looks like, for

n = 3:

C

3

2

1

A

B

Each disk has a name, capital letters for black disks and positive integers for the garnet ones, starting with the

largest disks. Notice the names in the picture above. Just like in the Tower of Hanoi problem, we can move

one disk at a time, but can never stack a larger disk on top of a smaller one. The goal is to separate everything

into two separate stacks, one with all the garnet disks and one with all the black disks, like this:

A

B

C 3

2

1

Before continuing to the next page, you might want to think a bit about what sort of algorithm you might use

to solve this problem. (Hint: How could you use the SOLVETOWER algorithm for the Tower of Hanoi as a

subroutine?)

(This space left intentionally blank to prevent spoilers while you think about the problem.)

csce350 Project 1: The Tower of Huger 1 of 3

Here’s a algorithm to solve the Tower of Huger problem.

SOLVEHUGER(n, a, b, c)

if n < 2 then

Move a disk from a to c.

Move a disk from a to b.

else

MOVESTACKOFPAIRS(n − 1, a, b, c)

Move a disk from a to c.

Move another disk from a to c.

MOVESTACKOFPAIRS(n − 1, b, a, c)

Move disk from c to b.

SOLVEHUGER(n − 1, a, b, c)

end if

The function call to MOVESTACKOFPAIRS, which is intended to move a stack of n alternating garnet/black

pairs, looks like this:

MOVESTACKOFPAIRS(n, a, b, c)

if n < 2 then

Move a disk from a to c.

Move a disk from a to b.

Move a disk from c to b.

else

MOVESTACKOFPAIRS(n − 1, a, b, c)

Move a disk from a to c.

Move another disk from a to c.

MOVESTACKOFPAIRS(n − 1, b, a, c)

Move a disk from c to b.

Move another disk from c to b.

MOVESTACKOFPAIRS(n − 1, a, b, c)

end if

(We could have used the standard SOLVETOWER instead of MOVESTACKOFPAIRS for this purpose. That would

have been correct, but slower.)

Your Task Your job for this project is to write a program that solves the Tower of Huger problem, using the

SOLVEHUGER algorithm. Specifically, you should write a C++ program that does precisely these things:

1. Read a positive integer n from standard input.

2. Output, to standard output, the starting state of the Tower of Huger with n pairs of disks. The first line

should be Starting at, and the next three lines should show contents of the three pegs. See example

output for details.

3. Output the sequence of moves used by the algorithm above for that value of n to solve the Tower of

Huger problem. For each move, describe the move like this,

Step : Move disk from peg to peg .

showing the move number, the disk that’s being moved, the source peg, and the target peg, Then show

the state of the pegs, just like at the starting state. Again, be sure to match the exact format of the sample

output shown below.

4. Output Done!

5. Return to Step 1 above to read and process another value of n. Terminate when standard input reaches

end-of-file.

csce350 Project 1: The Tower of Huger 2 of 3

Here’s a simple example input and output.

Sample Input 1

1

Sample Output 1

Starting at

0:A1

1:

2:

Step 1: Move disk 1 from peg 0 to peg 2.

0:A

1:

2:1

Step 2: Move disk A from peg 0 to peg 1.

0:

1:A

2:1

Done!

Since larger values of n lead to very long outputs, additional sample input/output pairs are available on the

course website. You’ll want to check them carefully.

Notes A few possibly helpful comments:

• For calibration purposes, my solution has 80 lines of code. If you find yourself writing huge amounts of

code, something has probably gone wrong.

• Keep in mind that you are expected to submit your own original work for this problem. Accessing

reference material for C++ in general is fine and encouraged. However, you are strongly discouraged

from conducting web searches for code specific to the Tower of Huger or Tower of Hanoi problems.

What to Submit You should submit, using the department’s dropbox website, a single C++ source file containing all of the code for your program. We will compile this program using this command line:

g++ -Wall -std=c++11 yourfile.cpp

csce350 Project 1: The Tower of Huger 3 of 3