shithub: puzzles

Download patch

ref: ac6fd11ddad3cc52adeeb16a49f71666549fa547
parent: ff8a9fbc541b714e64fc089f75ec712a04cbd90f
author: Simon Tatham <anakin@pobox.com>
date: Tue Sep 9 10:20:10 EDT 2014 

Improve connectedness-error highlighting in Range.

The previous approach of scanning the grid by depth-first search was
fine for deciding whether it was connected, but not so good for
pointing out where the mistake was in the grid. Replaced that code
with a dsf-based version, which identifies all connected components so
that an easy followup pass can highlight all but the largest as
erroneous.

[originally from svn r10223]


--- a/range.R
+++ b/range.R
@@ -1,10 +1,12 @@
 # -*- makefile -*-
 
-range    : [X] GTK COMMON range range-icon|no-icon
+RANGE_EXTRA = dsf
 
-range    : [G] WINDOWS COMMON range range.res|noicon.res
+range    : [X] GTK COMMON range RANGE_EXTRA range-icon|no-icon
 
-ALL += range[COMBINED]
+range    : [G] WINDOWS COMMON range RANGE_EXTRA range.res|noicon.res
+
+ALL += range[COMBINED] RANGE_EXTRA
 
 !begin am gtk
 GAMES += range
--- a/range.c
+++ b/range.c
@@ -1364,6 +1364,7 @@
 static int find_errors(const game_state *state, int *report)
 {
     int const w = state->params.w, h = state->params.h, n = w * h;
+    int *dsf;
 
     int r, c, i;
 
@@ -1415,14 +1416,50 @@
             }
         }
 
-    for (i = 0; i < n; ++i) if (dup->grid[i] != BLACK) dup->grid[i] = WHITE;
-    if (nblack + dfs_count_white(dup, any_white_cell) < n) {
+    /*
+     * Check that all the white cells form a single connected component.
+     */
+    dsf = snew_dsf(n);
+    for (r = 0; r < h-1; ++r)
+        for (c = 0; c < w; ++c)
+            if (state->grid[r*w+c] != BLACK &&
+                state->grid[(r+1)*w+c] != BLACK)
+                dsf_merge(dsf, r*w+c, (r+1)*w+c);
+    for (r = 0; r < h; ++r)
+        for (c = 0; c < w-1; ++c)
+            if (state->grid[r*w+c] != BLACK &&
+                state->grid[r*w+(c+1)] != BLACK)
+                dsf_merge(dsf, r*w+c, r*w+(c+1));
+    if (nblack + dsf_size(dsf, any_white_cell) < n) {
+        int biggest, canonical;
+
         if (!report) {
             printf("dfs fail at %d\n", any_white_cell);
             goto found_error;
         }
-        for (i = 0; i < n; ++i) if (state->grid[i] != BLACK) report[i] = TRUE;
+
+        /*
+         * Report this error by choosing one component to be the
+         * canonical one (we pick the largest, arbitrarily
+         * tie-breaking towards lower array indices) and highlighting
+         * as an error any square in a different component.
+         */
+        canonical = -1;
+        biggest = 0;
+        for (i = 0; i < n; ++i)
+            if (state->grid[i] != BLACK) {
+                int size = dsf_size(dsf, i);
+                if (size > biggest) {
+                    biggest = size;
+                    canonical = dsf_canonify(dsf, i);
+                }
+            }
+
+        for (i = 0; i < n; ++i)
+            if (state->grid[i] != BLACK && dsf_canonify(dsf, i) != canonical)
+                report[i] = TRUE;
     }
+    sfree(dsf);
 
     free_game(dup);
     return FALSE; /* if report != NULL, this is ignored */