/* FourCheeseStools.c implements functions for calculating the
 * moves required to move rounds of cheese between four stools
 * when constrained by Tower of Hanoi rules.
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "FourCheeseStools.h"
#define SENTINEL_MOVES -1

/* recursively calculate the number of moves required, recording
 * intermediate results in moveInfoTable
 */
moveInfo_t recursiveFourStoolMove(int n, moveInfo_t *moveInfoTable) {
    int i, bestSplit; /* loop index */
    double minMoves, candidateMoves;

    if (moveInfoTable[n].moves == SENTINEL_MOVES ) { /* some work to do */
	if (n == 1) {
	    moveInfoTable[n].moves = 1; /* it takes one move */
	    moveInfoTable[n].splitIndex= 1; /* move bottom 1 using 3 stools */
	}
	else if (n == 2) {
	    moveInfoTable[n].moves = 3; /* tower of hanoi */
	    moveInfoTable[n].splitIndex = 2;
	}
	else { /* for n>1, calculate recursively */
	    minMoves= pow(2, n); /* a high initial estimate */

	    /* take the minimum over 1<i<n, using the fact that
	     * it takes pow(2,i) to move i cheese rounds using only
	     * 3 pegs.
	     */
	    for (i = 2; i < n; i++) {
		candidateMoves= 2*recursiveFourStoolMove(n-i, moveInfoTable).moves
		    + pow(2,i) - 1;
		if (candidateMoves < minMoves) {
		    minMoves = candidateMoves;
		    bestSplit = i;
		}
	    }
	    moveInfoTable[n].moves = minMoves;
	    moveInfoTable[n].splitIndex = bestSplit;
	}
    }
    return moveInfoTable[n];
}
  
/*****************************************************************
 * Create and populate a table of moveInfo for n cheese rounds.
 * NB: calling function responsible to free moveInfoTable.
 ****************************************************************/
moveInfo_t *createMoveInfo(int n) {
    int i;
    moveInfo_t tmpInfo;
    moveInfo_t *moveInfoTable=
	(moveInfo_t *) malloc((n+1) * sizeof (moveInfo_t));

    /* initialize the table to sentinel value */
    for (i= 0; i <= n; i++) {
	moveInfoTable[i].moves= SENTINEL_MOVES;
    }

    /* tmpInfo not used */
    tmpInfo= recursiveFourStoolMove(n, moveInfoTable);
    return moveInfoTable;
}

  

/* A front-end to the recursive calculation of the number
 * of moves required.  Sets up a table to record intermediate
 * results, and then cleans it up.
 */
moveInfo_t fourStoolMove(int n){
    moveInfo_t returnMoveInfo, *moveInfoTable;

    /* set up a moveInfoTable, save the required value,
     * then tidy up.
     */
    moveInfoTable= createMoveInfo(n);
    returnMoveInfo= moveInfoTable[n];
    free(moveInfoTable);
    return returnMoveInfo;
}

int tourOfAnneHoy(int n, char src, char dst, char i1,
		  move_t *returnMoveList, int index) {
    int newIndex;
    if (n == 1) { /* presumed based case */
	returnMoveList[index].fromStool= src;
	returnMoveList[index].toStool= dst;
	return index + 1;
    }
    else { /* n > 1 */
	newIndex= tourOfAnneHoy (n-1, src, i1, dst, returnMoveList, index);
	newIndex= tourOfAnneHoy (1, src, dst, i1, returnMoveList, newIndex);
	newIndex= tourOfAnneHoy (n-1, i1, dst, src, returnMoveList, newIndex);
	return newIndex;
    }
}

int fourStoolTour(int n, char src, char dst, char i1, char i2,
		  move_t *returnMoveList, moveInfo_t *moveInfoTable,
		  int index) {
    int newIndex, split;

    if (n == 1) {
	return tourOfAnneHoy(1, src, dst, i1, returnMoveList, index);
    }
    else if (n == 2) {
	return tourOfAnneHoy(2, src, dst, i1, returnMoveList, index);
    }
    else { /* more than 2 cheese rounds */
	split= moveInfoTable[n].splitIndex;

	newIndex=
	    fourStoolTour(n-split, src, i1, i2, dst, returnMoveList,
			  moveInfoTable, index);
	newIndex=
	    tourOfAnneHoy(split, src, dst, i2, returnMoveList, newIndex);
	newIndex=
	    fourStoolTour(n-split, i1, dst, src, i2, returnMoveList,
			  moveInfoTable, newIndex);
	return newIndex;
    }
}

move_t *moveList(int n, char src, char dst, char i1, char i2){
    int tmpIndex;
    move_t *returnMoveList;
    moveInfo_t *moveInfoTable;

    /* create a table of moveInfo_t for deciding on move strategy
     */
    moveInfoTable= createMoveInfo(n);
    returnMoveList= (move_t *)malloc((moveInfoTable[n].moves+1) *
				     sizeof(move_t));
    /* set end of list */
    returnMoveList[moveInfoTable[n].moves].fromStool= '\0';
    returnMoveList[moveInfoTable[n].moves].toStool= '\0';

    /* tmpIndex is not used further */
    tmpIndex=
	fourStoolTour(n, src, dst, i1, i2, returnMoveList, moveInfoTable, 0);

    free(moveInfoTable);
    return returnMoveList;
}