--- a/sokosol.c	Sat May 06 00:33:47 2006 +0200
+++ b/sokosol.c	Sat May 06 00:34:04 2006 +0200
@@ -1,9 +1,7 @@
+#include <assert.h>
 #include <stdio.h>
 #include <string.h>
-#include <assert.h>
 #include <stdlib.h>
-#include <unistd.h>
-#include <signal.h>
 #include "general.h"
 
 #define NBOX(n) ((n)<<2)
@@ -26,613 +24,14 @@
  */
 
 
-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;
 
 
 
 
-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)
 	{
@@ -640,23 +39,9 @@
 		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);
+	assert(Morigin.NumPlatforms > Morigin.NumBoxesInPlatform);
 
-#ifndef DEBUG
-	program_alarm();
-#endif
-	search_depth(maps, 0, new_movements,
-		num_new_movements, 100. / num_new_movements,
-		0);
+	init_os();
 
-	return 0;
-
+	return solve_map(Morigin);
 }