X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=range.c;h=4dd39b97cd499f62cbd53c0d636cb26713b92d09;hb=db313b3948d27244dd7c34c2609c66d6204d8931;hp=43231d9683361b428a2572b6f7d2cbdf51b4fa1f;hpb=3b250baa02a7332510685948bf17576c397b8ceb;p=sgt-puzzles.git

diff --git a/range.c b/range.c
index 43231d9..4dd39b9 100644
--- a/range.c
+++ b/range.c
@@ -15,7 +15,8 @@
  *    cell.  Then n must equal h + v - 1.
  */
 
-/* example instance with its encoding:
+/* example instance with its encoding and textual representation, both
+ * solved and unsolved (made by thegame.solve and thegame.text_format)
  *
  * +--+--+--+--+--+--+--+
  * |  |  |  |  | 7|  |  |
@@ -34,6 +35,22 @@
  * +--+--+--+--+--+--+--+
  *
  * 7x7:d7b3e8e5c7a7c13e4d8b4d
+ *
+ * +--+--+--+--+--+--+--+
+ * |..|..|..|..| 7|..|..|
+ * +--+--+--+--+--+--+--+
+ * | 3|..|##|..|##|..| 8|
+ * +--+--+--+--+--+--+--+
+ * |##|..|..|##|..| 5|..|
+ * +--+--+--+--+--+--+--+
+ * |..|..| 7|..| 7|##|..|
+ * +--+--+--+--+--+--+--+
+ * |..|13|..|..|..|..|..|
+ * +--+--+--+--+--+--+--+
+ * | 4|..|##|..|##|..| 8|
+ * +--+--+--+--+--+--+--+
+ * |##|..| 4|..|..|##|..|
+ * +--+--+--+--+--+--+--+
  */
 
 #include <stdio.h>
@@ -99,7 +116,7 @@ static game_params *default_params(void)
     return ret;
 }
 
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
 {
     game_params *ret = snew(game_params);
     *ret = *params; /* structure copy */
@@ -138,14 +155,14 @@ static void decode_params(game_params *params, char const *string)
     }
 }
 
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
 {
     char str[80];
     sprintf(str, "%dx%d", params->w, params->h);
     return dupstr(str);
 }
 
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
 {
     config_item *ret;
 
@@ -169,7 +186,7 @@ static config_item *game_configure(game_params *params)
     return ret;
 }
 
