# HG changeset patch
# User viric@llimona
# Date 1171721670 -3600
# Node ID cd27cb41037563e37491f3953f84b427b9e0cdea
# Parent  545f73869d6518e8a91c001b84c2ffbf7877007f
Recursivity changed into a loop. Now the state is loaded on boot, and saved on TERM.

diff -r 545f73869d65 -r cd27cb410375 Makefile
--- a/Makefile	Fri Feb 16 23:53:32 2007 +0100
+++ b/Makefile	Sat Feb 17 15:14:30 2007 +0100
@@ -1,11 +1,11 @@
 CC=gcc
 
 # DEBUG for gprof
-CFLAGS=-pedantic -Wall -g -pg #-DDEBUG
-LDFLAGS=-pg -Wall
+#CFLAGS?=-pedantic -Wall -g -pg #-DDEBUG
+#LDFLAGS=-pg -Wall
 #
 # DEBUG
-CFLAGS=-pedantic -Wall -g #-DDEBUG
-LDFLAGS=-Wall
+CFLAGS?=-pedantic -Wall -g #-DDEBUG
+LDFLAGS?=-Wall
 
 include Makefile.deps
diff -r 545f73869d65 -r cd27cb410375 algorithm.c
--- a/algorithm.c	Fri Feb 16 23:53:32 2007 +0100
+++ b/algorithm.c	Sat Feb 17 15:14:30 2007 +0100
@@ -1,5 +1,6 @@
 #include <assert.h>
 #include <string.h>
+#include <stdlib.h>
 #include "general.h"
 
 /* Variables related to the showing of information by os */
@@ -425,97 +426,151 @@
 }
 
 
-
-static int search_depth(struct Map maps[], int depth,
-	struct BoxMove movements[],
-	int num_movements, float percent, float total_percent)
+static void update_depth_counters(const int depth)
 {
-	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++)
+struct Map *all_maps;
+struct BoxMove *all_movements; /* DEPTH movements of MAX_MOVES */
+int *all_mov_tries; /* The actual step in movements for every depth */
+int *all_mov_max; /* Maximum of movements per all_movement element */
+float *percent;
+float *percent_part;
+int depth;
+
+int search_loop(const struct Map *origin)
+{
+	int found; /* bool */
+
+	all_maps = malloc(sizeof(*all_maps) * (MAX_STEPS+1));
+	all_movements = malloc(sizeof(*all_movements)*MAX_MOVES*(MAX_STEPS+1));
+	all_mov_tries = malloc(sizeof(*all_mov_tries)*(MAX_STEPS+1));
+	all_mov_max = malloc(sizeof(*all_mov_max)*(MAX_STEPS+1));
+	percent = malloc(sizeof(*percent)*(MAX_STEPS+1));
+	percent_part = malloc(sizeof(*percent)*(MAX_STEPS+1));
+
+
+	if (load_state())
+	{
+		--depth;
+		if (all_mov_tries[depth] != 0)
+			all_mov_tries[depth] = 0;
+	} else
 	{
-		CopyMap(m, &maps[depth]);
-		force_move_box(m, movements[i]);
-		if (m->NumPlatforms == m->NumBoxesInPlatform)
+		depth = 0;
+		CopyMap(&all_maps[0], origin);
+		all_mov_max[0] = get_box_movements(&all_maps[0], &all_movements[0]);
+		assert(all_mov_max[0] < MAX_MOVES);
+		assert(all_mov_max[0] > 0);
+		percent[0] = 0.;
+		percent_part[0] = 100.;
+		all_mov_tries[0] = 0;
+	}
+
+
+	found = 0;
+	do
+	{
+		struct BoxMove *new_movements = &all_movements[(depth+1)*MAX_MOVES];
+		struct BoxMove *movements = &all_movements[depth*MAX_MOVES];
+		int num_movements = all_mov_max[depth];
+		int *num_new_movements = &all_mov_max[depth+1];
+		int *step = &all_mov_tries[depth];
+		struct Map *new_map = &all_maps[depth+1];
+
+		update_depth_counters(depth);
+
+		percent_part[depth+1] = percent_part[depth] / num_movements;
+
+		CopyMap(new_map, &all_maps[depth]);
+
+		/* DEBUG */
+#if DEBUG
+		ShowMap(new_map);
+		show_tries(depth);
+		printf("Nummovs[%i]: %i\n", depth, num_movements);
+		printf("Step[%i]: %i\n", depth, *step);
+#endif
+
+		/* Now four things can happen:
+		 * - look for depth + 1
+		 * - keep looking for movements in depth
+		 * - go one depth back.
+		 * - solve the puzle */
+
+		/* Go one depth back */
+		if (*step >= num_movements)
 		{
-			PrintMove(movements[i]);
-			actual_map = &maps[depth+1];
-			show_percent_and_map();
-			return 0;
+			--depth;
+			continue;
 		}
 
-		if (is_new_map(maps, depth+1))
+		force_move_box(new_map, movements[(*step)]);
+
+		++(*step);
+
+		/* Solve the puzzle */
+		if (new_map->NumPlatforms == new_map->NumBoxesInPlatform)
 		{
-			num_new_movements = get_box_movements(m, new_movements);
-			assert(num_new_movements < MAX_MOVES);
+			PrintMoves(all_movements, all_mov_tries, depth+1);
+			actual_map = &all_maps[depth+1];
+			show_percent_and_map();
+			save_state();
+			found = 1;
+		}
+		
+		if (is_new_map(all_maps, depth+1))
+		{
+			*num_new_movements =
+				get_box_movements(new_map, new_movements);
+			assert(*num_new_movements < MAX_MOVES);
 		}
 		else
-			num_new_movements = 0;
+			*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_and_map();
-#endif
-	
-		}
-		else
+		percent[depth] = percent[depth] + percent_part[depth+1];
+		percent_to_show = percent[depth];
+
+		/* Keep looking for movements in depth */
+		if (*num_new_movements == 0)
 		{
-			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]);
-					actual_map = &maps[depth+1];
-					show_percent_and_map();
-					return 0;
-				}
-			}
+			depth_to_show = depth;
+			actual_map = &all_maps[depth];
+			continue;
 		}
