#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>

#define BOX '$'
#define WALL '#'
#define MAN '@'
#define PLATFORM '.'
#define BOXINPLATFORM '*'
#define MANINPLATFORM 'E'
#define BLANK ' '
#define CORNER '-'
#define MANCANMOVE '+'

#define NBOX(n) ((n)<<2)

//#define DEBUG

enum
{
	ALARM_SECONDS=1
};


enum logic
{
	TRUE=1,
	FALSE=0,
};

#define MAX_X 50
#define MAX_Y 50
#define MAX_MOVES 50
#define MAX_STEPS 50
#define MAX_BOXES 15

#define MOVE_OK		1
#define MOVE_BOX	2
#define MOVE_ILLEGAL	0


/* SOKOBAN Solution Finder
 *
 * Input File Format: XSB
 *
 * XSB Format definition:
 * 	Character matrix of:
 * 		@	MAN
 * 		#	WALL
 * 		$	BOX
 * 		*	BOX over PLATFORM
 * 		+	PLATFORM
 * 		-	(optional) Where a BOX should not be put
 * 	Everything that cannot be reached by the man or boxes (WALLS) must be
 * 	marked as is: WALLS.
 * 	All lines must be of the same length.
 */

struct Position
{
	int x;
	int y;
};

struct Map
{
	char Cells[MAX_Y][MAX_X];
	char cells_boxes[MAX_Y][MAX_X];
	char man_moves[MAX_Y][MAX_X];
	int SizeX, SizeY;
	struct Position Man;
	int NumPlatforms;
	int NumBoxesInPlatform;
	struct Position Box[MAX_BOXES];
	int NumBoxes;
};



enum e_direction
{
	DIR_LEFT,
	DIR_RIGHT,
	DIR_DOWN,
	DIR_UP
};
const struct Position move_vectors[4] = {
	{0, 1},
	{0, -1},
	{1, 0},
	{-1, 0}};

struct BoxMove
{
	int box;
	struct Position dir;
};

float percent_to_show = 0;
int depth_to_show = 0;

int max_depth = 0;
int min_depth_period = 0;
int max_depth_period = 0;
struct Map * actual_map;




void CopyMap (struct Map *Mdest, const struct Map *Morig)
{
	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
}


void ReadMap(struct Map *M, char *FileName)
{
	FILE *Fitxer;
	int i,j;

	if(!(Fitxer = fopen(FileName, "r")))
	{
		printf("Error opening %s!", FileName);
		exit(1);
	}

	M->SizeX=0;
	M->SizeY=0;
	while (!feof(Fitxer))
	{
		fgets(M->Cells[M->SizeY], MAX_X, Fitxer);
		M->SizeY++;
	}
	M->SizeY--;
	M->SizeX = strlen(M->Cells[0]) - 1;

	M->NumPlatforms = 0;
	M->NumBoxesInPlatform = 0;
	M->NumBoxes = 0;
	for (j = 0; j<M->SizeY; j++)
		for (i=0; i<M->SizeX; i++)
		{
			if (M->Cells[j][i] == MAN)
			{ 
				M->Man.x = i; M->Man.y = j; 
				M->Cells[M->Man.y][M->Man.x] = BLANK;
			}

			if (M->Cells[j][i] == PLATFORM)
				M->NumPlatforms++;
			else if (M->Cells[j][i] == BOXINPLATFORM)
			{
				M->Cells[j][i] = PLATFORM;

				M->NumPlatforms++;
				M->NumBoxesInPlatform++;

				M->Box[M->NumBoxes].x = i;
				M->Box[M->NumBoxes].y = j;
				M->NumBoxes++;
			} else if (M->Cells[j][i] == BOX)
			{
				M->Cells[j][i] = BLANK;

				M->Box[M->NumBoxes].x = i;
				M->Box[M->NumBoxes].y = j;
				M->NumBoxes++;
			} else if (M->Cells[j][i] == CORNER)
			{
				M->Cells[j][i] = CORNER;
			} else if (M->Cells[j][i] != WALL)
			{
				if (    (M->Cells[j][i-1] == WALL &&
					 M->Cells[j-1][i] == WALL) ||
					(M->Cells[j][i-1] == WALL &&
					 M->Cells[j+1][i] == WALL) ||
					(M->Cells[j][i+1] == WALL &&
					 M->Cells[j-1][i] == WALL) ||
					(M->Cells[j][i+1] == WALL &&
					 M->Cells[j+1][i] == WALL))
				M->Cells[j][i] = CORNER;
			}
				
		}

}


