//-----------------------------------------------------------------------------
// enigma1372.c (c) 2006 by Charles Petzold
//
// "Three Tours" by Keith Austin, New Scientist, 24/13 December 2005, page 72
//
// One-way roads between cities E, J, B, H, and M are:
//	EJ, EB, EH, JB, BH, JM, HM
//
// Transport on each road is always Ass (A), Colt (C), Donkey (D), or Mule (M).
//
// Three possible tours from E to M use these transports
//	1. A, C, M, C, D, M, ?
//	2. D, A, C, D, A, C, A, ?
//	3. D, M, C, M, C, A, ?
//
// What is the direction between B and H, and on what animal?
//-----------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Structure for the 7 roads
struct
{
	char city1;
	char city2;
	int dir;	// 0 for city1 --> city2, 1 for city2 --> city1
	char animal;
}
roads[] = 
{ 
	'E', 'J', 0, '?', 'E', 'B', 0, '?', 'E', 'H', 0, '?', 'J', 'B', 0, '?', 
	'B', 'H', 0, '?', 'J', 'M', 0, '?', 'H', 'M', 0, '?'
};

// Structure for the entire route.
typedef struct
{
	int legs;		// number of roads (7 or 8)
	int roadindex[8];	// for each leg, index into 'roads' array
}
ROUTE;

// Recursive function.
void Travel(char city, ROUTE ** route, int * count, int leg)
{
	int road, i;

	// If there's been 7 or 9 legs of the route and the city is M, we have a good one.
	if (((leg == 7) || (leg == 8)) && (city == 'M'))
	{
		// Record the number of legs
		(*route)[*count].legs = leg;

		// Allocate more memory for the array
		*count += 1;
		*route = (ROUTE *) realloc(*route, (1 + *count) * sizeof(ROUTE));

		// Copy the route into the new slot.
		(*route)[*count] = (*route)[*count - 1];
		return;
	}

	// If we're already made 8 legs and haven't wound up in M, something's wrong.
	if (leg == 8)
		return;

	// Test each of the seven roads
	for (road = 0; road < 7; road++)
	{
		// If the beginning city is a match...
		if (roads[road].dir == 0 && city == roads[road].city1)
		{
			// ... store the road and call the function recursively
			(*route)[*count].roadindex[leg] = road;
			Travel(roads[road].city2, route, count, leg + 1);
		}
		// Similarly for going on the road in reverse
		if (roads[road].dir == 1 && city == roads[road].city2)
		{
			(*route)[*count].roadindex[leg] = road;
			Travel(roads[road].city1, route, count, leg + 1);
		}
	}		
}

int main(void)
{
	ROUTE * route;
	int count;
	int dirbits, anibits, road;
	char animals[] = { 'A', 'C', 'D', 'M' };

	// These are the know routes.
	char * rides[] = { "ACMCDM", "DACDACA", "DMCMCA" };

	// This loop goes through the 128 possibilities for the directions
	// 	of each road.
	for (dirbits = 0; dirbits < 128; dirbits++)
	{
		// Set the dir field of each ROAD structure based on dirbits.
		for (road = 0; road < 7; road++)
			roads[road].dir = (dirbits >> road) & 1;

		// Allocate memory for at least one route
		count = 0;
		route = (ROUTE *) malloc(sizeof(ROUTE));

		// Call the recursive function
		Travel('E', &route, &count, 0);
		
		// If there's at least 3 good routes, pursue this combination of directions
		if (count >= 3)
		{
			int knownroute, goodroute, leg;

			// Loop through the possible distributions of animals
			for (anibits = 0; anibits < 16384; anibits++)
			{
				// Initialize three matches to 0
				int match[] = { 0, 0, 0 };

				// Set the animals of each road based on anibits
				for (road = 0; road < 7; road++)
					roads[road].animal = animals[(anibits >> (road * 2)) & 3];

				// Loop through the routes from E to M
				for (goodroute = 0; goodroute < count; goodroute++)
				{
					// Loop through the known routes
					for (knownroute = 0; knownroute < 3; knownroute++)
					{
						// If the number of legs is the same...
						if (route[goodroute].legs == strlen(rides[knownroute]) + 1)
						{
							// ... and if the animals match up...
							for (leg = 0; leg < strlen(rides[knownroute]); leg++)
							{
								if (roads[route[goodroute].roadindex[leg]].animal != rides[knownroute][leg])
									break;
							}
							// ... then set match to 1.
							if (leg == strlen(rides[knownroute]))
							{
								match[knownroute] = 1;
							}
						}
					}
				}
				// If there are three matches with the known routes, we're done!
				if (match[0] == 1 && match[1] == 1 && match[2] == 1)
				{
					// Print the actual routes
					for (goodroute = 0; goodroute < count; goodroute++)
					{
						for (leg = 0; leg < route[goodroute].legs; leg++)
						{		
							if (roads[route[goodroute].roadindex[leg]].dir)		
								printf("%c->%c ", roads[route[goodroute].roadindex[leg]].city2, 
							        	          roads[route[goodroute].roadindex[leg]].city1);
							else
								printf("%c->%c ", roads[route[goodroute].roadindex[leg]].city1, 
								                  roads[route[goodroute].roadindex[leg]].city2);
						}
						printf("\n");
					}

					// Print the directions and animals for each pair of cities
					for (road = 0; road < 7; road++)
					{
						if (roads[road].dir)
							printf("%c --> %c", roads[road].city2, roads[road].city1);
						else
							printf("%c --> %c", roads[road].city1, roads[road].city2);

						printf(" by %c\n", roads[road].animal);
					}
				}
			}
		}
		free (route);
	}

	return 0;
}

// There are two solutions printed, in which case we must take the clue from the puzzle
// that "you can ride from E to J" as factual.