-	}
-	return 1;
+
+		/* Look for depth + 1*/
+		if (depth+1 < MAX_STEPS)
+		{
+			percent[depth+1] = percent[depth];
+			all_mov_tries[depth+1] = 0;
+			++depth;
+		}
+	} while(!found && depth >= 0);
+	free(all_maps);
+	free(all_movements);
+	free(all_mov_tries);
+	free(all_mov_max);
+
+	return found;
 }
 
 
 int solve_map(const struct Map *origin)
 {
-	struct Map *maps;
 	struct BoxMove new_movements[MAX_MOVES];
 	int num_new_movements;
 	int ret;
 
-	maps = malloc(sizeof(*maps) * (MAX_STEPS+1));
-
-	CopyMap(&maps[0], origin);
-
-	num_new_movements = get_box_movements(&maps[0], new_movements);
-	assert(num_new_movements < MAX_MOVES);
-	assert(num_new_movements > 0);
-
 	init_os();
 
-	ret = search_depth(maps, 0, new_movements,
-		num_new_movements, 100. / num_new_movements,
-		0);
-	free(maps);
+	ret = search_loop(origin);
+
 	return ret;
 }
diff -r 545f73869d65 -r cd27cb410375 general.h
--- a/general.h	Fri Feb 16 23:53:32 2007 +0100
+++ b/general.h	Sat Feb 17 15:14:30 2007 +0100
@@ -13,11 +13,11 @@
 enum
 {
 	ALARM_SECONDS=1,
-	MAX_X=50,
-	MAX_Y=50,
-	MAX_MOVES=50,
+	MAX_X=13,
+	MAX_Y=13,
+	MAX_MOVES=10,
 	MAX_STEPS=50,
-	MAX_BOXES=15
+	MAX_BOXES=10
 };
 
 
@@ -79,8 +79,11 @@
 void ReadMap(struct Map *M, char *FileName);
 void ShowMap (const struct Map *M);
 void init_os();
-void PrintMove(struct BoxMove b);
+void PrintMoves(const struct BoxMove *b, const int *steps, const int depth);
 void show_percent_and_map();
+void save_state();
+int load_state();
+void show_tries(const int d);
 
 /* Functions related to map solution
  * algorithm.c */
diff -r 545f73869d65 -r cd27cb410375 os.c
--- a/os.c	Fri Feb 16 23:53:32 2007 +0100
+++ b/os.c	Sat Feb 17 15:14:30 2007 +0100
@@ -15,6 +15,14 @@
 int max_depth_period = 0;
 struct Map * actual_map = NULL;
 
+/* The algorithm data */
+extern struct Map *all_maps;
+extern struct BoxMove *all_movements; /* DEPTH movements of MAX_MOVES */
+extern int *all_mov_tries; /* The actual step in movements for every depth */
+extern int *all_mov_max; /* Maximum of movements per all_movement element */
+extern float *percent;
+extern float *percent_part;
+extern int depth;
 
 void ReadMap(struct Map *M, char *FileName)
 {
@@ -129,9 +137,45 @@
 
 }
 
