Apply some optimisation to Undead's get_unique() function, which was

not only enumerating all possible arrangements of monsters along a
sight-line in O(3^n) time, but also allocated memory for them all and
then does a quadratic-time loop over that list to find arrangements
with a unique visibility count from both ends. Spotted by the new
'make test', which observed that 7x7dn#517035041807425 took 45 seconds
to generate.

This revised version still does the initial O(3^n) enumeration, which
can probably be got rid of as well with a bit more thought, but it now
doesn't allocate nearly so much memory and it spots uniques
efficiently. The above random seed now generates the same game ID in
less than a second, which drops this puzzle off the 'make test' hit
list of things most obviously needing speedup.

[originally from svn r9826]

diff --git a/undead.c b/undead.c
index 4cc4a124ad91ce63ef7530e9bae7c6a32255a246..e38c96844d33107cde490b0d2eba1a5d2f046e82 100644 (file)
--- a/undead.c
+++ b/undead.c
@@ -576,8 +576,9 @@ int next_list(struct guess *g, int pos) {
 
 void get_unique(game_state *state, int counter, random_state *rs) {
 
-    int p,i,c,count_uniques;
+    int p,i,c,pathlimit,count_uniques;
     struct guess path_guess;
+    int *view_count;
     
     struct entry {
         struct entry *link;
@@ -589,10 +590,10 @@ void get_unique(game_state *state, int counter, random_state *rs) {
     struct {
         struct entry *head;
         struct entry *node;
-    } views, single_views, loop_views, test_views;
+    } views, single_views, test_views;
 
     struct entry test_entry;
-    
+
     path_guess.length = state->common->paths[counter].num_monsters;
     path_guess.guess = snewn(path_guess.length,int);
     path_guess.possible = snewn(path_guess.length,int);
@@ -615,20 +616,17 @@ void get_unique(game_state *state, int counter, random_state *rs) {
 
     views.head = NULL;
     views.node = NULL;
+
+    pathlimit = state->common->paths[counter].length + 1;
+    view_count = snewn(pathlimit*pathlimit, int);
+    for (i = 0; i < pathlimit*pathlimit; i++)
+        view_count[i] = 0;
     
     do {
-        int mirror;
+        int mirror, start_view, end_view;
         
-        views.node = snewn(1,struct entry);
-        views.node->link = views.head;
-        views.node->guess = snewn(path_guess.length,int);
-        views.head = views.node;
-        views.node->start_view = 0;
-        views.node->end_view = 0;
-        memcpy(views.node->guess, path_guess.guess,
-               path_guess.length*sizeof(int));
-
         mirror = FALSE;
+        start_view = 0;
         for (p=0;p<state->common->paths[counter].length;p++) {
             if (state->common->paths[counter].p[p] == -1) mirror = TRUE;
             else {
@@ -636,17 +634,18 @@ void get_unique(game_state *state, int counter, random_state *rs) {
                     if (state->common->paths[counter].p[p] ==
                         state->common->paths[counter].mapping[i]) {
                         if (path_guess.guess[i] == 1 && mirror == TRUE)
-                            views.node->start_view++;
+                            start_view++;
                         if (path_guess.guess[i] == 2 && mirror == FALSE)
-                            views.node->start_view++;
+                            start_view++;
                         if (path_guess.guess[i] == 4)
-                            views.node->start_view++;
+                            start_view++;
                         break;
                     }
                 }
             }
         }
         mirror = FALSE;
+        end_view = 0;
         for (p=state->common->paths[counter].length-1;p>=0;p--) {
             if (state->common->paths[counter].p[p] == -1) mirror = TRUE;
             else {
@@ -654,16 +653,31 @@ void get_unique(game_state *state, int counter, random_state *rs) {
                     if (state->common->paths[counter].p[p] ==
                         state->common->paths[counter].mapping[i]) {
                         if (path_guess.guess[i] == 1 && mirror == TRUE)
-                            views.node->end_view++;
+                            end_view++;
                         if (path_guess.guess[i] == 2 && mirror == FALSE)
-                            views.node->end_view++;
+                            end_view++;
                         if (path_guess.guess[i] == 4)
-                            views.node->end_view++;
+                            end_view++;
                         break;
                     }
                 }
             }
         }
+
+        assert(start_view >= 0 && start_view < pathlimit);
+        assert(end_view >= 0 && end_view < pathlimit);
+        i = start_view * pathlimit + end_view;
+        view_count[i]++;
+        if (view_count[i] == 1) {
+            views.node = snewn(1,struct entry);
+            views.node->link = views.head;
+            views.node->guess = snewn(path_guess.length,int);
+            views.head = views.node;
+            views.node->start_view = start_view;
+            views.node->end_view = end_view;
+            memcpy(views.node->guess, path_guess.guess,
+                   path_guess.length*sizeof(int));
+        }
     } while (next_list(&path_guess, path_guess.length-1));
 
     /*  extract single entries from view list */
@@ -680,17 +694,8 @@ void get_unique(game_state *state, int counter, random_state *rs) {
     while (test_views.head != NULL) {
         test_views.node = test_views.head;
         test_views.head = test_views.head->link;
-        c = 0;
-        loop_views.head = views.head;
-        loop_views.node = views.node;
-        while (loop_views.head != NULL) {
-            loop_views.node = loop_views.head;
-            loop_views.head = loop_views.head->link;
-            if (test_views.node->start_view == loop_views.node->start_view &&
-                test_views.node->end_view == loop_views.node->end_view)
-                c++;
-        }
-        if (c == 1) {
+        i = test_views.node->start_view * pathlimit + test_views.node->end_view;
+        if (view_count[i] == 1) {
             single_views.node = snewn(1,struct entry);
             single_views.node->link = single_views.head;
             single_views.node->guess = snewn(path_guess.length,int);
@@ -703,6 +708,8 @@ void get_unique(game_state *state, int counter, random_state *rs) {
         }
     }
 
+    sfree(view_count);
+
     if (count_uniques > 0) {
         test_entry.start_view = 0;
         test_entry.end_view = 0;