COMP 104 : Programming

Lab 7 : Tower of Fruitcake

In this lab, you are going to help Artificial Intelligence researchers solve their famous "Tower of Fruitcake" problem.

There are nine letters: 'f', 'r', 'u', 'i', 't','c','a','k', and 'e', and three towers, A, B, and C. Initially, the nine letters can be in any position in any of the three towers. For instance, one possible initial state can be:


 t
f
 c
r
 i
 e
k
 u
 a
Tower A
 Tower B
 Tower C


The goal is to get from the given initial state to the following final state:
 

e

k

a

c

t

i

u

r

f

Tower A
 Tower B
 Tower C


There is only one type of actions (operators) that you are allowed to use for achieving this task:

    move(X,Y) - move the top letter from tower X to tower Y

(If tower X is empty, then this action has no effect.) For instance, for the above initial state, the new state after performing the action move(A,B) is:


 f

t

c
r
 i
 e
k
 u
 a
Tower A
 Tower B
 Tower C


Input/Output specification

The initial state will be given to you by a file named "initial_state.txt" that contains three non-empty lines of strings. The first non-empty line is the contents of tower A, starting from the bottom. Similarly, the next two non-empty lines are the contents of towers B and C.  For example, the contents of "initial_state.txt" for the above example is:

krf
uict
ae

Your solution needs to be written into another file called "solution.txt". It starts with the initial state, followed by the action to be performed, and then the new state that results from performing the action, and so on until the goal state is achieved. For instance, this contains one possible solution to the goal given the above initial state. While you are encouraged to find an efficient solution, reaching the goal state is sufficient for full marks.

As in Lab6, use separate files for the main program, the function prototypes, and the function definitions. Here is main.cpp with the main program, and here is lab7.h with the function prototypes. Your job is to create another file lab7.cpp with the function definitions.

HINTS
(1) Note that to pass a fstream variable into a function, you must use pass-by-reference. Thus for example, the following is okay:
    void my_function(int, ofstream&)
but not the following
    void my_function(int, ofstream)

(2) The string function length will be useful for this lab. Here is an example:
    string s = "fruitcake";
    cout << s.length();   // outputs 9 when s="fruitcake"

Demo your working program for your TA. The TA will check your source code to make sure you made reasonable use of strings, file I/O, and functions. If for some reason you cannot finish before the end of the lab period, email your program to your TA by Sunday 6 November 5PM (please include your name and lab section as a comment on line 1 of your program).