void ShowMap (const struct Map *M)
{
	struct Map Temp;
	int i,j;

	CopyMap(&Temp, M);

	Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN;

	for (i = 0; i < Temp.NumBoxes; i++)
	{
		if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM)
			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM;
		else
			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX;
	}

	for (j = 0; j<Temp.SizeY; j++)
	{
		for (i=0; i<Temp.SizeX; i++)
			fprintf(stderr,"%c", Temp.Cells[j][i]);
		fprintf(stderr,"\n");
	}

#if 0
	// Print Where the man can move
	for (j = 0; j<Temp.SizeY; j++)
	{
		for (i=0; i<Temp.SizeX; i++)
			printf("%c", Temp.ManMoves[j][i]);
		printf("\n");
	}
#endif

	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
			Temp.NumBoxesInPlatform);

}



int InverseMove(char Dir1, char Dir2)
{
	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
		return 1;
	return 0;
}


void PrintCombination(int Moves[], int NumMoves)
{
	int i;

	for (i=0; i < NumMoves; i++)
	{
		printf("%i", Moves[i] >> 2);
		if ((Moves[i] & 0x03) == DIR_LEFT)
			printf("L");
		else if ((Moves[i] & 0x03) == DIR_RIGHT)
			printf("R");
		else if ((Moves[i] & 0x03) == DIR_UP)
			printf("U");
		else
			printf("D");
		printf(",");
	}
	printf("\n");
}

#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/
 Situation:
    
  ->@$ #
      $
*/
int box_will_be_blocked(const struct Map * m, const struct Position mov,
	const struct Position box_pos)
{
	struct Position next_pos2, tmp, tmp2[2];
	int i;

	next_pos2.x = box_pos.x + mov.x;
	next_pos2.y = box_pos.y + mov.y;

	tmp.x = next_pos2.x + mov.x;
	tmp.y = next_pos2.y + mov.y;
	tmp2[0].x = next_pos2.x + mov.y;
	tmp2[0].y = next_pos2.y + mov.x;
	tmp2[1].x = next_pos2.x - mov.y;
	tmp2[1].y = next_pos2.y - mov.x;
	for (i=0; i < 2; i++)
	{
		if (m->man_moves[tmp.y][tmp.x] == WALL &&
			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
		{
			return TRUE;
		}
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)
		{
			return TRUE;
		}
		else if (m->man_moves[tmp.y][tmp.x] == BOX &&
			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)
		{
			return TRUE;
		}
	}

	return FALSE;
}

int is_corner_area(const struct Map * m, const struct Position p,
	const struct Position box, const struct Position new_box)
{
	int NumMoves, NewMoves;
	struct Position pos[MAX_MOVES];
	struct Position new_pos[MAX_MOVES];
	char corners[MAX_Y][MAX_X];
	int i,j;
	struct Position next_pos;
	char *next_cell;


	/* Blank the garden */
	for (j = 0; j<m->SizeY; j++)
		for (i=0; i<m->SizeX; i++)
			corners[j][i] = m->Cells[j][i];

	/* Let's put the boxes */
	for (i = 0; i<m->NumBoxes; i++)
		corners[m->Box[i].y][m->Box[i].x] = BOX;

	/* Let's put our box - it can be simply added */
	corners[new_box.y][new_box.x] = BOX;
	/* Let's remove the original box. */
	corners[box.y][box.x] = BLANK;

	NewMoves = 1;
	new_pos[0] = p;
	while (NewMoves > 0)
	{
		/* The before named "New Moves" become the moves we have
		   to analyze */
		NumMoves = NewMoves;
		for (i=0; i<NewMoves; i++)
		{
			pos[i] = new_pos[i];
		}

		/* Search new positions for each position */
		NewMoves = 0;
		for (i=0; i<NumMoves; i++)
		{
			/* For each direction */
			for (j=0; j<4; j++)
			{
				next_pos.x = pos[i].x + move_vectors[j].x;
				next_pos.y = pos[i].y + move_vectors[j].y;
				next_cell = &corners[next_pos.y][next_pos.x];
				if(*next_cell == BLANK ||
					*next_cell == PLATFORM)
				{
					return FALSE;
				}
				else if(*next_cell == CORNER)
				{
					new_pos[NewMoves] = next_pos;
					*next_cell = MANCANMOVE;
					NewMoves++;
				}
			}
		}
	}

	return TRUE;
}