-static game_params *custom_params(config_item *configuration)
+static game_params *custom_params(const config_item *configuration)
 {
     game_params *ret = snew(game_params);
     ret->w = atoi(configuration[0].sval);
@@ -182,7 +199,7 @@ static game_params *custom_params(config_item *configuration)
     memcpy(dst, src, n * sizeof (type)); \
 } while (0)
 
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
 {
     game_state *ret = snew(game_state);
     int const n = state->params.w * state->params.h;
@@ -292,10 +309,10 @@ enum {
     DIFF_RECURSION
 };
 
-static move *solve_internal(game_state *state, move *base, int diff);
+static move *solve_internal(const game_state *state, move *base, int diff);
 
-static char *solve_game(game_state *orig, game_state *curpos,
-                        char *aux, char **error)
+static char *solve_game(const game_state *orig, const game_state *curpos,
+                        const char *aux, char **error)
 {
     int const n = orig->params.w * orig->params.h;
     move *const base = snewn(n, move);
@@ -319,7 +336,7 @@ static char *solve_game(game_state *orig, game_state *curpos,
     return ret;
 }
 
-static square *find_clues(game_state *state, int *ret_nclues);
+static square *find_clues(const game_state *state, int *ret_nclues);
 static move *do_solve(game_state *state,
                       int nclues,
                       const square *clues,
@@ -327,7 +344,7 @@ static move *do_solve(game_state *state,
                       int difficulty);
 
 /* new_game_desc entry point in the solver subsystem */
-static move *solve_internal(game_state *state, move *base, int diff)
+static move *solve_internal(const game_state *state, move *base, int diff)
 {
     int nclues;
     square *const clues = find_clues(state, &nclues);
@@ -371,7 +388,7 @@ static move *do_solve(game_state *state,
 
 static int runlength(puzzle_size r, puzzle_size c,
                      puzzle_size dr, puzzle_size dc,
-                     game_state *state, int colourmask)
+                     const game_state *state, int colourmask)
 {
     int const w = state->params.w, h = state->params.h;
     int sz = 0;
@@ -615,7 +632,7 @@ static move *solver_reasoning_recursion(game_state *state,
     return buf;
 }
 
-static square *find_clues(game_state *state, int *ret_nclues)
+static square *find_clues(const game_state *state, int *ret_nclues)
 {
     int r, c, i, nclues = 0;
     square *ret = snewn(state->params.w * state->params.h, struct square);
@@ -672,7 +689,7 @@ static void newdesc_compute_clues(game_state *state);
 static int newdesc_strip_clues(game_state *state, int *shuffle_1toN);
 static char *newdesc_encode_game_description(int n, puzzle_size *grid);
 
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
                            char **aux, int interactive)
 {
     int const w = params->w, h = params->h, n = w * h;
@@ -893,7 +910,7 @@ static int dfs_count_white(game_state *state, int cell)
     return k;
 }
 
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
 {
     int const w = params->w, h = params->h;
     if (w < 1) return "Error: width is less than 1";
@@ -1060,7 +1077,7 @@ static char *newdesc_encode_game_description(int area, puzzle_size *grid)
     return desc;
 }
 
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
 {
     int const n = params->w * params->h;
     int squares = 0;
@@ -1092,10 +1109,11 @@ static char *validate_desc(game_params *params, char *desc)
     return NULL;
 }
 
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+                            const char *desc)
 {
     int i;
-    char *p;
+    const char *p;
 
     int const n = params->w * params->h;
     game_state *state = snew(game_state);
@@ -1134,14 +1152,15 @@ static game_state *new_game(midend *me, game_params *params, char *desc)
  * User interface: ascii
  */
 
-static int game_can_format_as_text_now(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
 {
     return TRUE;
 }
 
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
 {
-    int cellsize, r, c, i, w_string, h_string, n_string;
+    int r, c, i, w_string, h_string, n_string;
+    char cellsize;
     char *ret, *buf, *gridline;
 
     int const w = state->params.w, h = state->params.h;
@@ -1149,7 +1168,7 @@ static char *game_text_format(game_state *state)
     cellsize = 0; /* or may be used uninitialized */
 
     for (c = 0; c < w; ++c) {
-        for (r = 1; r < h; ++r) {
+        for (r = 0; r < h; ++r) {
             puzzle_size k = state->grid[idx(r, c, w)];
             int d;
             for (d = 0; k; k /= 10, ++d);
@@ -1208,7 +1227,7 @@ struct game_ui {
     unsigned int cursor_show: 1;
 };
 
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
 {
     struct game_ui *ui = snew(game_ui);
     ui->r = ui->c = 0;
@@ -1221,12 +1240,12 @@ static void free_ui(game_ui *ui)
     sfree(ui);
 }
 
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
 {
     return NULL;
 }
 
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
 {
 }
 
@@ -1248,12 +1267,15 @@ struct game_drawstate {
 #define COORD(x) ((x) * TILESIZE + BORDER)
 #define FROMCOORD(x) (((x) - BORDER) / TILESIZE)
 
-static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds,
+static char *interpret_move(const game_state *state, game_ui *ui,
+                            const game_drawstate *ds,
                             int x, int y, int button)
 {
     enum {none, forwards, backwards, hint};
     int const w = state->params.w, h = state->params.h;
     int r = ui->r, c = ui->c, action = none, cell;
+    int shift = button & MOD_SHFT;
+    button &= ~shift;
 
     if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL;
 
@@ -1311,7 +1333,36 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate
             int i;
             for (i = 0; i < 4 && cursors[i] != button; ++i);
             assert (i < 4);
-            if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
+            if (shift) {
+                int pre_r = r, pre_c = c, do_pre, do_post;
+                cell = state->grid[idx(r, c, state->params.w)];
+                do_pre = (cell == EMPTY);
+
+                if (out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
+                    if (do_pre)
+                        return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
+                    else
+                        return NULL;
+                }
+
+                ui->r += dr[i];
+                ui->c += dc[i];
+
+                cell = state->grid[idx(ui->r, ui->c, state->params.w)];
+                do_post = (cell == EMPTY);
+
+                /* (do_pre ? "..." : "") concat (do_post ? "..." : "") */
+                if (do_pre && do_post)
+                    return nfmtstr(80, "W,%d,%dW,%d,%d",
+                                   pre_r, pre_c, ui->r, ui->c);
+                else if (do_pre)
+                    return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
+                else if (do_post)
+                    return nfmtstr(40, "W,%d,%d", ui->r, ui->c);
+                else
+                    return "";
+
+            } else if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
                 ui->r += dr[i];
                 ui->c += dc[i];
             }
@@ -1359,9 +1410,10 @@ static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate
     return NULL;
 }
 
-static int find_errors(game_state *state, int *report)
+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;
 
@@ -1413,14 +1465,50 @@ static int find_errors(game_state *state, int *report)
             }
         }
 
-    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);
+            sfree(dsf);
             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 */
@@ -1430,7 +1518,7 @@ found_error:
     return TRUE;
 }
 
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
 {
     signed int r, c, value, nchars, ntok;
     signed char what_to_do;
@@ -1468,28 +1556,28 @@ failure:
     return NULL;
 }
 
-static void game_changed_state(game_ui *ui, game_state *oldstate,
-                               game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+                               const game_state *newstate)
 {
 }
 
-static float game_anim_length(game_state *oldstate, game_state *newstate,
-                              int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+                              const game_state *newstate, int dir, game_ui *ui)
 {
     return 0.0F;
 }
 
 #define FLASH_TIME 0.7F
 
-static float game_flash_length(game_state *from, game_state *to,
-                               int dir, game_ui *ui)
+static float game_flash_length(const game_state *from,
+                               const game_state *to, int dir, game_ui *ui)
 {
     if (!from->was_solved && to->was_solved && !to->has_cheated)
         return FLASH_TIME;
     return 0.0F;
 }
 
-static int game_status(game_state *state)
+static int game_status(const game_state *state)
 {
     return state->was_solved ? +1 : 0;
 }
@@ -1513,7 +1601,7 @@ enum {
     NCOLOURS
 };
 
-static void game_compute_size(game_params *params, int tilesize,
+static void game_compute_size(const game_params *params, int tilesize,
                               int *x, int *y)
 {
     *x = (1 + params->w) * tilesize;
@@ -1521,7 +1609,7 @@ static void game_compute_size(game_params *params, int tilesize,
 }
 
 static void game_set_size(drawing *dr, game_drawstate *ds,
-                          game_params *params, int tilesize)
+                          const game_params *params, int tilesize)
 {
     ds->tilesize = tilesize;
 }
@@ -1551,7 +1639,7 @@ static drawcell makecell(puzzle_size value, int error, int cursor, int flash)
     return ret;
 }
 
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
 {
     int const w = state->params.w, h = state->params.h, n = w * h;
     struct game_drawstate *ds = snew(struct game_drawstate);
@@ -1587,8 +1675,9 @@ static int cell_eq(drawcell a, drawcell b)
 static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c,
                       drawcell cell);
 
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
-                        game_state *state, int dir, game_ui *ui,
+static void game_redraw(drawing *dr, game_drawstate *ds,
+                        const game_state *oldstate, const game_state *state,
+                        int dir, const game_ui *ui,
                         float animtime, float flashtime)
 {
     int const w = state->params.w, h = state->params.h, n = w * h;
@@ -1606,8 +1695,6 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
     if (!ds->started) {
         ds->started = TRUE;
         draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND);
-	draw_rect(dr, BORDER-1, BORDER-1,
-		  ds->tilesize*w+2, ds->tilesize*h+2, COL_GRID);
         draw_update(dr, 0, 0, wpx, hpx);
     }
 
@@ -1639,17 +1726,15 @@ static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c,
                         cell.flash || cell.cursor ?
                         COL_LOWLIGHT : COL_BACKGROUND);
 
-    draw_rect        (draw, x, y, ts, ts, colour);
-    draw_rect_outline(draw, x, y, ts, ts, COL_GRID);
+    draw_rect_outline(draw, x,     y,     ts + 1, ts + 1, COL_GRID);
+    draw_rect        (draw, x + 1, y + 1, ts - 1, ts - 1, colour);
+    if (cell.error)
+	draw_rect_outline(draw, x + 1, y + 1, ts - 1, ts - 1, COL_ERROR);
 
     switch (cell.value) {
       case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz,
 			    cell.error ? COL_ERROR : COL_USER);
-      case BLACK: break;
-      case EMPTY:
-        if (cell.error)
-            draw_circle(draw, tx, ty, dotsz / 2, COL_ERROR, COL_GRID);
-        break;
+      case BLACK: case EMPTY: break;
       default:
 	{
 	    int const colour = (cell.error ? COL_ERROR : COL_GRID);
@@ -1660,10 +1745,10 @@ static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c,
 	}
     }
 
-    draw_update(draw, x, y, ts, ts);
+    draw_update(draw, x, y, ts + 1, ts + 1);
 }
 
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
 {
     puts("warning: game_timing_state was called (this shouldn't happen)");
     return FALSE; /* the (non-existing) timer should not be running */
@@ -1673,7 +1758,7 @@ static int game_timing_state(game_state *state, game_ui *ui)
  * User interface: print
  */
 
-static void game_print_size(game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, float *x, float *y)
 {
     int print_width, print_height;
     game_compute_size(params, 800, &print_width, &print_height);
@@ -1681,7 +1766,7 @@ static void game_print_size(game_params *params, float *x, float *y)
     *y = print_height / 100.0F;
 }
 
-static void game_print(drawing *dr, game_state *state, int tilesize)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
 {
     int const w = state->params.w, h = state->params.h;
     game_drawstate ds_obj, *ds = &ds_obj;
@@ -1713,7 +1798,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize)
 struct game const thegame = {
     "Range", "games.range", "range",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,