Recursivity changed into a loop. Now the state is loaded on boot, and saved on TERM.
--- 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
--- 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;
}
--- 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 */
--- 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
}
--- 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;