/*
* map.c: Game involving four-colouring a map.
*/
/*
* TODO:
*
* - clue marking
* - better four-colouring algorithm?
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#ifdef NO_TGMATH_H
# include <math.h>
#else
# include <tgmath.h>
#endif
#include "puzzles.h"
/*
* In standalone solver mode, `verbose' is a variable which can be
* set by command-line option; in debugging mode it's simply always
* true.
*/
#if defined STANDALONE_SOLVER
#define SOLVER_DIAGNOSTICS
static bool verbose = false;
#elif defined SOLVER_DIAGNOSTICS
#define verbose true
#endif
/*
* I don't seriously anticipate wanting to change the number of
* colours used in this game, but it doesn't cost much to use a
* #define just in case :-)
*/
#define FOUR 4
#define THREE (FOUR-1)
#define FIVE (FOUR+1)
#define SIX (FOUR+2)
/*
* Difficulty levels. I do some macro ickery here to ensure that my
* enum and the various forms of my name list always match up.
*/
#define DIFFLIST(A) \
A(EASY,Easy,e) \
A(NORMAL,Normal,n) \
A(HARD,Hard,h) \
A(RECURSE,Unreasonable,u)
#define ENUM(upper,title,lower) DIFF_ ## upper,
#define TITLE(upper,title,lower) #title,
#define ENCODE(upper,title,lower) #lower
#define CONFIG(upper,title,lower) ":" #title
enum { DIFFLIST(ENUM) DIFFCOUNT };
static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
static char const map_diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)
enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
enum {
COL_BACKGROUND,
COL_GRID,
COL_0, COL_1, COL_2, COL_3,
COL_ERROR, COL_ERRTEXT,
NCOLOURS
};
struct game_params {
int w, h, n, diff;
};
struct map {
int refcount;
int *map;
int *graph;
int n;
int ngraph;
bool *immutable;
int *edgex, *edgey; /* position of a point on each edge */
int *regionx, *regiony; /* position of a point in each region */
};
struct game_state {
game_params p;
struct map *map;
int *colouring, *pencil;
bool completed, cheated;
};
static game_params *default_params(void)
{
game_params *ret = snew(game_params);
#ifdef PORTRAIT_SCREEN
ret->w = 16;
ret->h = 18;
#else
ret->w = 20;
ret->h = 15;
#endif
ret->n = 30;
ret->diff = DIFF_NORMAL;
return ret;
}
static const struct game_params map_presets[] = {
#ifdef PORTRAIT_SCREEN
{16, 18, 30, DIFF_EASY},
{16, 18, 30, DIFF_NORMAL},
{16, 18, 30, DIFF_HARD},
{16, 18, 30, DIFF_RECURSE},
{25, 30, 75, DIFF_NORMAL},
{25, 30, 75, DIFF_HARD},
#else
{20, 15, 30, DIFF_EASY},
{20, 15, 30, DIFF_NORMAL},
{20, 15, 30, DIFF_HARD},
{20, 15, 30, DIFF_RECURSE},
{30, 25, 75, DIFF_NORMAL},
{30, 25, 75, DIFF_HARD},
#endif
};
static bool game_fetch_preset(int i, char **name, game_params **params)
{
game_params *ret;
char str[80];
if (i < 0 || i >= lenof(map_presets))
return false;
ret = snew(game_params);
*ret = map_presets[i];
sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
map_diffnames[ret->diff]);
*name = dupstr(str);
*params = ret;
return true;
}
static void free_params(game_params *params)
{
sfree(params);
}
static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
return ret;
}
static void decode_params(game_params *params, char const *string)
{
char const *p = string;
params->w = atoi(p);
while (*p && isdigit((unsigned char)*p)) p++;
if (*p == 'x') {
p++;
params->h = atoi(p);
while (*p && isdigit((unsigned char)*p)) p++;
} else {
params->h = params->w;
}
if (*p == 'n') {
p++;
params->n = atoi(p);
while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
} else {
if (params->h > 0 && params->w > 0 &&
params->w <= INT_MAX / params->h)
params->n = params->w * params->h / 8;
}
if (*p == 'd') {
int i;
p++;
for (i = 0; i < DIFFCOUNT; i++)
if (*p == map_diffchars[i])
params->diff = i;
if (*p) p++;
}
}
static char *encode_params(const game_params *params, bool full)
{
char ret[400];
sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
if (full)
sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
return dupstr(ret);
}
static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
ret = snewn(5, config_item);
ret[0].name = "Width";
ret[0].type = C_STRING;
sprintf(buf, "%d", params->w);
ret[0].u.string.sval = dupstr(buf);
ret[1].name = "Height";
ret[1].type = C_STRING;
sprintf(buf, "%d", params->h);
ret[1].u.string.sval = dupstr(buf);
ret[2].name = "Regions";
ret[2].type = C_STRING;
sprintf(buf, "%d", params->n);
ret[2].u.string.sval = dupstr(buf);
ret[3].name = "Difficulty";
ret[3].type = C_CHOICES;
ret[3].u.choices.choicenames = DIFFCONFIG;
ret[3].u.choices.selected = params->diff;
ret[4].name = NULL;
ret[4].type = C_END;
return ret;
}
static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
ret->w = atoi(cfg[0].u.string.sval);
ret->h = atoi(cfg[1].u.string.sval);
ret->n = atoi(cfg[2].u.string.sval);
ret->diff = cfg[3].u.choices.selected;
return ret;
}
static const char *validate_params(const game_params *params, bool full)
{
if (params->w < 2 || params->h < 2)
return "Width and height must be at least two";
if (params->w > INT_MAX / 2 / params->h)
return "Width times height must not be unreasonably large";
if (params->n < 5)
return "Must have at least five regions";
if (params->n > params->w * params->h)
return "Too many regions to fit in grid";
return NULL;
}
/* ----------------------------------------------------------------------
* Cumulative frequency table functions.
*/
/*
* Initialise a cumulative frequency table. (Hardly worth writing
* this function; all it does is to initialise everything in the
* array to zero.)
*/
static void cf_init(int *table, int n)
{
int i;
for (i = 0; i < n; i++)
table[i] = 0;
}
/*
* Increment the count of symbol `sym' by `count'.
*/
static void cf_add(int *table, int n, int sym, int count)
{
int bit;
bit = 1;
while (sym != 0) {
if (sym & bit) {
table[sym] += count;
sym &= ~bit;
}
bit <<= 1;
}
table[0] += count;
}
/*
* Cumulative frequency lookup: return the total count of symbols
* with value less than `sym'.
*/
static int cf_clookup(int *table, int n, int sym)
{
int bit, index, limit, count;
if (sym == 0)
return 0;
assert(0 < sym && sym <= n);
count = table[0]; /* start with the whole table size */
bit = 1;
while (bit < n)
bit <<= 1;
limit = n;
while (bit > 0) {
/*
* Find the least number with its lowest set bit in this
* position which is greater than or equal to sym.
*/
index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
if (index < limit) {
count -= table[index];
limit = index;
}
bit >>= 1;
}
return count;
}
/*
* Single frequency lookup: return the count of symbol `sym'.
*/
static int cf_slookup(int *table, int n, int sym)
{
int count, bit;
assert(0 <= sym && sym < n);
count = table[sym];
for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
count -= table[sym+bit];
return count;
}
/*
* Return the largest symbol index such that the cumulative
* frequency up to that symbol is less than _or equal to_ count.
*/
static int cf_whichsym(int *table, int n, int count) {
int bit, sym, top;
assert(count >= 0 && count < table[0]);
bit = 1;
while (bit < n)
bit <<= 1;
sym = 0;
top = table[0];
while (bit > 0) {
if (sym+bit < n) {
if (count >= top - table[sym+bit])
sym += bit;
else
top -= table[sym+bit];
}
bit >>= 1;
}
return sym;
}
| 