X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=guess.c;h=df9b7f628c9d117d614257d93b3f44794b20fed5;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=38cdf25d365582cc085af01170bd743b438c1d0c;hpb=96315bc2baecb68040600cf93da4b4ce729e1acc;p=sgt-puzzles.git

diff --git a/guess.c b/guess.c
index 38cdf25..df9b7f6 100644
--- a/guess.c
+++ b/guess.c
@@ -43,7 +43,7 @@ struct game_state {
     pegrow solution;
     int next_go; /* from 0 to nguesses-1;
                     if next_go == nguesses then they've lost. */
-    int solved;
+    int solved;   /* +1 = win, -1 = lose, 0 = still playing */
 };
 
 static game_params *default_params(void)
@@ -66,7 +66,7 @@ static void free_params(game_params *params)
     sfree(params);
 }
 
-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 */
@@ -145,7 +145,7 @@ 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 data[256];
 
@@ -156,7 +156,7 @@ static char *encode_params(game_params *params, int full)
     return dupstr(data);
 }
 
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
 {
     config_item *ret;
     char buf[80];
@@ -199,7 +199,7 @@ static config_item *game_configure(game_params *params)
     return ret;
 }
 
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
 {
     game_params *ret = snew(game_params);
 
@@ -213,7 +213,7 @@ static game_params *custom_params(config_item *cfg)
     return ret;
 }
 
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
 {
     if (params->ncolours < 2 || params->npegs < 2)
 	return "Trivial solutions are uninteresting";
@@ -264,7 +264,7 @@ static void free_pegrow(pegrow pegs)
     sfree(pegs);
 }
 
-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)
 {
     unsigned char *bmp = snewn(params->npegs, unsigned char);
@@ -287,7 +287,7 @@ newcol:
     return ret;
 }
 
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
 {
     unsigned char *bmp;
     int i;
@@ -310,7 +310,8 @@ 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)
 {
     game_state *state = snew(game_state);
     unsigned char *bmp;
@@ -335,7 +336,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc)
     return state;
 }
 
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
 {
     game_state *ret = snew(game_state);
     int i;
@@ -365,23 +366,23 @@ static void free_game(game_state *state)
     sfree(state);
 }
 
-static char *solve_game(game_state *state, game_state *currstate,
-			char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+                        const char *aux, char **error)
 {
     return dupstr("S");
 }
 
-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)
 {
     return NULL;
 }
 
