X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/6f2d8d7c70f6bbf8bce982ced1fa879e967afbbf..41184c244487c6f50cd174a0a913b02c5255aab9:/pattern.c diff --git a/pattern.c b/pattern.c index 55f840f..f8e8fc5 100644 --- a/pattern.c +++ b/pattern.c @@ -1,9 +1,5 @@ /* * pattern.c: the pattern-reconstruction game known as `nonograms'. - * - * TODO before checkin: - * - * - make some sort of stab at number-of-numbers judgment */ #include @@ -15,9 +11,6 @@ #include "puzzles.h" -#define max(x,y) ( (x)>(y) ? (x):(y) ) -#define min(x,y) ( (x)<(y) ? (x):(y) ) - enum { COL_BACKGROUND, COL_EMPTY, @@ -52,7 +45,7 @@ struct game_state { unsigned char *grid; int rowsize; int *rowdata, *rowlen; - int completed; + int completed, cheated; }; #define FLASH_TIME 0.13F @@ -66,24 +59,26 @@ static game_params *default_params(void) return ret; } +static const struct game_params pattern_presets[] = { + {10, 10}, + {15, 15}, + {20, 20}, +#ifndef SLOW_SYSTEM + {25, 25}, + {30, 30}, +#endif +}; + static int game_fetch_preset(int i, char **name, game_params **params) { game_params *ret; char str[80]; - static const struct { int x, y; } values[] = { - {10, 10}, - {15, 15}, - {20, 20}, - {25, 25}, - {30, 30}, - }; - - if (i < 0 || i >= lenof(values)) + + if (i < 0 || i >= lenof(pattern_presets)) return FALSE; ret = snew(game_params); - ret->w = values[i].x; - ret->h = values[i].y; + *ret = pattern_presets[i]; sprintf(str, "%dx%d", ret->w, ret->h); @@ -104,9 +99,8 @@ static game_params *dup_params(game_params *params) return ret; } -static game_params *decode_params(char const *string) +static void decode_params(game_params *ret, char const *string) { - game_params *ret = default_params(); char const *p = string; ret->w = atoi(p); @@ -118,11 +112,9 @@ static game_params *decode_params(char const *string) } else { ret->h = ret->w; } - - return ret; } -static char *encode_params(game_params *params) +static char *encode_params(game_params *params, int full) { char ret[400]; int len; @@ -173,12 +165,8 @@ static game_params *custom_params(config_item *cfg) static char *validate_params(game_params *params) { - if (params->w <= 0 && params->h <= 0) + if (params->w <= 0 || params->h <= 0) return "Width and height must both be greater than zero"; - if (params->w <= 0) - return "Width must be greater than zero"; - if (params->h <= 0) - return "Height must be greater than zero"; return NULL; } @@ -476,19 +464,37 @@ static unsigned char *generate_soluble(random_state *rs, int w, int h) return grid; } -static char *new_game_seed(game_params *params, random_state *rs, - game_aux_info **aux) +struct game_aux_info { + int w, h; + unsigned char *grid; +}; + +static char *new_game_desc(game_params *params, random_state *rs, + game_aux_info **aux, int interactive) { unsigned char *grid; int i, j, max, rowlen, *rowdata; - char intbuf[80], *seed; - int seedlen, seedpos; + char intbuf[80], *desc; + int desclen, descpos; grid = generate_soluble(rs, params->w, params->h); max = max(params->w, params->h); rowdata = snewn(max, int); /* + * Save the solved game in an aux_info. + */ + { + game_aux_info *ai = snew(game_aux_info); + + ai->w = params->w; + ai->h = params->h; + ai->grid = grid; + + *aux = ai; + } + + /* * Seed is a slash-separated list of row contents; each row * contents section is a dot-separated list of integers. Row * contents are listed in the order (columns left to right, @@ -498,7 +504,7 @@ static char *new_game_seed(game_params *params, random_state *rs, * passes, first computing the seed size and then writing it * out. */ - seedlen = 0; + desclen = 0; for (i = 0; i < params->w + params->h; i++) { if (i < params->w) rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); @@ -507,14 +513,14 @@ static char *new_game_seed(game_params *params, random_state *rs, params->w, 1); if (rowlen > 0) { for (j = 0; j < rowlen; j++) { - seedlen += 1 + sprintf(intbuf, "%d", rowdata[j]); + desclen += 1 + sprintf(intbuf, "%d", rowdata[j]); } } else { - seedlen++; + desclen++; } } - seed = snewn(seedlen, char); - seedpos = 0; + desc = snewn(desclen, char); + descpos = 0; for (i = 0; i < params->w + params->h; i++) { if (i < params->w) rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w); @@ -523,30 +529,31 @@ static char *new_game_seed(game_params *params, random_state *rs, params->w, 1); if (rowlen > 0) { for (j = 0; j < rowlen; j++) { - int len = sprintf(seed+seedpos, "%d", rowdata[j]); + int len = sprintf(desc+descpos, "%d", rowdata[j]); if (j+1 < rowlen) - seed[seedpos + len] = '.'; + desc[descpos + len] = '.'; else - seed[seedpos + len] = '/'; - seedpos += len+1; + desc[descpos + len] = '/'; + descpos += len+1; } } else { - seed[seedpos++] = '/'; + desc[descpos++] = '/'; } } - assert(seedpos == seedlen); - assert(seed[seedlen-1] == '/'); - seed[seedlen-1] = '\0'; + assert(descpos == desclen); + assert(desc[desclen-1] == '/'); + desc[desclen-1] = '\0'; sfree(rowdata); - return seed; + return desc; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { - assert(!"Shouldn't happen"); + sfree(aux->grid); + sfree(aux); } -static char *validate_seed(game_params *params, char *seed) +static char *validate_desc(game_params *params, char *desc) { int i, n, rowspace; char *p; @@ -557,10 +564,10 @@ static char *validate_seed(game_params *params, char *seed) else rowspace = params->w + 1; - if (*seed && isdigit((unsigned char)*seed)) { + if (*desc && isdigit((unsigned char)*desc)) { do { - p = seed; - while (seed && isdigit((unsigned char)*seed)) seed++; + p = desc; + while (desc && isdigit((unsigned char)*desc)) desc++; n = atoi(p); rowspace -= n+1; @@ -570,15 +577,15 @@ static char *validate_seed(game_params *params, char *seed) else return "at least one row contains more numbers than will fit"; } - } while (*seed++ == '.'); + } while (*desc++ == '.'); } else { - seed++; /* expect a slash immediately */ + desc++; /* expect a slash immediately */ } - if (seed[-1] == '/') { + if (desc[-1] == '/') { if (i+1 == params->w + params->h) return "too many row/column specifications"; - } else if (seed[-1] == '\0') { + } else if (desc[-1] == '\0') { if (i+1 < params->w + params->h) return "too few row/column specifications"; } else @@ -588,7 +595,7 @@ static char *validate_seed(game_params *params, char *seed) return NULL; } -static game_state *new_game(game_params *params, char *seed) +static game_state *new_game(midend_data *me, game_params *params, char *desc) { int i; char *p; @@ -604,19 +611,19 @@ static game_state *new_game(game_params *params, char *seed) state->rowdata = snewn(state->rowsize * (state->w + state->h), int); state->rowlen = snewn(state->w + state->h, int); - state->completed = FALSE; + state->completed = state->cheated = FALSE; for (i = 0; i < params->w + params->h; i++) { state->rowlen[i] = 0; - if (*seed && isdigit((unsigned char)*seed)) { + if (*desc && isdigit((unsigned char)*desc)) { do { - p = seed; - while (seed && isdigit((unsigned char)*seed)) seed++; + p = desc; + while (desc && isdigit((unsigned char)*desc)) desc++; state->rowdata[state->rowsize * i + state->rowlen[i]++] = atoi(p); - } while (*seed++ == '.'); + } while (*desc++ == '.'); } else { - seed++; /* expect a slash immediately */ + desc++; /* expect a slash immediately */ } } @@ -642,6 +649,7 @@ static game_state *dup_game(game_state *state) (ret->w + ret->h) * sizeof(int)); ret->completed = state->completed; + ret->cheated = state->cheated; return ret; } @@ -654,6 +662,73 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *ai, + char **error) +{ + game_state *ret; + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + /* + * If we already have the solved state in an aux_info, copy it + * out. + */ + if (ai) { + + assert(ret->w == ai->w); + assert(ret->h == ai->h); + memcpy(ret->grid, ai->grid, ai->w * ai->h); + + } else { + int w = state->w, h = state->h, i, j, done_any, max; + unsigned char *matrix, *workspace; + int *rowdata; + + matrix = snewn(w*h, unsigned char); + max = max(w, h); + workspace = snewn(max*3, unsigned char); + rowdata = snewn(max+1, int); + + memset(matrix, 0, w*h); + + do { + done_any = 0; + for (i=0; irowdata + state->rowsize*(w+i), + max*sizeof(int)); + rowdata[state->rowlen[w+i]] = 0; + done_any |= do_row(workspace, workspace+max, workspace+2*max, + matrix+i*w, w, 1, rowdata); + } + for (i=0; irowdata + state->rowsize*i, max*sizeof(int)); + rowdata[state->rowlen[i]] = 0; + done_any |= do_row(workspace, workspace+max, workspace+2*max, + matrix+i, h, w, rowdata); + } + } while (done_any); + + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) { + int c = (matrix[i*w+j] == BLOCK ? GRID_FULL : + matrix[i*w+j] == DOT ? GRID_EMPTY : GRID_UNKNOWN); + ret->grid[i*w+j] = c; + if (c == GRID_UNKNOWN) + ret->completed = FALSE; + } + } + + if (!ret->completed) { + free_game(ret); + *error = "Solving algorithm cannot complete this puzzle"; + return NULL; + } + } + + return ret; +} + static char *game_text_format(game_state *state) { return NULL; @@ -683,11 +758,12 @@ static void free_ui(game_ui *ui) sfree(ui); } -static game_state *make_move(game_state *from, game_ui *ui, - int x, int y, int button) -{ +static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, + int x, int y, int button) { game_state *ret; + button &= ~MOD_MASK; + x = FROMCOORD(from->w, x); y = FROMCOORD(from->h, y); @@ -1003,15 +1079,16 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, } static float game_anim_length(game_state *oldstate, - game_state *newstate, int dir) + game_state *newstate, int dir, game_ui *ui) { return 0.0F; } static float game_flash_length(game_state *oldstate, - game_state *newstate, int dir) + game_state *newstate, int dir, game_ui *ui) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1021,6 +1098,11 @@ static int game_wants_statusbar(void) return FALSE; } +static int game_timing_state(game_state *state) +{ + return TRUE; +} + #ifdef COMBINED #define thegame pattern #endif @@ -1035,12 +1117,13 @@ const struct game thegame = { dup_params, TRUE, game_configure, custom_params, validate_params, - new_game_seed, + new_game_desc, game_free_aux_info, - validate_seed, + validate_desc, new_game, dup_game, free_game, + TRUE, solve_game, FALSE, game_text_format, new_ui, free_ui, @@ -1053,6 +1136,8 @@ const struct game thegame = { game_anim_length, game_flash_length, game_wants_statusbar, + FALSE, game_timing_state, + 0, /* mouse_priorities */ }; #ifdef STANDALONE_SOLVER @@ -1097,7 +1182,7 @@ int main(int argc, char **argv) game_params *p; game_state *s; int recurse = TRUE; - char *id = NULL, *seed, *err; + char *id = NULL, *desc, *err; int y, x; int grade = FALSE; @@ -1116,20 +1201,21 @@ int main(int argc, char **argv) return 1; } - seed = strchr(id, ':'); - if (!seed) { + desc = strchr(id, ':'); + if (!desc) { fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); return 1; } - *seed++ = '\0'; + *desc++ = '\0'; - p = decode_params(id); - err = validate_seed(p, seed); + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); if (err) { fprintf(stderr, "%s: %s\n", argv[0], err); return 1; } - s = new_game(p, seed); + s = new_game(NULL, p, desc); { int w = p->w, h = p->h, i, j, done_any, max;