int does_box_close_corners(const struct Map * m, const struct Position mov,
	const struct Position box_pos)
{
	struct Position p, p2;

	p.x = box_pos.x + mov.x;
	p.y = box_pos.y + mov.y;
	
	/* Let's plan the checks */
	/* The point will be marked with a MANCANMOVE */
	p2.x = p.x + mov.x;
	p2.y = p.y + mov.y;
	if (m->Cells[p2.y][p2.x] == CORNER)
	{
		if (is_corner_area(m, p2, box_pos, p))
			return TRUE;
	}

	p2.x = p.x + mov.y;
	p2.y = p.y + mov.x;
	if (m->Cells[p2.y][p2.x] == CORNER)
	{
		if (is_corner_area(m, p2, box_pos, p))
			return TRUE;
	}

	p2.x = p.x - mov.y;
	p2.y = p.y - mov.x;
	if (m->Cells[p2.y][p2.x] == CORNER)
	{
		if (is_corner_area(m, p2, box_pos, p))
			return TRUE;
	}
	return FALSE;
}
#endif

/*
Catch the situation where a box is moved next to a corner, where the box
next to it will not be able to be moved.
*/
int is_dead1(const struct Map * m, const struct Position mov,
	const struct Position new_pos)
{
	struct Position opposite1, opposite2;

	/* The wall corners must exist */
	opposite1.x = -mov.y;
	opposite1.y = -mov.x;
	opposite2.x = mov.y;
	opposite2.y = mov.x;

#ifdef DEBUG
	ShowMap(m);
#endif

	/* Test the first corner */
	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]
		== WALL)
	{
		/* Test wall at opposites 1*/
		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
			== WALL &&
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
		{
				return TRUE;
		}
		else
		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
			== BOX &&
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
		{
				return TRUE;
		}
		/* Test wall at opposites 2 */
		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
			== WALL &&
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
		{
				return TRUE;
		}
		else
		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
			== BOX &&
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
		{
				return TRUE;
		}
	}

	/* Test the second corner */
	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]
		== WALL)
	{
		/* Test wall at opposites 1*/
		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
			== WALL &&
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
		{
				return TRUE;
		}
		else
		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]
			== BOX &&
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
		{
				return TRUE;
		}
		/* Test wall at opposites 2 */
		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
			== WALL &&
			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)
		{
				return TRUE;
		}
		else
		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]
			== BOX &&
			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)
		{
				return TRUE;
		}
	}

	return FALSE;
}

/*
Catch the situation where a corner gets surrounded by boxes.
*/
int is_dead2(const struct Map * m, const struct Position mov,
	const struct Position new_pos)
{
	struct Position next, next2, opposite1, opposite2;

	next.x = new_pos.x+mov.x;
	next.y = new_pos.y+mov.y;

	/* The corner must exist */
	if (m->Cells[next.y][next.x] != CORNER)
		return FALSE;


	/* The wall corners must exist */
	opposite1.x = next.x -mov.y;
	opposite1.y = next.y -mov.x;
	opposite2.x = next.x + mov.y;
	opposite2.y = next.y + mov.x;

	if (m->man_moves[opposite1.y][opposite1.x] == BOX)
	{
		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL
		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)
		   return TRUE;
	}

	if (m->man_moves[opposite2.y][opposite2.x] == BOX)
	{
		if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL
		   && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL)
		   return TRUE;
	}
	return FALSE;
}