-static int is_markable(game_params *params, pegrow pegs)
+static int is_markable(const game_params *params, pegrow pegs)
 {
     int i, nset = 0, nrequired, ret = 0;
     pegrow colcount = new_pegrow(params->ncolours);
@@ -420,9 +421,10 @@ struct game_ui {
     int drag_opeg; /* peg index, if dragged from a peg (from current guess), otherwise -1 */
 
     int show_labels;                   /* label the colours with letters */
+    pegrow hint;
 };
 
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
 {
     game_ui *ui = snew(game_ui);
     memset(ui, 0, sizeof(game_ui));
@@ -436,12 +438,14 @@ static game_ui *new_ui(game_state *state)
 
 static void free_ui(game_ui *ui)
 {
+    if (ui->hint)
+        free_pegrow(ui->hint);
     free_pegrow(ui->curr_pegs);
     sfree(ui->holds);
     sfree(ui);
 }
 
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
 {
     char *ret, *p, *sep;
     int i;
@@ -463,10 +467,10 @@ static char *encode_ui(game_ui *ui)
     return sresize(ret, p - ret, char);
 }
 
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
 {
     int i;
-    char *p = encoding;
+    const char *p = encoding;
     for (i = 0; i < ui->curr_pegs->npegs; i++) {
         ui->curr_pegs->pegs[i] = atoi(p);
         while (*p && isdigit((unsigned char)*p)) p++;
@@ -481,11 +485,16 @@ static void decode_ui(game_ui *ui, char *encoding)
     ui->markable = is_markable(&ui->params, ui->curr_pegs);
 }
 
-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)
 {
     int i;
 
+    if (newstate->next_go < oldstate->next_go) {
+        sfree(ui->hint);
+        ui->hint = NULL;
+    }
+
     /* Implement holds, clear other pegs.
      * This does something that is arguably the Right Thing even
      * for undo. */
@@ -564,13 +573,13 @@ struct game_drawstate {
     int drag_col, blit_ox, blit_oy;
 };
 
-static void set_peg(game_params *params, game_ui *ui, int peg, int col)
+static void set_peg(const game_params *params, game_ui *ui, int peg, int col)
 {
     ui->curr_pegs->pegs[peg] = col;
     ui->markable = is_markable(params, ui->curr_pegs);
 }
 
-static int mark_pegs(pegrow guess, pegrow solution, int ncols)
+static int mark_pegs(pegrow guess, const pegrow solution, int ncols)
 {
     int nc_place = 0, nc_colour = 0, i, j;
 
@@ -610,7 +619,7 @@ static int mark_pegs(pegrow guess, pegrow solution, int ncols)
     return nc_place;
 }
 
-static char *encode_move(game_state *from, game_ui *ui)
+static char *encode_move(const game_state *from, game_ui *ui)
 {
     char *buf, *p, *sep;
     int len, i;
@@ -632,8 +641,128 @@ static char *encode_move(game_state *from, game_ui *ui)
     return buf;
 }
 
-static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
-			    int x, int y, int button)
+static void compute_hint(const game_state *state, game_ui *ui)
+{
+    /* Suggest the lexicographically first row consistent with all
+     * previous feedback.  This is not only a useful hint, but also
+     * a reasonable strategy if applied consistently.  If the user
+     * uses hints in every turn, they may be able to intuit this
+     * strategy, or one similar to it.  I (Jonas Kölker) came up
+     * with something close to it without seeing it in action. */
+
+    /* Some performance characteristics: I want to ask for each n,
+     * how many solutions are guessed in exactly n guesses if you
+     * use the hint in each turn.
+     *
+     * With 4 pegs and 6 colours you get the following histogram:
+     *
+     *  1 guesses:     1 solution
+     *  2 guesses:     4 solutions
+     *  3 guesses:    25 solutions
+     *  4 guesses:   108 solutions
+     *  5 guesses:   305 solutions
+     *  6 guesses:   602 solutions
+     *  7 guesses:   196 solutions
+     *  8 guesses:    49 solutions
+     *  9 guesses:     6 solutions
+     * (note: the tenth guess is never necessary.)
+     *
+     * With 5 pegs and 8 colours you get the following histogram:
+     *
+     *  1 guesses:     1 solution
+     *  2 guesses:     5 solutions
+     *  3 guesses:    43 solutions
+     *  4 guesses:   278 solutions
+     *  5 guesses:  1240 solutions
+     *  6 guesses:  3515 solutions
+     *  7 guesses:  7564 solutions
+     *  8 guesses: 14086 solutions
+     *  9 guesses:  4614 solutions
+     * 10 guesses:  1239 solutions
+     * 11 guesses:   175 solutions
+     * 12 guesses:     7 solutions
+     * 13 guesses:     1 solution
+     *
+     * The solution which takes too many guesses is {8, 8, 5, 6, 7}.
+     * The game ID is c8p5g12Bm:4991e5e41a. */
+
+    int mincolour = 1, maxcolour = 0, i, j;
+
+    /* For large values of npegs and ncolours, the lexicographically
+     * next guess make take a while to find.  Finding upper and
+     * lower limits on which colours we have to consider will speed
+     * this up, as will caching our progress from one invocation to
+     * the next.  The latter strategy works, since if we have ruled
+     * out a candidate we will never reverse this judgment in the
+     * light of new information.  Removing information, i.e. undo,
+     * will require us to backtrack somehow.  We backtrack by fully
+     * forgetting our progress (and recomputing it if required). */
+
+    for (i = 0; i < state->next_go; ++i)
+        for (j = 0; j < state->params.npegs; ++j)
+            if (state->guesses[i]->pegs[j] > maxcolour)
+                maxcolour = state->guesses[i]->pegs[j];
+    maxcolour = min(maxcolour + 1, state->params.ncolours);
+
+increase_mincolour:
+    for (i = 0; i < state->next_go; ++i) {
+        if (state->guesses[i]->feedback[0])
+            goto next_iteration;
+        for (j = 0; j < state->params.npegs; ++j)
+            if (state->guesses[i]->pegs[j] != mincolour)
+                goto next_iteration;
+        ++mincolour;
+        goto increase_mincolour;
+    next_iteration:
+        ;
+    }
+
+    if (!ui->hint) {
+        ui->hint = new_pegrow(state->params.npegs);
+        for (i = 0; i < state->params.npegs; ++i)
+            ui->hint->pegs[i] = 1;
+    }
+
+    while (ui->hint->pegs[0] <= state->params.ncolours) {
+        for (i = 0; i < state->next_go; ++i) {
+            mark_pegs(ui->hint, state->guesses[i], maxcolour);
+            for (j = 0; j < state->params.npegs; ++j)
+                if (ui->hint->feedback[j] != state->guesses[i]->feedback[j])
+                    goto increment_pegrow;
+        }
+        /* a valid guess was found; install it and return */
+        for (i = 0; i < state->params.npegs; ++i)
+            ui->curr_pegs->pegs[i] = ui->hint->pegs[i];
+
+        ui->markable = TRUE;
+        ui->peg_cur = state->params.npegs;
+        ui->display_cur = 1;
+        return;
+
+    increment_pegrow:
+        for (i = ui->hint->npegs;
+             ++ui->hint->pegs[--i], i && ui->hint->pegs[i] > maxcolour;
+             ui->hint->pegs[i] = mincolour);
+    }
+    /* No solution is compatible with the given hints.  Impossible! */
+    /* (hack new_game_desc to create invalid solutions to get here) */
+
+    /* For some values of npegs and ncolours, the hinting function takes a
+     * long time to complete.  To visually indicate completion with failure,
+     * should it ever happen, update the ui in some trivial way.  This gives
+     * the user a sense of broken(ish)ness and futility. */
+    if (!ui->display_cur) {
+        ui->display_cur = 1;
+    } else if (state->params.npegs == 1) {
+        ui->display_cur = 0;
+    } else {
+        ui->peg_cur = (ui->peg_cur + 1) % state->params.npegs;
+    }
+}
+
+static char *interpret_move(const game_state *from, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
 {
     int over_col = 0;           /* one-indexed */
     int over_guess = -1;        /* zero-indexed */
@@ -752,6 +881,9 @@ static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
         if (button == CURSOR_UP && ui->colour_cur > 0)
             ui->colour_cur--;
         ret = "";
+    } else if (button == 'h' || button == 'H' || button == '?') {
+        compute_hint(from, ui);
+        ret = "";
     } else if (button == CURSOR_LEFT || button == CURSOR_RIGHT) {
         int maxcur = from->params.npegs;
         if (ui->markable) maxcur++;
@@ -774,7 +906,9 @@ static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
         ui->display_cur = 1;
         set_peg(&from->params, ui, ui->peg_cur, 0);
         ret = "";
-    } else if (button == 'H' || button == 'h') {
+    } else if (button == CURSOR_SELECT2) {
+        if (ui->peg_cur == from->params.npegs)
+            return NULL;
         ui->display_cur = 1;
         ui->holds[ui->peg_cur] = 1 - ui->holds[ui->peg_cur];
         ret = "";
@@ -782,15 +916,15 @@ static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
     return ret;
 }
 
-static game_state *execute_move(game_state *from, char *move)
+static game_state *execute_move(const game_state *from, const char *move)
 {
     int i, nc_place;
     game_state *ret;
-    char *p;
+    const char *p;
 
     if (!strcmp(move, "S")) {
 	ret = dup_game(from);
-	ret->solved = 1;
+	ret->solved = -1;
 	return ret;
     } else if (move[0] == 'G') {
 	p = move+1;
@@ -817,11 +951,11 @@ static game_state *execute_move(game_state *from, char *move)
 	nc_place = mark_pegs(ret->guesses[from->next_go], ret->solution, ret->params.ncolours);
 
 	if (nc_place == ret->solution->npegs) {
-	    ret->solved = 1; /* win! */
+	    ret->solved = +1; /* win! */
 	} else {
 	    ret->next_go = from->next_go + 1;
 	    if (ret->next_go >= ret->params.nguesses)
-		ret->solved = 1; /* 'lose' so we show the pegs. */
+		ret->solved = -1; /* lose, meaning we show the pegs. */
 	}
 
 	return ret;
@@ -842,8 +976,8 @@ static game_state *execute_move(game_state *from, char *move)
 
 #define BORDER    0.5
 
-static void game_compute_size(game_params *params, int tilesize,
-			      int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+                              int *x, int *y)
 {
     double hmul, vmul_c, vmul_g, vmul;
     int hintw = (params->npegs+1)/2;
@@ -870,7 +1004,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)
 {
     int colh, guessh;
 
@@ -897,7 +1031,7 @@ static void game_set_size(drawing *dr, game_drawstate *ds,
 
     assert(ds->pegsz > 0);
     assert(!ds->blit_peg);             /* set_size is never called twice */
-    ds->blit_peg = blitter_new(dr, ds->pegsz, ds->pegsz);
+    ds->blit_peg = blitter_new(dr, ds->pegsz+2, ds->pegsz+2);
 }
 
 static float *game_colours(frontend *fe, int *ncolours)
@@ -1004,7 +1138,7 @@ static float *game_colours(frontend *fe, int *ncolours)
     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)
 {
     struct game_drawstate *ds = snew(struct game_drawstate);
     int i;
@@ -1206,14 +1340,14 @@ static void currmove_redraw(drawing *dr, game_drawstate *ds, int guess, int col)
     draw_update(dr, ox-off-1, oy, 2, PEGSZ);
 }
 
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
-			game_state *state, int dir, game_ui *ui,
-			float animtime, float flashtime)
+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 i, new_move, last_go;
+    int i, new_move;
 
     new_move = (state->next_go != ds->next_go) || !ds->started;
-    last_go = (state->next_go == state->params.nguesses-1);
 
     if (!ds->started) {
       draw_rect(dr, 0, 0, ds->w, ds->h, COL_BACKGROUND);
@@ -1243,29 +1377,31 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
     }
 
     /* draw the guesses (so far) and the hints
-     * (in reverse order to avoid trampling holds) */
+     * (in reverse order to avoid trampling holds, and postponing the
+     * next_go'th to not overrender the top of the circular cursor) */
     for (i = state->params.nguesses - 1; i >= 0; i--) {
-        if (state->next_go > i || state->solved) {
+        if (i < state->next_go || state->solved) {
             /* this info is stored in the game_state already */
             guess_redraw(dr, ds, i, state->guesses[i], NULL, -1, 0,
                          ui->show_labels);
             hint_redraw(dr, ds, i, state->guesses[i],
                         i == (state->next_go-1) ? 1 : 0, FALSE, FALSE);
-        } else if (state->next_go == i) {
-            /* this is the one we're on; the (incomplete) guess is
-             * stored in the game_ui. */
-            guess_redraw(dr, ds, i, ui->curr_pegs,
-                         ui->holds, ui->display_cur ? ui->peg_cur : -1, 0,
-                         ui->show_labels);
-            hint_redraw(dr, ds, i, NULL, 1,
-                        ui->display_cur && ui->peg_cur == state->params.npegs,
-                        ui->markable);
-        } else {
+        } else if (i > state->next_go) {
             /* we've not got here yet; it's blank. */
             guess_redraw(dr, ds, i, NULL, NULL, -1, 0, ui->show_labels);
             hint_redraw(dr, ds, i, NULL, 0, FALSE, FALSE);
         }
     }
+    if (!state->solved) {
+	/* this is the one we're on; the (incomplete) guess is stored in
+	 * the game_ui. */
+	guess_redraw(dr, ds, state->next_go, ui->curr_pegs,
+		     ui->holds, ui->display_cur ? ui->peg_cur : -1, 0,
+		     ui->show_labels);
+	hint_redraw(dr, ds, state->next_go, NULL, 1,
+		    ui->display_cur && ui->peg_cur == state->params.npegs,
+		    ui->markable);
+    }
 
     /* draw the 'current move' and 'able to mark' sign. */
     if (new_move)
@@ -1274,7 +1410,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
         currmove_redraw(dr, ds, state->next_go, COL_HOLD);
 
     /* draw the solution (or the big rectangle) */
-    if ((state->solved != ds->solved) || !ds->started) {
+    if ((!state->solved ^ !ds->solved) || !ds->started) {
         draw_rect(dr, SOLN_OX, SOLN_OY, SOLN_W, SOLN_H,
                   state->solved ? COL_BACKGROUND : COL_EMPTY);
         draw_update(dr, SOLN_OX, SOLN_OY, SOLN_W, SOLN_H);
@@ -1291,39 +1427,49 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
     if (ui->drag_col != 0) {
         int ox = ui->drag_x - (PEGSZ/2);
         int oy = ui->drag_y - (PEGSZ/2);
-        debug(("Saving to blitter at (%d,%d)", ox, oy));
-        blitter_save(dr, ds->blit_peg, ox, oy);
+        ds->blit_ox = ox - 1; ds->blit_oy = oy - 1;
+        debug(("Saving to blitter at (%d,%d)", ds->blit_ox, ds->blit_oy));
+        blitter_save(dr, ds->blit_peg, ds->blit_ox, ds->blit_oy);
         draw_peg(dr, ds, ox, oy, TRUE, ui->show_labels, ui->drag_col);
-
-        ds->blit_ox = ox; ds->blit_oy = oy;
     }
     ds->drag_col = ui->drag_col;
 
     ds->started = 1;
 }
 
-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;
 }
 
-static float game_flash_length(game_state *oldstate, game_state *newstate,
-			       int dir, game_ui *ui)
+static float game_flash_length(const game_state *oldstate,
+                               const game_state *newstate, int dir, game_ui *ui)
 {
     return 0.0F;
 }
 
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_status(const game_state *state)
+{
+    /*
+     * We return nonzero whenever the solution has been revealed, even
+     * (on spoiler grounds) if it wasn't guessed correctly. The
+     * correct return value from this function is already in
+     * state->solved.
+     */
+    return state->solved;
+}
+
+static int game_timing_state(const game_state *state, game_ui *ui)
 {
     return TRUE;
 }
 
-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)
 {
 }
 
-static void game_print(drawing *dr, game_state *state, int tilesize)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
 {
 }
 
@@ -1362,6 +1508,7 @@ const struct game thegame = {
     game_redraw,
     game_anim_length,
     game_flash_length,
+    game_status,
     FALSE, FALSE, game_print_size, game_print,
     FALSE,			       /* wants_statusbar */
     FALSE, game_timing_state,