/* Final Fantasy 13-2 solver for Hands of Time clock puzzles
 * Author:  Geoff Carpenter
 *
 * Clock is comprised of a circle of single digits; one must find a path
 * that visits all of the digits just once.  At each digit, one can move
 * the indicate number of positions either clockwise or counterclockwise.
 * 
 * Given a problem of 113, there are 2 possible solutions:
 *	pos: 1 number: 1
 *	pos: 2 number: 1
 *	pos: 3 number: 3
 *
 *	pos: 2 number: -1
 *	pos: 1 number: -1
 *	pos: 3 number: 3
 *
 * "pos" indicates the position on the clock, with "1" being the topmost,
 * "2" being the next one in clockwise order.
 * "number" indicates the label on the clock digit; a negative value means
 * to move in a counterclockwise direction to locate the next element.
 */


%include <OMEcore.o2h>

class FF13_ClockPuzzle {
	array	initialState;
	int	totalPositions;
	array	solution;
	array	jumpAmount;
} inherits from Object;

FF13_ClockPuzzle:create(any startVal)
{
	if (argc == 0) exit;

	call "FF13_ClockPuzzle:initialize"(arrayToSet(argv));
	call "iterateSolutions"();
	send "deleteYourself" to thisObject;
}

FF13_ClockPuzzle:initialize(any startVal)
{
	int	l;

	l = call "loadProblem"(startVal);
	if (l == 0) {
		display("No argument provided\n");
		return (0);
	}
	display("total positions=", l, " initial state=",initialState);
	return (l);
}

FF13_ClockPuzzle:iterateSolutions()
{
	int i, j, ok;

	for(i=0;i<totalPositions;i+=1) { // try various starting positions
		ok = call "solveRecursively"(i, totalPositions,
			totalPositions, initialState);
		if (ok != 0) {
			display("\nSolved starting from position ", i+1, "\n");
			for(j=totalPositions-1;j>=0;j-=1) {
				display("pos: ", solution[j] + 1,
					" number: ", jumpAmount[j], "\n");
			}
			break;
		}
	}
	if (ok == 0) {
		display("No solution found\n");
	}
	return (ok);
}

FF13_ClockPuzzle:delete()
{
}

FF13_ClockPuzzle:getInitialState()
{
	return (initialState);
}

FF13_ClockPuzzle:loadProblem(any startVal)
{
	int	i;
	string	initial;

display("loadProblem argv=", argv);
	initial = makeAsString(startVal);
	if (initial == "nil") {	// no arguments...
		return (0);
	}

	totalPositions = length(initial);
	for(i=0;i<totalPositions;i+=1) {	// load problem description
		initialState[i] = midchar(initial, i) - '0';
	}
	return (totalPositions);
}

FF13_ClockPuzzle:solveRecursively(int startFrom, int moves,
	int total, array state)
{
	int count, pos1, pos2, ok;

	moves -= 1;
	count = state[startFrom];
	if (count == 0) {	// position already visited
		return (0);	// fail
	}
	state[startFrom] = 0;	// clear position
	if (moves == 0) {	// last move
		solution[moves] = startFrom;
		jumpAmount[moves] = count;
		return (1);			// success, all done
	}
	pos1 = startFrom + count;		// clockwise
	if (pos1 >= total) pos1 -= total;	// wrap if needed
	ok = call "solveRecursively"(pos1, moves, total, state);
	if (ok != 0) {				// solution found
		solution[moves] = startFrom;	// record move
		jumpAmount[moves] = count;
		return (1);			// success
	}
	// try other direction...
	pos2 = startFrom - count;		// counterclockwise
	if (pos2 < 0) pos2 += total;		// wrap if needed
	ok = call "solveRecursively"(pos2, moves, total, state);
	if (ok != 0) {				// solution found
		solution[moves] = startFrom;	// record move
		jumpAmount[moves] = -count;
		return (1);			// success
	}
	return (0); // failed either way
}

class FF13_ParallelClockPuzzle {
	any	problem;
	int	pendingAttempts;
	int	total;
	int	maxPending;
	int	totalSolutions;
} inherits from FF13_ClockPuzzle;

FF13_ParallelClockPuzzle:create(any startVal)
{
	int	i;

	total = call "FF13_ClockPuzzle:initialize"(arrayToSet(argv));
	problem = call "getInitialState"();

	pendingAttempts = total;
	maxPending = total;
	alwaysAllow("attemptSolution");
	for(i=0;i<total;i+=1) {
		send "attemptSolution"(emptySet + (emptySet + i), i, total,
			problem) to thisObject;
	}
}

FF13_ParallelClockPuzzle:answer(int ok, set path,
	int startFrom, int moves, int count)
{
	int	i, j, l, amt, lastPos, pos, pos2, sign;

	if (ok == 1) {				// solution found
		totalSolutions += 1;
		display("Solution #", totalSolutions, ": ", path, "\n");
		lastPos = -1;
		amt = 0;
		for pos in path do {
			if (lastPos != -1) {
				if ((lastPos + amt) == pos) {
					sign = 1;
				} else {
					sign = -1;
				}
				display("pos: ", lastPos + 1,
					" number: ", sign * amt, "\n");
			}
			amt = problem[pos];
			pos2 = pos + amt;
			if (pos2 >= l) pos2 -= l;
			lastPos = pos;
		}
		sign = 1;	// last move is always forced
		display("pos: ", lastPos + 1,
			" number: ", sign * amt, "\n");
		display("END solution ", path, "\n");
		
	}
	pendingAttempts -= 1;
	if (pendingAttempts == 0) {
		display("All done, ", totalSolutions,
			" solutions found, maxPending=", maxPending, "\n");
	}
}

FF13_ParallelClockPuzzle:attemptSolution(set path, int startFrom,
	int moves, array state)
{
	int count, pos1, pos2, ok;

	moves -= 1;
	count = state[startFrom];
	if (count == 0) {	// failure, reached node already used
		send "answer"(0, emptySet + path, startFrom, moves, count)
			to fromObject;
		exit;		// all done
	}
	state[startFrom] = 0;	// clear position
	if (moves == 0) {	// last move, success
		send "answer"(1, emptySet + path, startFrom, moves, count)
			to fromObject;
		exit;		// all done
	}

	pos1 = startFrom + count;		// clockwise
	if (pos1 >= total) pos1 -= total;	// wrap if needed
	pos2 = startFrom - count;		// counterclockwise
	if (pos2 < 0) pos2 += total;		// wrap if needed

	pendingAttempts += 1; // current count plus 1 more
	if (pendingAttempts > maxPending) {
		maxPending = pendingAttempts;
	}
	send "attemptSolution"(emptySet + (path + pos1), pos1, moves, state)
		to thisObject from fromObject;
	send "attemptSolution"(emptySet + (path + pos2), pos2, moves, state)
		to thisObject from fromObject;
}