int is_box_movable(const struct Map * m, const struct Position mov,
	const struct Position box_pos)
{
	struct Position next_pos2;

	next_pos2.x = box_pos.x + mov.x;
	next_pos2.y = box_pos.y + mov.y;

	if((m->Cells[next_pos2.y][next_pos2.x] != BLANK &&
		m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) ||
		m->man_moves[next_pos2.y][next_pos2.x] == BOX)
	{
		return FALSE;
	}
	else if (is_dead1(m, mov, next_pos2) == TRUE)
	{
		return FALSE;
	}
	else if (is_dead2(m, mov, next_pos2) == TRUE)
	{
		return FALSE;
	}
	return TRUE;
}

/* It modifies m->man_moves */
int get_box_movements(struct Map * m,
	struct BoxMove movements[])
{
	struct Position pos[MAX_MOVES];
	struct Position new_pos[MAX_MOVES];
	int NumMoves, NewMoves;
	int j, i;
	struct Position next_pos;
	char *next_cell;
	int num_box_movements = 0;
	
	/* Let's  the map with only walls in man_moves - other, blanks */
	for (j = 0; j<m->SizeY; j++)
		for (i=0; i<m->SizeX; i++)
		{
			if (m->Cells[j][i] == WALL)
				m->man_moves[j][i] = WALL;
			else
				m->man_moves[j][i] = BLANK;
		}

	/* Let's put the boxes */
	for (i = 0; i<m->NumBoxes; i++)
	{
		m->man_moves[m->Box[i].y][m->Box[i].x] = BOX;
		m->cells_boxes[m->Box[i].y][m->Box[i].x] = i;
	}

	NewMoves = 1;
	new_pos[0].x = m->Man.x;
	new_pos[0].y = m->Man.y;
	m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE;
	while (NewMoves > 0)
	{
		/* The before named "New Moves" become the moves we have
		   to analyze */
		NumMoves = NewMoves;
		for (i=0; i<NewMoves; i++)
		{
			pos[i] = new_pos[i];
		}

		/* Search new positions for each position */
		NewMoves = 0;
		for (i=0; i<NumMoves; i++)
		{
			/* For each direction */
			for (j=0; j<4; j++)
			{
				next_pos.x = pos[i].x + move_vectors[j].x;
				next_pos.y = pos[i].y + move_vectors[j].y;
				next_cell = &m->man_moves[next_pos.y][next_pos.x];
				if(*next_cell == BLANK)
				{
					new_pos[NewMoves] = next_pos;
					*next_cell = MANCANMOVE;
					NewMoves++;
				}
				else if (*next_cell == BOX)
				{
						
					/* Check if the box is movable */

					if (is_box_movable(m, move_vectors[j],
						next_pos ))
					{
						{
					movements[num_box_movements].box =
					m->cells_boxes[next_pos.y][next_pos.x];
					movements[num_box_movements].dir =
					move_vectors[j];
					num_box_movements++;
						}
					}
					
				}

			}
		}
	}

	return num_box_movements;
}

void force_move_box(struct Map *m, struct BoxMove move)
{
	struct Position newpos;


	/* Add coords */
	newpos.x = m->Box[move.box].x + move.dir.x;
	newpos.y = m->Box[move.box].y + move.dir.y;

	/* Be certain the move can be done */
	assert(m->Cells[newpos.y][newpos.x] != BOX);
	assert(m->Cells[newpos.y][newpos.x] != WALL);

	/* Control if we moved the box to a platform */
	if(m->Cells[newpos.y][newpos.x] == PLATFORM)
	{
		m->NumBoxesInPlatform++;
	}

	/* Control if we moved the box from a platform */
	if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM)
	{
		m->NumBoxesInPlatform--;
	}
	m->Man = m->Box[move.box];

	m->Box[move.box] = newpos;
}

