X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=range.c;h=3f2bdaccfa7adc1767048765d6f44b828ba1ae52;hb=fa64ed3e875e005452e5ecd639bd1d6099387bd7;hp=a82acb34593f434fd5f3e892897dd3c314c0645b;hpb=d14999949c018255b5100a317ea1b7b9b74dfc6e;p=sgt-puzzles.git diff --git a/range.c b/range.c index a82acb3..3f2bdac 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 @@ -49,7 +66,7 @@ #define setmember(obj, field) ( (obj) . field = field ) -char *nfmtstr(int n, char *fmt, ...) { +static char *nfmtstr(int n, char *fmt, ...) { va_list va; char *ret = snewn(n+1, char); va_start(va, fmt); @@ -83,7 +100,7 @@ struct game_state { }; #define DEFAULT_PRESET 0 -static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}}; +static struct game_params range_presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}}; /* rationale: I want all four combinations of {odd/even, odd/even}, as * they play out differently with respect to two-way symmetry. I also * want them to be generated relatively fast yet still be large enough @@ -95,11 +112,11 @@ static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}}; static game_params *default_params(void) { game_params *ret = snew(game_params); - *ret = presets[DEFAULT_PRESET]; /* structure copy */ + *ret = range_presets[DEFAULT_PRESET]; /* structure copy */ 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 */ @@ -108,10 +125,15 @@ static game_params *dup_params(game_params *params) static int game_fetch_preset(int i, char **name, game_params **params) { - if (i < 0 || i >= lenof(presets)) return FALSE; + game_params *ret; + + if (i < 0 || i >= lenof(range_presets)) return FALSE; - *name = nfmtstr(40, "%d x %d", presets[i].w, presets[i].h); - *params = dup_params(&presets[i]); + ret = default_params(); + *ret = range_presets[i]; /* struct copy */ + *params = ret; + + *name = nfmtstr(40, "%d x %d", range_presets[i].w, range_presets[i].h); return TRUE; } @@ -133,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; @@ -164,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); @@ -177,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; @@ -287,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); @@ -314,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, @@ -322,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); @@ -333,19 +355,19 @@ static move *solve_internal(game_state *state, move *base, int diff) return moves; } +static reasoning *const reasonings[] = { + solver_reasoning_not_too_big, + solver_reasoning_adjacency, + solver_reasoning_connectedness, + solver_reasoning_recursion +}; + static move *do_solve(game_state *state, int nclues, const square *clues, move *move_buffer, int difficulty) { - reasoning *reasonings[] = { - solver_reasoning_not_too_big, - solver_reasoning_adjacency, - solver_reasoning_connectedness, - solver_reasoning_recursion - }; - struct move *buf = move_buffer, *oldbuf; int i; @@ -366,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; @@ -610,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); @@ -667,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; @@ -888,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"; @@ -1055,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; @@ -1087,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); @@ -1129,12 +1152,12 @@ 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; char *ret, *buf, *gridline; @@ -1144,7 +1167,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); @@ -1201,14 +1224,13 @@ static char *game_text_format(game_state *state) struct game_ui { puzzle_size r, c; /* cursor position */ unsigned int cursor_show: 1; - unsigned int cheated: 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; - ui->cursor_show = ui->cheated = FALSE; + ui->cursor_show = FALSE; return ui; } @@ -1217,14 +1239,13 @@ 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 dupstr(ui->cheated ? "1" : "0"); + return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { - ui->cheated = (*encoding == '1'); } typedef struct drawcell { @@ -1245,12 +1266,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, 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; @@ -1308,7 +1332,36 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, 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]; } @@ -1325,7 +1378,14 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, ret = nfmtstr(40, "%c,%d,%d", buf->colour == M_BLACK ? 'B' : 'W', buf->square.r, buf->square.c); - ui->cheated = TRUE; /* you are being naughty ;-) */ + /* We used to set a flag here in the game_ui indicating + * that the player had used the hint function. I (SGT) + * retired it, on grounds of consistency with other games + * (most of these games will still flash to indicate + * completion if you solved and undid it, so why not if + * you got a hint?) and because the flash is as much about + * checking you got it all right than about congratulating + * you on a job well done. */ } sfree(buf); return ret; @@ -1349,9 +1409,10 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, 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; @@ -1403,14 +1464,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 */ @@ -1420,7 +1517,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; @@ -1458,28 +1555,32 @@ 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) { - if (newstate->has_cheated) ui->cheated = TRUE; } -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 && !ui->cheated) + if (!from->was_solved && to->was_solved && !to->has_cheated) return FLASH_TIME; return 0.0F; } +static int game_status(const game_state *state) +{ + return state->was_solved ? +1 : 0; +} + /* ---------------------------------------------------------------------- * Drawing routines. */ @@ -1499,7 +1600,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; @@ -1507,7 +1608,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; } @@ -1537,7 +1638,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); @@ -1573,8 +1674,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; @@ -1592,8 +1694,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); } @@ -1625,17 +1725,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); @@ -1646,10 +1744,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 */ @@ -1659,7 +1757,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); @@ -1667,7 +1765,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; @@ -1727,6 +1825,7 @@ struct game const thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,