/***************************************************************** 
 * FourCheeseStools.h provides the public interface for moving
 * rounds of cheese between four stools, always obeying the
 * Tower of Hanoi (TOH) rules (see handout).
 ***************************************************************/


/*****************************************************************
 * moveInfo_t variables record both the number of moves required
 * (moves) and where to split a stack of cheese rounds
 * (splitIndex) in four-stool cheese moving.
 ****************************************************************/
typedef struct moveInfo_ {
  int moves;
  int splitIndex;
} moveInfo_t;

/*****************************************************************
 * move_t variables record a single move from (fromStool) to 
 * (toStool), assuming the stools are labeled with characters and
 * the top cheese on stool fromStool is moved to stool toStool.
 ****************************************************************/
typedef struct move_ {
  char fromStool;
  char toStool;
} move_t;

/*****************************************************************
 * fourStoolMove: find the number of moves, and the best split
 *                between three-stool and four-stool tactics, for
 *                moving a stack of n cheese rounds across 4
 *                stools.
 *
 * parameter:     n is the number of cheese rounds, stacked in
 *                decreasing order of diameter, to be moved from
 *                a source stool to a destination stool.
 *
 * return:        struct {moves, splitIndex} that minimizes the
 *                value of moves over all choices of splitIndex,
 *                1 < splitIndex < n, using the strategy:
 *
 *                move (n - splitIndex) smallest rounds of cheese
 *                to an intermediate stool, using 4 stools.  Then
 *                move splitIndex largest rounds of cheese to the
 *                destination stool using 3 stools, then move the
 *                (n - splitIndex) smallest rounds of cheese from
 *                the intermediate stool to the destination, using
 *                4 stools.
 ****************************************************************/
moveInfo_t fourStoolMove(int n);

/*****************************************************************
 * moveList: find a (possibly optimally) short list of moves over
 *           from stool src to stool dst, using i1 and i2 as
 *           intermediates.
 *
 * parameter: n is the (positive integer) number of cheese rounds,
 *            stacked in decreasing order of diameter, to be moved
 *            from stool src to stool dst, using stools i1 and i2
 *            as intermediates.  src, dst, i1, and i2 are distinct
 *            characters.
 *
 * return:    An array of type move_t, terminated by struct {\0, \0}.
 *            Executing the moves will transfer the stack of
 *            n cheese rounds (in decreasing order of diameter)
 *            from stool src to stool dst, using i1 and i2 as
 *            intermediates, never stacking a larger cheese round
 *            on top of a smaller one (TOH rule).
 ****************************************************************/
move_t *moveList(int n, char src, char dst, char i1, char i2);