X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/48a10826fef7777bb8b061f4a121f481ced98bc0..b2a646f1af7858878025bdae14bef9482bee8e26:/sixteen.c

diff --git a/sixteen.c b/sixteen.c
index 950f724..c202de1 100644
--- a/sixteen.c
+++ b/sixteen.c
@@ -36,6 +36,7 @@ enum {
 
 struct game_params {
     int w, h;
+    int movetarget;
 };
 
 struct game_state {
@@ -44,7 +45,7 @@ struct game_state {
     int completed;
     int just_used_solve;	       /* used to suppress undo animation */
     int used_solve;		       /* used to suppress completion flash */
-    int movecount;
+    int movecount, movetarget;
     int last_movement_sense;
 };
 
@@ -53,6 +54,7 @@ static game_params *default_params(void)
     game_params *ret = snew(game_params);
 
     ret->w = ret->h = 4;
+    ret->movetarget = 0;
 
     return ret;
 }
@@ -77,6 +79,7 @@ static int game_fetch_preset(int i, char **name, game_params **params)
     *params = ret = snew(game_params);
     ret->w = w;
     ret->h = h;
+    ret->movetarget = 0;
     return TRUE;
 }
 
@@ -92,25 +95,34 @@ 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();
-
     ret->w = ret->h = atoi(string);
+    ret->movetarget = 0;
     while (*string && isdigit(*string)) string++;
     if (*string == 'x') {
         string++;
         ret->h = atoi(string);
+	while (*string && isdigit((unsigned char)*string))
+	    string++;
+    }
+    if (*string == 'm') {
+        string++;
+        ret->movetarget = atoi(string);
+	while (*string && isdigit((unsigned char)*string))
+	    string++;
     }
-
-    return ret;
 }
 
-static char *encode_params(game_params *params)
+static char *encode_params(game_params *params, int full)
 {
     char data[256];
 
     sprintf(data, "%dx%d", params->w, params->h);
+    /* Shuffle limit is part of the limited parameters, because we have to
+     * supply the target move count. */
+    if (params->movetarget)
+        sprintf(data + strlen(data), "m%d", params->movetarget);
 
     return dupstr(data);
 }
@@ -120,7 +132,7 @@ static config_item *game_configure(game_params *params)
     config_item *ret;
     char buf[80];
 
-    ret = snewn(3, config_item);
+    ret = snewn(4, config_item);
 
     ret[0].name = "Width";
     ret[0].type = C_STRING;
@@ -134,11 +146,17 @@ static config_item *game_configure(game_params *params)
     ret[1].sval = dupstr(buf);
     ret[1].ival = 0;
 
-    ret[2].name = NULL;
-    ret[2].type = C_END;
-    ret[2].sval = NULL;
+    ret[2].name = "Number of shuffling moves";
+    ret[2].type = C_STRING;
+    sprintf(buf, "%d", params->movetarget);
+    ret[2].sval = dupstr(buf);
     ret[2].ival = 0;
 
+    ret[3].name = NULL;
+    ret[3].type = C_END;
+    ret[3].sval = NULL;
+    ret[3].ival = 0;
+
     return ret;
 }
 
@@ -148,6 +166,7 @@ static game_params *custom_params(config_item *cfg)
 
     ret->w = atoi(cfg[0].sval);
     ret->h = atoi(cfg[1].sval);
+    ret->movetarget = atoi(cfg[2].sval);
 
     return ret;
 }
@@ -174,8 +193,8 @@ static int perm_parity(int *perm, int n)
     return ret;
 }
 