int are_boxes_equal(const struct Position b1[], const struct Position b2[],
	int n)
{
	int i;
	char tmp[MAX_Y][MAX_X]; /* !!!argh */

	memset(tmp, 0, sizeof(tmp));

	for (i=0; i < n; i++)
	{
		tmp[b1[i].y][b1[i].x] = 1;
	}
	for (i=0; i < n; i++)
	{
		if (tmp[b2[i].y][b2[i].x] != 1)
			return FALSE;
	}
	return TRUE;
}

int is_new_map(struct Map maps[], int depth)
{
	struct Map *m;
	int i;

	m = &maps[depth];

	for(i=0; i<max_depth; i++)
	{
		/* No l'hem de comparar amb ell mateix */
		if (i == depth)
			continue;

		if (m->NumBoxesInPlatform != maps[i].NumBoxesInPlatform)
			continue;
		else
		{
			if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes))
				continue;
		}
		return FALSE;
	}
	return TRUE;
}

void PrintMove(struct BoxMove b)
{
	printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
}

void show_percent_callback(int parameter)
{
	fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show,
		min_depth_period, max_depth_period);
	ShowMap(actual_map);
	fflush(stderr);
	min_depth_period = MAX_STEPS;
	max_depth_period = 0;
#ifndef DEBUG
	alarm(ALARM_SECONDS);
#endif
}

int search_depth(struct Map maps[], int depth,
	struct BoxMove movements[],
	int num_movements, float percent, float total_percent)
{
	struct BoxMove new_movements[MAX_MOVES];
	int num_new_movements;
	struct Map *m; 
	int i;
	float next_percent;

	next_percent = percent / num_movements;

	m = &maps[depth+1];
	if (depth > max_depth)
		max_depth = depth;
	if (depth > max_depth_period)
		max_depth_period = depth;
	if (depth < min_depth_period)
		min_depth_period = depth;

	for (i=0; i < num_movements; i++)
	{
		CopyMap(m, &maps[depth]);
		force_move_box(m, movements[i]);
		if (m->NumPlatforms == m->NumBoxesInPlatform)
		{
			printf("\nSolved!\n");
			PrintMove(movements[i]);
			return 0;
		}

		if (is_new_map(maps, depth+1))
		{
			num_new_movements = get_box_movements(m, new_movements);
			assert(num_new_movements < MAX_MOVES);
		}
		else
			num_new_movements = 0;

		if (num_new_movements == 0)
		{
			percent_to_show = total_percent + next_percent*i;
			depth_to_show = depth;
			actual_map = &maps[depth];
#ifdef DEBUG		/* to be out */
			show_percent_callback(0);
#endif
	
		}
		else
		{
			if (depth+1 < MAX_STEPS)
			{
				if(search_depth(maps, depth+1, new_movements,
					num_new_movements, next_percent,
					total_percent + next_percent*i) == 0)
				{
					PrintMove(movements[i]);
					return 0;
				}
			}
		}
	}
	return 1;
}




void program_alarm()
{
        struct sigaction my_action;
        int result;

        my_action.sa_handler = show_percent_callback;
        my_action.sa_flags = 0;
        memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask));

        result = sigaction(SIGALRM, &my_action, NULL);
        assert(result == 0);

	alarm(1);
}

int main(int argn, char **argv)
{
	struct Map Morigin;
	struct Map maps[MAX_STEPS+1];
	struct BoxMove new_movements[MAX_MOVES];
	int num_new_movements;


	if (argn != 2)
	{
		printf("Usage: %s <mapfile>\n", argv[0]);
		exit(3);
	}
	ReadMap(&Morigin, argv[1]);

	// Reget the original map
	CopyMap(&maps[0], &Morigin);

	assert(maps[0].NumPlatforms > maps[0].NumBoxesInPlatform);

	num_new_movements = get_box_movements(&maps[0], new_movements);
	assert(num_new_movements < MAX_MOVES);
	assert(num_new_movements > 0);

#ifndef DEBUG
	program_alarm();
#endif
	search_depth(maps, 0, new_movements,
		num_new_movements, 100. / num_new_movements,
		0);

	return 0;

}