From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/unfinished/path.c | 786 +++++++++++++++++++++++++++++ 1 file changed, 786 insertions(+) create mode 100644 apps/plugins/puzzles/src/unfinished/path.c (limited to 'apps/plugins/puzzles/src/unfinished/path.c') diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c new file mode 100644 index 0000000000..61d6c61c6a --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/path.c @@ -0,0 +1,786 @@ +/* + * Experimental grid generator for Nikoli's `Number Link' puzzle. + */ + +#include +#include +#include +#include "puzzles.h" + +/* + * 2005-07-08: This is currently a Path grid generator which will + * construct valid grids at a plausible speed. However, the grids + * are not of suitable quality to be used directly as puzzles. + * + * The basic strategy is to start with an empty grid, and + * repeatedly either (a) add a new path to it, or (b) extend one + * end of a path by one square in some direction and push other + * paths into new shapes in the process. The effect of this is that + * we are able to construct a set of paths which between them fill + * the entire grid. + * + * Quality issues: if we set the main loop to do (a) where possible + * and (b) only where necessary, we end up with a grid containing a + * few too many small paths, which therefore doesn't make for an + * interesting puzzle. If we reverse the priority so that we do (b) + * where possible and (a) only where necessary, we end up with some + * staggeringly interwoven grids with very very few separate paths, + * but the result of this is that there's invariably a solution + * other than the intended one which leaves many grid squares + * unfilled. There's also a separate problem which is that many + * grids have really boring and obvious paths in them, such as the + * entire bottom row of the grid being taken up by a single path. + * + * It's not impossible that a few tweaks might eliminate or reduce + * the incidence of boring paths, and might also find a happy + * medium between too many and too few. There remains the question + * of unique solutions, however. I fear there is no alternative but + * to write - somehow! - a solver. + * + * While I'm here, some notes on UI strategy for the parts of the + * puzzle implementation that _aren't_ the generator: + * + * - data model is to track connections between adjacent squares, + * so that you aren't limited to extending a path out from each + * number but can also mark sections of path which you know + * _will_ come in handy later. + * + * - user interface is to click in one square and drag to an + * adjacent one, thus creating a link between them. We can + * probably tolerate rapid mouse motion causing a drag directly + * to a square which is a rook move away, but any other rapid + * motion is ambiguous and probably the best option is to wait + * until the mouse returns to a square we know how to reach. + * + * - a drag causing the current path to backtrack has the effect + * of removing bits of it. + * + * - the UI should enforce at all times the constraint that at + * most two links can come into any square. + * + * - my Cunning Plan for actually implementing this: the game_ui + * contains a grid-sized array, which is copied from the current + * game_state on starting a drag. While a drag is active, the + * contents of the game_ui is adjusted with every mouse motion, + * and is displayed _in place_ of the game_state itself. On + * termination of a drag, the game_ui array is copied back into + * the new game_state (or rather, a string move is encoded which + * has precisely the set of link changes to cause that effect). + */ + +/* + * Standard notation for directions. + */ +#define L 0 +#define U 1 +#define R 2 +#define D 3 +#define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0) +#define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0) + +/* + * Perform a breadth-first search over a grid of squares with the + * colour of square (X,Y) given by grid[Y*w+X]. The search begins + * at (x,y), and finds all squares which are the same colour as + * (x,y) and reachable from it by orthogonal moves. On return: + * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if + * unreachable or a different colour + * - the returned value is the number of reachable squares, + * including (x,y) itself + * - list[0] up to list[returned value - 1] list those squares, in + * increasing order of distance from (x,y) (and in arbitrary + * order within that). + */ +static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list) +{ + int i, j, c, listsize, listdone; + + /* + * Start by clearing the output arrays. + */ + for (i = 0; i < w*h; i++) + dist[i] = list[i] = -1; + + /* + * Set up the initial list. + */ + listsize = 1; + listdone = 0; + list[0] = y*w+x; + dist[y*w+x] = 0; + c = grid[y*w+x]; + + /* + * Repeatedly process a square and add any extra squares to the + * end of list. + */ + while (listdone < listsize) { + i = list[listdone++]; + y = i / w; + x = i % w; + for (j = 0; j < 4; j++) { + int xx, yy, ii; + + xx = x + DX(j); + yy = y + DY(j); + ii = yy*w+xx; + + if (xx >= 0 && xx < w && yy >= 0 && yy < h && + grid[ii] == c && dist[ii] == -1) { + dist[ii] = dist[i] + 1; + assert(listsize < w*h); + list[listsize++] = ii; + } + } + } + + return listsize; +} + +struct genctx { + int w, h; + int *grid, *sparegrid, *sparegrid2, *sparegrid3; + int *dist, *list; + + int npaths, pathsize; + int *pathends, *sparepathends; /* 2*npaths entries */ + int *pathspare; /* npaths entries */ + int *extends; /* 8*npaths entries */ +}; + +static struct genctx *new_genctx(int w, int h) +{ + struct genctx *ctx = snew(struct genctx); + ctx->w = w; + ctx->h = h; + ctx->grid = snewn(w * h, int); + ctx->sparegrid = snewn(w * h, int); + ctx->sparegrid2 = snewn(w * h, int); + ctx->sparegrid3 = snewn(w * h, int); + ctx->dist = snewn(w * h, int); + ctx->list = snewn(w * h, int); + ctx->npaths = ctx->pathsize = 0; + ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL; + return ctx; +} + +static void free_genctx(struct genctx *ctx) +{ + sfree(ctx->grid); + sfree(ctx->sparegrid); + sfree(ctx->sparegrid2); + sfree(ctx->sparegrid3); + sfree(ctx->dist); + sfree(ctx->list); + sfree(ctx->pathends); + sfree(ctx->sparepathends); + sfree(ctx->pathspare); + sfree(ctx->extends); +} + +static int newpath(struct genctx *ctx) +{ + int n; + + n = ctx->npaths++; + if (ctx->npaths > ctx->pathsize) { + ctx->pathsize += 16; + ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int); + ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int); + ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int); + ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int); + } + return n; +} + +static int is_endpoint(struct genctx *ctx, int x, int y) +{ + int w = ctx->w, h = ctx->h, c; + + assert(x >= 0 && x < w && y >= 0 && y < h); + + c = ctx->grid[y*w+x]; + if (c < 0) + return FALSE; /* empty square is not an endpoint! */ + assert(c >= 0 && c < ctx->npaths); + if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x) + return TRUE; + return FALSE; +} + +/* + * Tries to extend a path by one square in the given direction, + * pushing other paths around if necessary. Returns TRUE on success + * or FALSE on failure. + */ +static int extend_path(struct genctx *ctx, int path, int end, int direction) +{ + int w = ctx->w, h = ctx->h; + int x, y, xe, ye, cut; + int i, j, jp, n, first, last; + + assert(path >= 0 && path < ctx->npaths); + assert(end == 0 || end == 1); + + /* + * Find the endpoint of the path and the point we plan to + * extend it into. + */ + y = ctx->pathends[path * 2 + end] / w; + x = ctx->pathends[path * 2 + end] % w; + assert(x >= 0 && x < w && y >= 0 && y < h); + + xe = x + DX(direction); + ye = y + DY(direction); + if (xe < 0 || xe >= w || ye < 0 || ye >= h) + return FALSE; /* could not extend in this direction */ + + /* + * We don't extend paths _directly_ into endpoints of other + * paths, although we don't mind too much if a knock-on effect + * of an extension is to push part of another path into a third + * path's endpoint. + */ + if (is_endpoint(ctx, xe, ye)) + return FALSE; + + /* + * We can't extend a path back the way it came. + */ + if (ctx->grid[ye*w+xe] == path) + return FALSE; + + /* + * Paths may not double back on themselves. Check if the new + * point is adjacent to any point of this path other than (x,y). + */ + for (j = 0; j < 4; j++) { + int xf, yf; + + xf = xe + DX(j); + yf = ye + DY(j); + + if (xf >= 0 && xf < w && yf >= 0 && yf < h && + (xf != x || yf != y) && ctx->grid[yf*w+xf] == path) + return FALSE; + } + + /* + * Now we're convinced it's valid to _attempt_ the extension. + * It may still fail if we run out of space to push other paths + * into. + * + * So now we can set up our temporary data structures. We will + * need: + * + * - a spare copy of the grid on which to gradually move paths + * around (sparegrid) + * + * - a second spare copy with which to remember how paths + * looked just before being cut (sparegrid2). FIXME: is + * sparegrid2 necessary? right now it's never different from + * grid itself + * + * - a third spare copy with which to do the internal + * calculations involved in reconstituting a cut path + * (sparegrid3) + * + * - something to track which paths currently need + * reconstituting after being cut, and which have already + * been cut (pathspare) + * + * - a spare copy of pathends to store the altered states in + * (sparepathends) + */ + memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int)); + memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int)); + memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int)); + for (i = 0; i < ctx->npaths; i++) + ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */ + + /* + * Working in sparegrid, actually extend the path. If it cuts + * another, begin a loop in which we restore any cut path by + * moving it out of the way. + */ + cut = ctx->sparegrid[ye*w+xe]; + ctx->sparegrid[ye*w+xe] = path; + ctx->sparepathends[path*2+end] = ye*w+xe; + ctx->pathspare[path] = 2; /* this one is sacrosanct */ + if (cut >= 0) { + assert(cut >= 0 && cut < ctx->npaths); + ctx->pathspare[cut] = 1; /* broken */ + + while (1) { + for (i = 0; i < ctx->npaths; i++) + if (ctx->pathspare[i] == 1) + break; + if (i == ctx->npaths) + break; /* we're done */ + + /* + * Path i needs restoring. So walk along its original + * track (as given in sparegrid2) and see where it's + * been cut. Where it has, surround the cut points in + * the same colour, without overwriting already-fixed + * paths. + */ + memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int)); + n = bfs(w, h, ctx->sparegrid2, + ctx->pathends[i*2] % w, ctx->pathends[i*2] / w, + ctx->dist, ctx->list); + first = last = -1; +if (ctx->sparegrid3[ctx->pathends[i*2]] != i || + ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return FALSE;/* FIXME */ + for (j = 0; j < n; j++) { + jp = ctx->list[j]; + assert(ctx->dist[jp] == j); + assert(ctx->sparegrid2[jp] == i); + + /* + * Wipe out the original path in sparegrid. + */ + if (ctx->sparegrid[jp] == i) + ctx->sparegrid[jp] = -1; + + /* + * Be prepared to shorten the path at either end if + * the endpoints have been stomped on. + */ + if (ctx->sparegrid3[jp] == i) { + if (first < 0) + first = jp; + last = jp; + } + + if (ctx->sparegrid3[jp] != i) { + int jx = jp % w, jy = jp / w; + int dx, dy; + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) { + int newp, newv; + if (!dy && !dx) + continue; /* central square */ + if (jx+dx < 0 || jx+dx >= w || + jy+dy < 0 || jy+dy >= h) + continue; /* out of range */ + newp = (jy+dy)*w+(jx+dx); + newv = ctx->sparegrid3[newp]; + if (newv >= 0 && (newv == i || + ctx->pathspare[newv] == 2)) + continue; /* can't use this square */ + ctx->sparegrid3[newp] = i; + } + } + } + + if (first < 0 || last < 0) + return FALSE; /* path is completely wiped out! */ + + /* + * Now we've covered sparegrid3 in possible squares for + * the new layout of path i. Find the actual layout + * we're going to use by bfs: we want the shortest path + * from one endpoint to the other. + */ + n = bfs(w, h, ctx->sparegrid3, first % w, first / w, + ctx->dist, ctx->list); + if (ctx->dist[last] < 2) { + /* + * Either there is no way to get between the path's + * endpoints, or the remaining endpoints simply + * aren't far enough apart to make the path viable + * any more. This means the entire push operation + * has failed. + */ + return FALSE; + } + + /* + * Write the new path into sparegrid. Also save the new + * endpoint locations, in case they've changed. + */ + jp = last; + j = ctx->dist[jp]; + while (1) { + int d; + + if (ctx->sparegrid[jp] >= 0) { + if (ctx->pathspare[ctx->sparegrid[jp]] == 2) + return FALSE; /* somehow we've hit a fixed path */ + ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */ + } + ctx->sparegrid[jp] = i; + + if (j == 0) + break; + + /* + * Now look at the neighbours of jp to find one + * which has dist[] one less. + */ + for (d = 0; d < 4; d++) { + int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d); + if (jx >= 0 && jx < w && jy >= 0 && jy < w && + ctx->dist[jy*w+jx] == j-1) { + jp = jy*w+jx; + j--; + break; + } + } + assert(d < 4); + } + + ctx->sparepathends[i*2] = first; + ctx->sparepathends[i*2+1] = last; +//printf("new ends of path %d: %d,%d\n", i, first, last); + ctx->pathspare[i] = 2; /* fixed */ + } + } + + /* + * If we got here, the extension was successful! + */ + memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int)); + memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int)); + return TRUE; +} + +/* + * Tries to add a new path to the grid. + */ +static int add_path(struct genctx *ctx, random_state *rs) +{ + int w = ctx->w, h = ctx->h; + int i, ii, n; + + /* + * Our strategy is: + * - randomly choose an empty square in the grid + * - do a BFS from that point to find a long path starting + * from it + * - if we run out of viable empty squares, return failure. + */ + + /* + * Use `sparegrid' to collect a list of empty squares. + */ + n = 0; + for (i = 0; i < w*h; i++) + if (ctx->grid[i] == -1) + ctx->sparegrid[n++] = i; + + /* + * Shuffle the grid. + */ + for (i = n; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->sparegrid[i]; + ctx->sparegrid[i] = ctx->sparegrid[k]; + ctx->sparegrid[k] = t; + } + } + + /* + * Loop over it trying to add paths. This looks like a + * horrifying N^4 algorithm (that is, (w*h)^2), but I predict + * that in fact the worst case will very rarely arise because + * when there's lots of grid space an attempt will succeed very + * quickly. + */ + for (ii = 0; ii < n; ii++) { + int i = ctx->sparegrid[ii]; + int y = i / w, x = i % w, nsq; + int r, c, j; + + /* + * BFS from here to find long paths. + */ + nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list); + + /* + * If there aren't any long enough, give up immediately. + */ + assert(nsq > 0); /* must be the start square at least! */ + if (ctx->dist[ctx->list[nsq-1]] < 3) + continue; + + /* + * Find the first viable endpoint in ctx->list (i.e. the + * first point with distance at least three). I could + * binary-search for this, but that would be O(log N) + * whereas in fact I can get a constant time bound by just + * searching up from the start - after all, there can be at + * most 13 points at _less_ than distance 3 from the + * starting one! + */ + for (j = 0; j < nsq; j++) + if (ctx->dist[ctx->list[j]] >= 3) + break; + assert(j < nsq); /* we tested above that there was one */ + + /* + * Now we know that any element of `list' between j and nsq + * would be valid in principle. However, we want a few long + * paths rather than many small ones, so select only those + * elements which are either the maximum length or one + * below it. + */ + while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]]) + j++; + r = j + random_upto(rs, nsq - j); + j = ctx->list[r]; + + /* + * And that's our endpoint. Mark the new path on the grid. + */ + c = newpath(ctx); + ctx->pathends[c*2] = i; + ctx->pathends[c*2+1] = j; + ctx->grid[j] = c; + while (j != i) { + int d, np, index, pts[4]; + np = 0; + for (d = 0; d < 4; d++) { + int xn = (j % w) + DX(d), yn = (j / w) + DY(d); + if (xn >= 0 && xn < w && yn >= 0 && yn < w && + ctx->dist[yn*w+xn] == ctx->dist[j] - 1) + pts[np++] = yn*w+xn; + } + if (np > 1) + index = random_upto(rs, np); + else + index = 0; + j = pts[index]; + ctx->grid[j] = c; + } + + return TRUE; + } + + return FALSE; +} + +/* + * The main grid generation loop. + */ +static void gridgen_mainloop(struct genctx *ctx, random_state *rs) +{ + int w = ctx->w, h = ctx->h; + int i, n; + + /* + * The generation algorithm doesn't always converge. Loop round + * until it does. + */ + while (1) { + for (i = 0; i < w*h; i++) + ctx->grid[i] = -1; + ctx->npaths = 0; + + while (1) { + /* + * See if the grid is full. + */ + for (i = 0; i < w*h; i++) + if (ctx->grid[i] < 0) + break; + if (i == w*h) + return; + +#ifdef GENERATION_DIAGNOSTICS + { + int x, y; + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + if (ctx->grid[y*w+x] >= 0) + printf("%2d", ctx->grid[y*w+x]); + else + printf(" ."); + } + printf(" |\n"); + } + } +#endif + /* + * Try adding a path. + */ + if (add_path(ctx, rs)) { +#ifdef GENERATION_DIAGNOSTICS + printf("added path\n"); +#endif + continue; + } + + /* + * Try extending a path. First list all the possible + * extensions. + */ + for (i = 0; i < ctx->npaths * 8; i++) + ctx->extends[i] = i; + n = i; + + /* + * Then shuffle the list. + */ + for (i = n; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->extends[i]; + ctx->extends[i] = ctx->extends[k]; + ctx->extends[k] = t; + } + } + + /* + * Now try each one in turn until one works. + */ + for (i = 0; i < n; i++) { + int p, d, e; + p = ctx->extends[i]; + d = p % 4; + p /= 4; + e = p % 2; + p /= 2; + +#ifdef GENERATION_DIAGNOSTICS + printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e, + ctx->pathends[p*2+e] % w, + ctx->pathends[p*2+e] / w, d); +#endif + if (extend_path(ctx, p, e, d)) { +#ifdef GENERATION_DIAGNOSTICS + printf("extended path %d end %d (%d,%d) in dir %d\n", p, e, + ctx->pathends[p*2+e] % w, + ctx->pathends[p*2+e] / w, d); +#endif + break; + } + } + + if (i < n) + continue; + + break; + } + } +} + +/* + * Wrapper function which deals with the boring bits such as + * removing the solution from the generated grid, shuffling the + * numeric labels and creating/disposing of the context structure. + */ +static int *gridgen(int w, int h, random_state *rs) +{ + struct genctx *ctx; + int *ret; + int i; + + ctx = new_genctx(w, h); + + gridgen_mainloop(ctx, rs); + + /* + * There is likely to be an ordering bias in the numbers + * (longer paths on lower numbers due to there having been more + * grid space when laying them down). So we must shuffle the + * numbers. We use ctx->pathspare for this. + * + * This is also as good a time as any to shift to numbering + * from 1, for display to the user. + */ + for (i = 0; i < ctx->npaths; i++) + ctx->pathspare[i] = i+1; + for (i = ctx->npaths; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->pathspare[i]; + ctx->pathspare[i] = ctx->pathspare[k]; + ctx->pathspare[k] = t; + } + } + + /* FIXME: remove this at some point! */ + { + int y, x; + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + assert(ctx->grid[y*w+x] >= 0); + printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]); + } + printf(" |\n"); + } + printf("\n"); + } + + /* + * Clear the grid, and write in just the endpoints. + */ + for (i = 0; i < w*h; i++) + ctx->grid[i] = 0; + for (i = 0; i < ctx->npaths; i++) { + ctx->grid[ctx->pathends[i*2]] = + ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i]; + } + + ret = ctx->grid; + ctx->grid = NULL; + + free_genctx(ctx); + + return ret; +} + +#ifdef TEST_GEN + +#define TEST_GENERAL + +int main(void) +{ + int w = 10, h = 8; + random_state *rs = random_init("12345", 5); + int x, y, i, *grid; + + for (i = 0; i < 10; i++) { + grid = gridgen(w, h, rs); + + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + if (grid[y*w+x] > 0) + printf("%2d", grid[y*w+x]); + else + printf(" ."); + } + printf(" |\n"); + } + printf("\n"); + + sfree(grid); + } + + return 0; +} +#endif + +#ifdef TEST_GENERAL +#include + +void fatal(char *fmt, ...) +{ + va_list ap; + + fprintf(stderr, "fatal error: "); + + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); + + fprintf(stderr, "\n"); + exit(1); +} +#endif -- cgit v1.2.3