-static char *new_game_seed(game_params *params, random_state *rs,
-			   game_aux_info **aux)
+static char *new_game_desc(game_params *params, random_state *rs,
+			   game_aux_info **aux, int interactive)
 {
     int stop, n, i, x;
     int x1, x2, p1, p2;
@@ -186,80 +205,178 @@ static char *new_game_seed(game_params *params, random_state *rs,
     n = params->w * params->h;
 
     tiles = snewn(n, int);
-    used = snewn(n, int);
 
-    for (i = 0; i < n; i++) {
-        tiles[i] = -1;
-        used[i] = FALSE;
-    }
+    if (params->movetarget) {
+	int prevoffset = -1;
+        int max = (params->w > params->h ? params->w : params->h);
+        int *prevmoves = snewn(max, int);
 
-    /*
-     * If both dimensions are odd, there is a parity constraint.
-     */
-    if (params->w & params->h & 1)
-        stop = 2;
-    else
-        stop = 0;
+	/*
+	 * Shuffle the old-fashioned way, by making a series of
+	 * single moves on the grid.
+	 */
 
-    /*
-     * Place everything except (possibly) the last two tiles.
-     */
-    for (x = 0, i = n; i > stop; i--) {
-        int k = i > 1 ? random_upto(rs, i) : 0;
-        int j;
+	for (i = 0; i < n; i++)
+	    tiles[i] = i;
 
-        for (j = 0; j < n; j++)
-            if (!used[j] && (k-- == 0))
-                break;
+	for (i = 0; i < params->movetarget; i++) {
+	    int start, offset, len, direction, index;
+	    int j, tmp;
 
-        assert(j < n && !used[j]);
-        used[j] = TRUE;
+	    /*
+	     * Choose a move to make. We can choose from any row
+	     * or any column.
+	     */
+	    while (1) {
+		j = random_upto(rs, params->w + params->h);
+
+		if (j < params->w) {
+		    /* Column. */
+                    index = j;
+		    start = j;
+		    offset = params->w;
+		    len = params->h;
+		} else {
+		    /* Row. */
+                    index = j - params->w;
+		    start = index * params->w;
+		    offset = 1;
+		    len = params->w;
+		}
 
-        while (tiles[x] >= 0)
-            x++;
-        assert(x < n);
-        tiles[x] = j;
-    }
+		direction = -1 + 2 * random_upto(rs, 2);
 
-    if (stop) {
-        /*
-         * Find the last two locations, and the last two pieces.
-         */
-        while (tiles[x] >= 0)
-            x++;
-        assert(x < n);
-        x1 = x;
-        x++;
-        while (tiles[x] >= 0)
-            x++;
-        assert(x < n);
-        x2 = x;
-
-        for (i = 0; i < n; i++)
-            if (!used[i])
-                break;
-        p1 = i;
-        for (i = p1+1; i < n; i++)
-            if (!used[i])
-                break;
-        p2 = i;
+		/*
+		 * To at least _try_ to avoid boring cases, check
+		 * that this move doesn't directly undo a previous
+		 * one, or repeat it so many times as to turn it
+		 * into fewer moves in the opposite direction. (For
+		 * example, in a row of length 4, we're allowed to
+		 * move it the same way twice, but not three
+		 * times.)
+                 * 
+                 * We track this for each individual row/column,
+                 * and clear all the counters as soon as a
+                 * perpendicular move is made. This isn't perfect
+                 * (it _can't_ guaranteeably be perfect - there
+                 * will always come a move count beyond which a
+                 * shorter solution will be possible than the one
+                 * which constructed the position) but it should
+                 * sort out all the obvious cases.
+		 */
+                if (offset == prevoffset) {
+                    tmp = prevmoves[index] + direction;
+                    if (abs(2*tmp) > len || abs(tmp) < abs(prevmoves[index]))
+                        continue;
+                }
+
+		/* If we didn't `continue', we've found an OK move to make. */
+                if (offset != prevoffset) {
+                    int i;
+                    for (i = 0; i < max; i++)
+                        prevmoves[i] = 0;
+                    prevoffset = offset;
+                }
+                prevmoves[index] += direction;
+		break;
+	    }
 
-        /*
-         * Try the last two tiles one way round. If that fails, swap
-         * them.
-         */
-        tiles[x1] = p1;
-        tiles[x2] = p2;
-        if (perm_parity(tiles, n) != 0) {
-            tiles[x1] = p2;
-            tiles[x2] = p1;
-            assert(perm_parity(tiles, n) == 0);
-        }
+	    /*
+	     * Make the move.
+	     */
+	    if (direction < 0) {
+		start += (len-1) * offset;
+		offset = -offset;
+	    }
+	    tmp = tiles[start];
+	    for (j = 0; j+1 < len; j++)
+		tiles[start + j*offset] = tiles[start + (j+1)*offset];
+	    tiles[start + (len-1) * offset] = tmp;
+	}
+
+        sfree(prevmoves);
+
+    } else {
+
+	used = snewn(n, int);
+
+	for (i = 0; i < n; i++) {
+	    tiles[i] = -1;
+	    used[i] = FALSE;
+	}
+
+	/*
+	 * If both dimensions are odd, there is a parity
+	 * constraint.
+	 */
+	if (params->w & params->h & 1)
+	    stop = 2;
+	else
+	    stop = 0;
+
+	/*
+	 * Place everything except (possibly) the last two tiles.
+	 */
+	for (x = 0, i = n; i > stop; i--) {
+	    int k = i > 1 ? random_upto(rs, i) : 0;
+	    int j;
+
+	    for (j = 0; j < n; j++)
+		if (!used[j] && (k-- == 0))
+		    break;
+
+	    assert(j < n && !used[j]);
+	    used[j] = TRUE;
+
+	    while (tiles[x] >= 0)
+		x++;
+	    assert(x < n);
+	    tiles[x] = j;
+	}
+
+	if (stop) {
+	    /*
+	     * Find the last two locations, and the last two
+	     * pieces.
+	     */
+	    while (tiles[x] >= 0)
+		x++;
+	    assert(x < n);
+	    x1 = x;
+	    x++;
+	    while (tiles[x] >= 0)
+		x++;
+	    assert(x < n);
+	    x2 = x;
+
+	    for (i = 0; i < n; i++)
+		if (!used[i])
+		    break;
+	    p1 = i;
+	    for (i = p1+1; i < n; i++)
+		if (!used[i])
+		    break;
+	    p2 = i;
+
+	    /*
+	     * Try the last two tiles one way round. If that fails,
+	     * swap them.
+	     */
+	    tiles[x1] = p1;
+	    tiles[x2] = p2;
+	    if (perm_parity(tiles, n) != 0) {
+		tiles[x1] = p2;
+		tiles[x2] = p1;
+		assert(perm_parity(tiles, n) == 0);
+	    }
+	}
+
+	sfree(used);
     }
 
     /*
-     * Now construct the game seed, by describing the tile array as
-     * a simple sequence of comma-separated integers.
+     * Now construct the game description, by describing the tile
+     * array as a simple sequence of comma-separated integers.
      */
     ret = NULL;
     retlen = 0;
@@ -276,7 +393,6 @@ static char *new_game_seed(game_params *params, random_state *rs,
     ret[retlen-1] = '\0';              /* delete last comma */
 
     sfree(tiles);
-    sfree(used);
 
     return ret;
 }
@@ -287,14 +403,14 @@ static void game_free_aux_info(game_aux_info *aux)
 }
 
 
-static char *validate_seed(game_params *params, char *seed)
+static char *validate_desc(game_params *params, char *desc)
 {
     char *p, *err;
     int i, area;
     int *used;
 
     area = params->w * params->h;
-    p = seed;
+    p = desc;
     err = NULL;
 
     used = snewn(area, int);
@@ -338,7 +454,7 @@ static char *validate_seed(game_params *params, char *seed)
     return err;
 }
 
-static game_state *new_game(game_params *params, char *seed)
+static game_state *new_game(midend_data *me, game_params *params, char *desc)
 {
     game_state *state = snew(game_state);
     int i;
@@ -349,7 +465,7 @@ static game_state *new_game(game_params *params, char *seed)
     state->n = params->w * params->h;
     state->tiles = snewn(state->n, int);
 
-    p = seed;
+    p = desc;
     i = 0;
     for (i = 0; i < state->n; i++) {
         assert(*p);
@@ -361,6 +477,7 @@ static game_state *new_game(game_params *params, char *seed)
     assert(!*p);
 
     state->completed = state->movecount = 0;
+    state->movetarget = params->movetarget;
     state->used_solve = state->just_used_solve = FALSE;
     state->last_movement_sense = 0;
 
@@ -378,6 +495,7 @@ static game_state *dup_game(game_state *state)
     memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
     ret->completed = state->completed;
     ret->movecount = state->movecount;
+    ret->movetarget = state->movetarget;
     ret->used_solve = state->used_solve;
     ret->just_used_solve = state->just_used_solve;
     ret->last_movement_sense = state->last_movement_sense;
@@ -406,7 +524,7 @@ static game_state *solve_game(game_state *state, game_aux_info *aux,
     for (i = 0; i < ret->n; i++)
 	ret->tiles[i] = i+1;
     ret->used_solve = ret->just_used_solve = TRUE;
-    ret->completed = ret->movecount;
+    ret->completed = ret->movecount = 1;
 
     return ret;
 }
@@ -459,13 +577,13 @@ static void free_ui(game_ui *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) {
     int cx, cy;
     int dx, dy, tx, ty, n;
     game_state *ret;
 
+    button &= ~MOD_MASK;
     if (button != LEFT_BUTTON && button != RIGHT_BUTTON)
         return NULL;
 
@@ -816,17 +934,21 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 	if (state->used_solve)
 	    sprintf(statusbuf, "Moves since auto-solve: %d",
 		    state->movecount - state->completed);
-	else
+	else {
 	    sprintf(statusbuf, "%sMoves: %d",
 		    (state->completed ? "COMPLETED! " : ""),
 		    (state->completed ? state->completed : state->movecount));
+            if (state->movetarget)
+                sprintf(statusbuf+strlen(statusbuf), " (target %d)",
+                        state->movetarget);
+	}
 
 	status_bar(fe, statusbuf);
     }
 }
 
 static float game_anim_length(game_state *oldstate,
-			      game_state *newstate, int dir)
+			      game_state *newstate, int dir, game_ui *ui)
 {
     if ((dir > 0 && newstate->just_used_solve) ||
 	(dir < 0 && oldstate->just_used_solve))
@@ -836,7 +958,7 @@ static float game_anim_length(game_state *oldstate,
 }
 
 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 &&
 	!oldstate->used_solve && !newstate->used_solve)
@@ -850,6 +972,11 @@ static int game_wants_statusbar(void)
     return TRUE;
 }
 
+static int game_timing_state(game_state *state)
+{
+    return TRUE;
+}
+
 #ifdef COMBINED
 #define thegame sixteen
 #endif
@@ -864,9 +991,9 @@ 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,
@@ -883,4 +1010,5 @@ const struct game thegame = {
     game_anim_length,
     game_flash_length,
     game_wants_statusbar,
+    FALSE, game_timing_state,
 };