-void PrintMove(const struct BoxMove b)
+void PrintMoves(const struct BoxMove *b, const int *steps, const int depth)
 {
-	fprintf(stdout,"Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y);
+	int i;
+	int offset;
+	char *dir;
+
+	/* The first isn't a movement. Movements are stored from b[1] and on */
+	for (i=0; i < depth; ++i)
+	{
+		/* the steps are incremented after try. So to find the movement,
+		 * we should substract 1. */
+		offset = i*MAX_MOVES + steps[i] -1;
+		if (b[offset].dir.x == 0 && 
+			b[offset].dir.y == 1)
+			dir = "down";
+		else if (b[offset].dir.x == 0 && 
+			b[offset].dir.y == -1)
+			dir = "up";
+		else if (b[offset].dir.x == -1 && 
+			b[offset].dir.y == 0)
+			dir = "left";
+		else if (b[offset].dir.x == 1 && 
+			b[offset].dir.y == 0)
+			dir = "right";
+		else
+			dir = "unknown";
+
+		fprintf(stdout,"Box: %i, Direction: %s\n",
+				b[offset].box, dir);
+	}
+}
+
+void show_tries(const int d)
+{
+	int i;
+
+	for(i=0; i<=d; ++i)
+		printf("%i/%i,", all_mov_tries[i], all_mov_max[i]);
+	putchar('\n');
 }
 
 void show_percent_and_map()
@@ -140,6 +184,7 @@
 		min_depth_period, max_depth_period);
 	if(actual_map != NULL)
 		ShowMap(actual_map);
+	show_tries(min_depth_period);
 	fflush(stdout);
 	min_depth_period = MAX_STEPS;
 	max_depth_period = 0;
@@ -184,10 +229,65 @@
         assert(result == 0);
 }
 
+void save_state()
+{
+	FILE *f;
+
+	f = fopen("state.raw", "w");
+	fwrite(all_maps, sizeof(*all_maps), MAX_STEPS+1, f);
+	fwrite(all_movements, sizeof(*all_movements), MAX_MOVES*(MAX_STEPS+1), f);
+	fwrite(all_mov_tries, sizeof(*all_mov_tries), MAX_STEPS+1, f);
+	fwrite(all_mov_max, sizeof(*all_mov_max), MAX_STEPS+1, f);
+	fwrite(percent, sizeof(*percent), MAX_STEPS+1, f);
+	fwrite(percent_part, sizeof(*percent_part), MAX_STEPS+1, f);
+	fwrite(&depth, sizeof(depth), 1, f);
+	fclose(f);
+}
+
+int load_state()
+{
+	FILE *f;
+
+	f = fopen("state.raw", "r");
+	if (f == NULL)
+		return 0;
+	fread(all_maps, sizeof(*all_maps), MAX_STEPS+1, f);
+	fread(all_movements, sizeof(*all_movements), MAX_MOVES*(MAX_STEPS+1), f);
+	fread(all_mov_tries, sizeof(*all_mov_tries), MAX_STEPS+1, f);
+	fread(all_mov_max, sizeof(*all_mov_max), MAX_STEPS+1, f);
+	fread(percent, sizeof(*percent), MAX_STEPS+1, f);
+	fread(percent_part, sizeof(*percent_part), MAX_STEPS+1, f);
+	fread(&depth, sizeof(depth), 1, f);
+	fclose(f);
+	return 1;
+}
+
+static void save_state_callback(const int parameter)
+{
+	save_state();
+	exit(0);
+}
+
+static void program_term_int()
+{
+        struct sigaction my_action;
+        int result;
+
+        my_action.sa_handler = save_state_callback;
+        my_action.sa_flags = 0;
+        memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask));
+
+        result = sigaction(SIGTERM, &my_action, NULL);
+        assert(result == 0);
+        result = sigaction(SIGINT, &my_action, NULL);
+        assert(result == 0);
+}
+
 void init_os()
 {
 #ifndef DEBUG
 	program_usr1();
+	program_term_int();
 	/* program_alarm();*/
 #endif
 }
diff -r 545f73869d65 -r cd27cb410375 sokosol.c
--- a/sokosol.c	Fri Feb 16 23:53:32 2007 +0100
+++ b/sokosol.c	Sat Feb 17 15:14:30 2007 +0100
@@ -24,11 +24,6 @@
  */
 
 
-
-
-
-
-
 int main(int argn, char **argv)
 {
 	struct Map Morigin;