X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/4a29930e1b9db1332c93244365db1642fcfac1cd..59dae0db4e2110631e1c7f2ea5990f6b406aff6e:/rect.c diff --git a/rect.c b/rect.c index 0940cdd..5852f59 100644 --- a/rect.c +++ b/rect.c @@ -9,18 +9,16 @@ /* * TODO: * - * - Improve on singleton removal by making an aesthetic choice - * about which of the options to take. - * - * - When doing the 3x3 trick in singleton removal, limit the size - * of the generated rectangles in accordance with the max - * rectangle size. - * - * - If we start by sorting the rectlist in descending order - * of area, we might be able to bias our random number - * selection to produce a few large rectangles more often - * than oodles of small ones? Unsure, but might be worth a - * try. + * - Improve singleton removal. + * + It would be nice to limit the size of the generated + * rectangles in accordance with existing constraints such as + * the maximum rectangle size and the one about not + * generating a rectangle the full width or height of the + * grid. + * + This could be achieved by making a less random choice + * about which of the available options to use. + * + Alternatively, we could create our rectangle and then + * split it up. */ #include @@ -103,10 +101,8 @@ static int game_fetch_preset(int i, char **name, game_params **params) case 2: w = 11, h = 11; break; case 3: w = 13, h = 13; break; case 4: w = 15, h = 15; break; -#ifndef SLOW_SYSTEM case 5: w = 17, h = 17; break; case 6: w = 19, h = 19; break; -#endif default: return FALSE; } @@ -327,7 +323,8 @@ static void remove_number_placement(int w, int h, struct numberdata *number, } static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, - game_state *result, random_state *rs) + unsigned char *hedge, unsigned char *vedge, + random_state *rs) { struct rectlist *rectpositions; int *overlaps, *rectbyplace, *workspace; @@ -751,7 +748,7 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, int placement; int number; } *rpns = NULL; - int nrpns = 0, rpnsize = 0; + size_t nrpns = 0, rpnsize = 0; int j; for (i = 0; i < nrects; i++) { @@ -852,25 +849,25 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, assert(rectpositions[i].n > 0); if (rectpositions[i].n > 1) { ret = FALSE; - } else if (result) { - /* - * Place the rectangle in its only possible position. - */ - int x, y; - struct rect *r = &rectpositions[i].rects[0]; - - for (y = 0; y < r->h; y++) { - if (r->x > 0) - vedge(result, r->x, r->y+y) = 1; - if (r->x+r->w < result->w) - vedge(result, r->x+r->w, r->y+y) = 1; - } - for (x = 0; x < r->w; x++) { - if (r->y > 0) - hedge(result, r->x+x, r->y) = 1; - if (r->y+r->h < result->h) - hedge(result, r->x+x, r->y+r->h) = 1; - } + } else if (hedge && vedge) { + /* + * Place the rectangle in its only possible position. + */ + int x, y; + struct rect *r = &rectpositions[i].rects[0]; + + for (y = 0; y < r->h; y++) { + if (r->x > 0) + vedge[(r->y+y) * w + r->x] = 1; + if (r->x+r->w < w) + vedge[(r->y+y) * w + r->x+r->w] = 1; + } + for (x = 0; x < r->w; x++) { + if (r->y > 0) + hedge[r->y * w + r->x+x] = 1; + if (r->y+r->h < h) + hedge[(r->y+r->h) * w + r->x+x] = 1; + } } } @@ -891,13 +888,26 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, * Grid generation code. */ -static struct rectlist *get_rectlist(game_params *params, int *grid) +/* + * This function does one of two things. If passed r==NULL, it + * counts the number of possible rectangles which cover the given + * square, and returns it in *n. If passed r!=NULL then it _reads_ + * *n to find an index, counts the possible rectangles until it + * reaches the nth, and writes it into r. + * + * `scratch' is expected to point to an array of 2 * params->w + * ints, used internally as scratch space (and passed in like this + * to avoid re-allocating and re-freeing it every time round a + * tight loop). + */ +static void enum_rects(game_params *params, int *grid, struct rect *r, int *n, + int sx, int sy, int *scratch) { - int rw, rh; - int x, y; - int maxarea; - struct rect *rects = NULL; - int nrects = 0, rectsize = 0; + int rw, rh, mw, mh; + int x, y, dx, dy; + int maxarea, realmaxarea; + int index = 0; + int *top, *bottom; /* * Maximum rectangle area is 1/6 of total grid size, unless @@ -908,43 +918,97 @@ static struct rectlist *get_rectlist(game_params *params, int *grid) if (maxarea < 2) maxarea = 2; - for (rw = 1; rw <= params->w; rw++) - for (rh = 1; rh <= params->h; rh++) { - if (rw * rh > maxarea) + /* + * Scan the grid to find the limits of the region within which + * any rectangle containing this point must fall. This will + * save us trawling the inside of every rectangle later on to + * see if it contains any used squares. + */ + top = scratch; + bottom = scratch + params->w; + for (dy = -1; dy <= +1; dy += 2) { + int *array = (dy == -1 ? top : bottom); + for (dx = -1; dx <= +1; dx += 2) { + for (x = sx; x >= 0 && x < params->w; x += dx) { + array[x] = -2 * params->h * dy; + for (y = sy; y >= 0 && y < params->h; y += dy) { + if (index(params, grid, x, y) == -1 && + (x == sx || dy*y <= dy*array[x-dx])) + array[x] = y; + else + break; + } + } + } + } + + /* + * Now scan again to work out the largest rectangles we can fit + * in the grid, so that we can terminate the following loops + * early once we get down to not having much space left in the + * grid. + */ + realmaxarea = 0; + for (x = 0; x < params->w; x++) { + int x2; + + rh = bottom[x] - top[x] + 1; + if (rh <= 0) + continue; /* no rectangles can start here */ + + dx = (x > sx ? -1 : +1); + for (x2 = x; x2 >= 0 && x2 < params->w; x2 += dx) + if (bottom[x2] < bottom[x] || top[x2] > top[x]) + break; + + rw = abs(x2 - x); + if (realmaxarea < rw * rh) + realmaxarea = rw * rh; + } + + if (realmaxarea > maxarea) + realmaxarea = maxarea; + + /* + * Rectangles which go right the way across the grid are + * boring, although they can't be helped in the case of + * extremely small grids. (Also they might be generated later + * on by the singleton-removal process; we can't help that.) + */ + mw = params->w - 1; + if (mw < 3) mw++; + mh = params->h - 1; + if (mh < 3) mh++; + + for (rw = 1; rw <= mw; rw++) + for (rh = 1; rh <= mh; rh++) { + if (rw * rh > realmaxarea) continue; if (rw * rh == 1) continue; - for (x = 0; x <= params->w - rw; x++) - for (y = 0; y <= params->h - rh; y++) { - if (nrects >= rectsize) { - rectsize = nrects + 256; - rects = sresize(rects, rectsize, struct rect); + for (x = max(sx - rw + 1, 0); x <= min(sx, params->w - rw); x++) + for (y = max(sy - rh + 1, 0); y <= min(sy, params->h - rh); + y++) { + /* + * Check this rectangle against the region we + * defined above. + */ + if (top[x] <= y && top[x+rw-1] <= y && + bottom[x] >= y+rh-1 && bottom[x+rw-1] >= y+rh-1) { + if (r && index == *n) { + r->x = x; + r->y = y; + r->w = rw; + r->h = rh; + return; + } + index++; } - - rects[nrects].x = x; - rects[nrects].y = y; - rects[nrects].w = rw; - rects[nrects].h = rh; - nrects++; } } - if (nrects > 0) { - struct rectlist *ret; - ret = snew(struct rectlist); - ret->rects = rects; - ret->n = nrects; - return ret; - } else { - assert(rects == NULL); /* hence no need to free */ - return NULL; - } -} - -static void free_rectlist(struct rectlist *list) -{ - sfree(list->rects); - sfree(list); + assert(!r); + *n = index; } static void place_rect(game_params *params, int *grid, struct rect r) @@ -1053,19 +1117,13 @@ static void display_grid(game_params *params, int *grid, int *numbers, int all) } #endif -struct game_aux_info { - int w, h; - unsigned char *vedge; /* (w+1) x h */ - unsigned char *hedge; /* w x (h+1) */ -}; - static char *new_game_desc(game_params *params, random_state *rs, - game_aux_info **aux, int interactive) + char **aux, int interactive) { int *grid, *numbers = NULL; - struct rectlist *list; - int x, y, y2, y2last, yx, run, i; + int x, y, y2, y2last, yx, run, i, nsquares; char *desc, *p; + int *enum_rects_scratch; game_params params2real, *params2 = ¶ms2real; while (1) { @@ -1080,47 +1138,67 @@ static char *new_game_desc(game_params *params, random_state *rs, grid = snewn(params2->w * params2->h, int); + enum_rects_scratch = snewn(2 * params2->w, int); + + nsquares = 0; for (y = 0; y < params2->h; y++) for (x = 0; x < params2->w; x++) { index(params2, grid, x, y) = -1; + nsquares++; } - list = get_rectlist(params2, grid); - assert(list != NULL); - /* - * Place rectangles until we can't any more. + * Place rectangles until we can't any more. We do this by + * finding a square we haven't yet covered, and randomly + * choosing a rectangle to cover it. */ - while (list->n > 0) { - int i, m; + + while (nsquares > 0) { + int square = random_upto(rs, nsquares); + int n; struct rect r; - /* - * Pick a random rectangle. - */ - i = random_upto(rs, list->n); - r = list->rects[i]; + x = params2->w; + y = params2->h; + for (y = 0; y < params2->h; y++) { + for (x = 0; x < params2->w; x++) { + if (index(params2, grid, x, y) == -1 && square-- == 0) + break; + } + if (x < params2->w) + break; + } + assert(x < params2->w && y < params2->h); /* - * Place it. + * Now see how many rectangles fit around this one. */ - place_rect(params2, grid, r); + enum_rects(params2, grid, NULL, &n, x, y, enum_rects_scratch); - /* - * Winnow the list by removing any rectangles which - * overlap this one. - */ - m = 0; - for (i = 0; i < list->n; i++) { - struct rect s = list->rects[i]; - if (s.x+s.w <= r.x || r.x+r.w <= s.x || - s.y+s.h <= r.y || r.y+r.h <= s.y) - list->rects[m++] = s; + if (!n) { + /* + * There are no possible rectangles covering this + * square, meaning it must be a singleton. Mark it + * -2 so we know not to keep trying. + */ + index(params2, grid, x, y) = -2; + nsquares--; + } else { + /* + * Pick one at random. + */ + n = random_upto(rs, n); + enum_rects(params2, grid, &r, &n, x, y, enum_rects_scratch); + + /* + * Place it. + */ + place_rect(params2, grid, r); + nsquares -= r.w * r.h; } - list->n = m; } - free_rectlist(list); + sfree(enum_rects_scratch); /* * Deal with singleton spaces remaining in the grid, one by @@ -1550,7 +1628,7 @@ static char *new_game_desc(game_params *params, random_state *rs, if (params->unique) ret = rect_solver(params->w, params->h, nnumbers, nd, - NULL, rs); + NULL, NULL, rs); else ret = TRUE; /* allow any number placement at all */ @@ -1595,26 +1673,31 @@ static char *new_game_desc(game_params *params, random_state *rs, } /* - * Store the rectangle data in the game_aux_info. + * Store the solution in aux. */ { - game_aux_info *ai = snew(game_aux_info); + char *ai; + int len; + + len = 2 + (params->w-1)*params->h + (params->h-1)*params->w; + ai = snewn(len, char); + + ai[0] = 'S'; - ai->w = params->w; - ai->h = params->h; - ai->vedge = snewn(ai->w * ai->h, unsigned char); - ai->hedge = snewn(ai->w * ai->h, unsigned char); + p = ai+1; for (y = 0; y < params->h; y++) - for (x = 1; x < params->w; x++) { - vedge(ai, x, y) = - index(params, grid, x, y) != index(params, grid, x-1, y); - } + for (x = 1; x < params->w; x++) + *p++ = (index(params, grid, x, y) != + index(params, grid, x-1, y) ? '1' : '0'); + for (y = 1; y < params->h; y++) - for (x = 0; x < params->w; x++) { - hedge(ai, x, y) = - index(params, grid, x, y) != index(params, grid, x, y-1); - } + for (x = 0; x < params->w; x++) + *p++ = (index(params, grid, x, y) != + index(params, grid, x, y-1) ? '1' : '0'); + + assert(p - ai == len-1); + *p = '\0'; *aux = ai; } @@ -1662,13 +1745,6 @@ static char *new_game_desc(game_params *params, random_state *rs, return desc; } -static void game_free_aux_info(game_aux_info *ai) -{ - sfree(ai->vedge); - sfree(ai->hedge); - sfree(ai); -} - static char *validate_desc(game_params *params, char *desc) { int area = params->w * params->h; @@ -1769,60 +1845,71 @@ static void free_game(game_state *state) sfree(state); } -static game_state *solve_game(game_state *state, game_state *currstate, - game_aux_info *ai, char **error) +static char *solve_game(game_state *state, game_state *currstate, + char *ai, char **error) { - game_state *ret; + unsigned char *vedge, *hedge; + int x, y, len; + char *ret, *p; + int i, j, n; + struct numberdata *nd; - if (!ai) { - int i, j, n; - struct numberdata *nd; - - /* - * Attempt the in-built solver. - */ - - /* Set up each number's (very short) candidate position list. */ - for (i = n = 0; i < state->h * state->w; i++) - if (state->grid[i]) - n++; - - nd = snewn(n, struct numberdata); - - for (i = j = 0; i < state->h * state->w; i++) - if (state->grid[i]) { - nd[j].area = state->grid[i]; - nd[j].npoints = 1; - nd[j].points = snewn(1, struct point); - nd[j].points[0].x = i % state->w; - nd[j].points[0].y = i / state->w; - j++; - } + if (ai) + return dupstr(ai); - assert(j == n); + /* + * Attempt the in-built solver. + */ - ret = dup_game(state); - ret->cheated = TRUE; + /* Set up each number's (very short) candidate position list. */ + for (i = n = 0; i < state->h * state->w; i++) + if (state->grid[i]) + n++; + + nd = snewn(n, struct numberdata); + + for (i = j = 0; i < state->h * state->w; i++) + if (state->grid[i]) { + nd[j].area = state->grid[i]; + nd[j].npoints = 1; + nd[j].points = snewn(1, struct point); + nd[j].points[0].x = i % state->w; + nd[j].points[0].y = i / state->w; + j++; + } - rect_solver(state->w, state->h, n, nd, ret, NULL); + assert(j == n); - /* - * Clean up. - */ - for (i = 0; i < n; i++) - sfree(nd[i].points); - sfree(nd); + vedge = snewn(state->w * state->h, unsigned char); + hedge = snewn(state->w * state->h, unsigned char); + memset(vedge, 0, state->w * state->h); + memset(hedge, 0, state->w * state->h); - return ret; - } + rect_solver(state->w, state->h, n, nd, hedge, vedge, NULL); - assert(state->w == ai->w); - assert(state->h == ai->h); + /* + * Clean up. + */ + for (i = 0; i < n; i++) + sfree(nd[i].points); + sfree(nd); - ret = dup_game(state); - memcpy(ret->vedge, ai->vedge, ai->w * ai->h * sizeof(unsigned char)); - memcpy(ret->hedge, ai->hedge, ai->w * ai->h * sizeof(unsigned char)); - ret->cheated = TRUE; + len = 2 + (state->w-1)*state->h + (state->h-1)*state->w; + ret = snewn(len, char); + + p = ret; + *p++ = 'S'; + for (y = 0; y < state->h; y++) + for (x = 1; x < state->w; x++) + *p++ = vedge[y*state->w+x] ? '1' : '0'; + for (y = 1; y < state->h; y++) + for (x = 0; x < state->w; x++) + *p++ = hedge[y*state->w+x] ? '1' : '0'; + *p++ = '\0'; + assert(p - ret == len); + + sfree(vedge); + sfree(hedge); return ret; } @@ -2065,6 +2152,15 @@ static void free_ui(game_ui *ui) sfree(ui); } +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + static void coord_round(float x, float y, int *xr, int *yr) { float xs, ys, xv, yv, dx, dy, dist; @@ -2149,14 +2245,16 @@ static void coord_round(float x, float y, int *xr, int *yr) } } -static void ui_draw_rect(game_state *state, game_ui *ui, - unsigned char *hedge, unsigned char *vedge, int c) +/* + * Returns TRUE if it has made any change to the grid. + */ +static int grid_draw_rect(game_state *state, + unsigned char *hedge, unsigned char *vedge, + int c, int really, + int x1, int y1, int x2, int y2) { int x, y; - int x1 = ui->x1; - int y1 = ui->y1; - int x2 = ui->x2; - int y2 = ui->y2; + int changed = FALSE; /* * Draw horizontal edges of rectangles. @@ -2169,7 +2267,9 @@ static void ui_draw_rect(game_state *state, game_ui *ui, val = c; else if (c == 1) val = 0; - index(state,hedge,x,y) = val; + changed = changed || (index(state,hedge,x,y) != val); + if (really) + index(state,hedge,x,y) = val; } /* @@ -2183,8 +2283,20 @@ static void ui_draw_rect(game_state *state, game_ui *ui, val = c; else if (c == 1) val = 0; - index(state,vedge,x,y) = val; + changed = changed || (index(state,vedge,x,y) != val); + if (really) + index(state,vedge,x,y) = val; } + + return changed; +} + +static int ui_draw_rect(game_state *state, game_ui *ui, + unsigned char *hedge, unsigned char *vedge, int c, + int really) +{ + return grid_draw_rect(state, hedge, vedge, c, really, + ui->x1, ui->y1, ui->x2, ui->y2); } static void game_changed_state(game_ui *ui, game_state *oldstate, @@ -2198,11 +2310,12 @@ struct game_drawstate { unsigned long *visible; }; -static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, - int x, int y, int button) { +static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ int xc, yc; int startdrag = FALSE, enddrag = FALSE, active = FALSE; - game_state *ret; + char buf[80], *ret; button &= ~MOD_MASK; @@ -2260,44 +2373,24 @@ static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, if (enddrag) { if (xc >= 0 && xc <= 2*from->w && yc >= 0 && yc <= 2*from->h) { - ret = dup_game(from); if (ui->dragged) { - ui_draw_rect(ret, ui, ret->hedge, ret->vedge, 1); + if (ui_draw_rect(from, ui, from->hedge, + from->vedge, 1, FALSE)) { + sprintf(buf, "R%d,%d,%d,%d", + ui->x1, ui->y1, ui->x2 - ui->x1, ui->y2 - ui->y1); + ret = dupstr(buf); + } } else { if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) { - hedge(ret,xc/2,yc/2) = !hedge(ret,xc/2,yc/2); + sprintf(buf, "H%d,%d", xc/2, yc/2); + ret = dupstr(buf); } if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) { - vedge(ret,xc/2,yc/2) = !vedge(ret,xc/2,yc/2); + sprintf(buf, "V%d,%d", xc/2, yc/2); + ret = dupstr(buf); } } - - if (!memcmp(ret->hedge, from->hedge, from->w*from->h) && - !memcmp(ret->vedge, from->vedge, from->w*from->h)) { - free_game(ret); - ret = NULL; - } - - /* - * We've made a real change to the grid. Check to see - * if the game has been completed. - */ - if (ret && !ret->completed) { - int x, y, ok; - unsigned char *correct = get_correct(ret); - - ok = TRUE; - for (x = 0; x < ret->w; x++) - for (y = 0; y < ret->h; y++) - if (!index(ret, correct, x, y)) - ok = FALSE; - - sfree(correct); - - if (ok) - ret->completed = TRUE; - } } ui->drag_start_x = -1; @@ -2315,11 +2408,84 @@ static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, if (ret) return ret; /* a move has been made */ else if (active) - return from; /* UI activity has occurred */ + return ""; /* UI activity has occurred */ else return NULL; } +static game_state *execute_move(game_state *from, char *move) +{ + game_state *ret; + int x1, y1, x2, y2, mode; + + if (move[0] == 'S') { + char *p = move+1; + int x, y; + + ret = dup_game(from); + ret->cheated = TRUE; + + for (y = 0; y < ret->h; y++) + for (x = 1; x < ret->w; x++) { + vedge(ret, x, y) = (*p == '1'); + if (*p) p++; + } + for (y = 1; y < ret->h; y++) + for (x = 0; x < ret->w; x++) { + hedge(ret, x, y) = (*p == '1'); + if (*p) p++; + } + + return ret; + + } else if (move[0] == 'R' && + sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 && + x1 >= 0 && x2 >= 0 && x1+x2 <= from->w && + y1 >= 0 && y2 >= 0 && y1+y2 <= from->h) { + x2 += x1; + y2 += y1; + mode = move[0]; + } else if ((move[0] == 'H' || move[0] == 'V') && + sscanf(move+1, "%d,%d", &x1, &y1) == 2 && + (move[0] == 'H' ? HRANGE(from, x1, y1) : + VRANGE(from, x1, y1))) { + mode = move[0]; + } else + return NULL; /* can't parse move string */ + + ret = dup_game(from); + + if (mode == 'R') { + grid_draw_rect(ret, ret->hedge, ret->vedge, 1, TRUE, x1, y1, x2, y2); + } else if (mode == 'H') { + hedge(ret,x1,y1) = !hedge(ret,x1,y1); + } else if (mode == 'V') { + vedge(ret,x1,y1) = !vedge(ret,x1,y1); + } + + /* + * We've made a real change to the grid. Check to see + * if the game has been completed. + */ + if (!ret->completed) { + int x, y, ok; + unsigned char *correct = get_correct(ret); + + ok = TRUE; + for (x = 0; x < ret->w; x++) + for (y = 0; y < ret->h; y++) + if (!index(ret, correct, x, y)) + ok = FALSE; + + sfree(correct); + + if (ok) + ret->completed = TRUE; + } + + return ret; +} + /* ---------------------------------------------------------------------- * Drawing routines. */ @@ -2476,7 +2642,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, vedge = snewn(state->w*state->h, unsigned char); memcpy(hedge, state->hedge, state->w*state->h); memcpy(vedge, state->vedge, state->w*state->h); - ui_draw_rect(state, ui, hedge, vedge, 2); + ui_draw_rect(state, ui, hedge, vedge, 2, TRUE); } else { hedge = state->hedge; vedge = state->vedge; @@ -2615,7 +2781,6 @@ const struct game thegame = { TRUE, game_configure, custom_params, validate_params, new_game_desc, - game_free_aux_info, validate_desc, new_game, dup_game, @@ -2624,8 +2789,11 @@ const struct game thegame = { TRUE, game_text_format, new_ui, free_ui, + encode_ui, + decode_ui, game_changed_state, - make_move, + interpret_move, + execute_move, game_size, game_colours, game_new_drawstate,