X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mm/blobdiff_plain/7a869046513cff8cf3c3ccea0c28d2ccab29b868..0fd4f3753c6a4e596f4635ac75fdb1e3730ede64:/mm.c diff --git a/mm.c b/mm.c index e25f5d4..7ed9b16 100644 --- a/mm.c +++ b/mm.c @@ -28,6 +28,7 @@ /*----- Header files ------------------------------------------------------*/ +#include #include #include #include @@ -35,6 +36,7 @@ #include #include +#include #include #include #include @@ -115,6 +117,7 @@ static void rate_init(ratectx *r, const dig *s) static ratectx *rate_new(const mm *m, const dig *s) { ratectx *r = rate_alloc(m); + rate_init(r, s); return (r); } @@ -144,11 +147,7 @@ static void rate(const ratectx *r, const dig *g, unsigned *b, unsigned *w) *w = ww; } -static void rate_free(ratectx *r) -{ - xfree(r->v); - DESTROY(r); -} +static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); } /*----- Computer player ---------------------------------------------------*/ @@ -177,6 +176,8 @@ static void rate_free(ratectx *r) typedef struct cpc { mm m; /* Game parameters */ + unsigned f; /* Various flags */ +#define CPCF_QUIET 1u /* Don't produce lots of output */ dig *s; /* n^k * k */ /* Remaining guesses */ size_t ns; /* Number of remaining guesses */ dig *bg; /* k */ /* Current best guess */ @@ -222,6 +223,7 @@ static void foreach_proto(cpc *c, void (*fn)(cpc *c, unsigned x)) { unsigned k = c->m.k, n = c->m.n; + dofep(c, fn, k, n, 0, c->x); } @@ -315,19 +317,25 @@ static void all_guesses(dig **ss, unsigned k, unsigned n, } } -#define THINK(what, how) do { \ - clock_t _t0, _t1; \ - fputs(what "...", stdout); \ - fflush(stdout); \ - _t0 = clock(); \ +#define THINK(c, what, how) do { \ + clock_t _t0 = 0, _t1; \ + if (!(c->f & CPCF_QUIET)) { \ + fputs(what "...", stdout); \ + fflush(stdout); \ + _t0 = clock(); \ + } \ do how while (0); \ - _t1 = clock(); \ - printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \ + if (!(c->f & CPCF_QUIET)) { \ + _t1 = clock(); \ + printf(" done (%.2fs)\n", (_t1 - _t0)/(double)CLOCKS_PER_SEC); \ + } \ } while (0) -static cpc *cpc_new(const mm *m) +static cpc *cpc_new(const mm *m, unsigned f) { cpc *c = CREATE(cpc); + + c->f = f; c->m = *m; c->ns = ipow(c->m.n, c->m.k); c->s = xmalloc((c->ns + 2) * c->m.k * sizeof(dig)); @@ -336,7 +344,7 @@ static cpc *cpc_new(const mm *m) c->x = 0; c->v = xmalloc((c->m.k + 1) * (c->m.k + 1) * sizeof(size_t)); c->r = rate_alloc(m); - THINK("Setting up", { + THINK(c, "Setting up", { dig *ss = c->s; all_guesses(&ss, c->m.k, c->m.n, 0, 0); }); return (c); @@ -351,36 +359,39 @@ static void cpc_free(cpc *c) } static void cp_rate(void *r, const dig *g, unsigned *b, unsigned *w) -{ - rate(r, g, b, w); -} + { rate(r, g, b, w); } static const dig *cp_guess(void *cc) { cpc *c = cc; if (c->ns == 0) { - printf("Liar! All solutions ruled out.\n"); + if (!(c->f & CPCF_QUIET)) + printf("Liar! All solutions ruled out.\n"); return (0); } if (c->ns == 1) { - fputs("Done! Solution is ", stdout); - print_guess(&c->m, c->s); - putchar('\n'); + if (!(c->f & CPCF_QUIET)) { + fputs("Done! Solution is ", stdout); + print_guess(&c->m, c->s); + putchar('\n'); + } return (c->s); } - printf("(Possible solutions remaining = %lu)\n", - (unsigned long)c->ns); - if (c->ns < 32) { - const dig *s; - size_t i; - for (i = c->ns, s = c->s; i; i--, s += c->m.k) { - printf(" %2lu: ", (unsigned long)(c->ns - i + 1)); - print_guess(&c->m, s); - putchar('\n'); + if (!(c->f & CPCF_QUIET)) { + printf("(Possible solutions remaining = %lu)\n", + (unsigned long)c->ns); + if (c->ns < 32) { + const dig *s; + size_t i; + for (i = c->ns, s = c->s; i; i--, s += c->m.k) { + printf(" %2lu: ", (unsigned long)(c->ns - i + 1)); + print_guess(&c->m, s); + putchar('\n'); + } } } - THINK("Pondering", { + THINK(c, "Pondering", { best_guess(c); }); return (c->bg); @@ -389,10 +400,13 @@ static const dig *cp_guess(void *cc) static void cp_update(void *cc, const dig *g, unsigned b, unsigned w) { cpc *c = cc; - fputs("My guess = ", stdout); - print_guess(&c->m, g); - printf("; rating = %u black, %u white\n", b, w); - THINK("Filtering", { + + if (!(c->f & CPCF_QUIET)) { + fputs("My guess = ", stdout); + print_guess(&c->m, g); + printf("; rating = %u black, %u white\n", b, w); + } + THINK(c, "Filtering", { filter_guesses(c, g, b, w); }); } @@ -459,7 +473,7 @@ typedef struct spc { static spc *spc_new(const mm *m) { spc *s = CREATE(spc); - s->c = cpc_new(m); + s->c = cpc_new(m, 0); s->h = hpc_new(m); s->i = 0; return (s); @@ -497,9 +511,99 @@ again: } static void sp_update(void *ss, const dig *g, unsigned b, unsigned w) + { spc *s = ss; cp_update(s->c, g, b, w); } + +/*----- Full tournament stuff ---------------------------------------------*/ + +DA_DECL(uint_v, unsigned); + +typedef struct allstats { + const mm *m; + unsigned f; +#define AF_VERBOSE 1u + uint_v gmap; + unsigned long g; + unsigned long n; + clock_t t; +} allstats; + +static void dorunone(allstats *a, dig *s) { - spc *s = ss; - cp_update(s->c, g, b, w); + ratectx *r = rate_new(a->m, s); + clock_t t = 0, t0, t1; + cpc *c; + int n = 0; + const dig *g; + unsigned b, w; + + if (a->f & AF_VERBOSE) { + print_guess(a->m, s); + fputs(": ", stdout); + fflush(stdout); + } + + c = cpc_new(a->m, CPCF_QUIET); + for (;;) { + t0 = clock(); + g = cp_guess(c); + t1 = clock(); + t += t1 - t0; + assert(g); + n++; + rate(r, g, &b, &w); + if (b == a->m->k) + break; + t0 = clock(); + cp_update(c, g, b, w); + t1 = clock(); + t += t1 - t0; + } + a->t += t; + a->g += n; + while (DA_LEN(&a->gmap) <= n) + DA_PUSH(&a->gmap, 0); + DA(&a->gmap)[n]++; + rate_free(r); + cpc_free(c); + + if (a->f & AF_VERBOSE) + printf("%2u (%5.2fs)\n", n, (double)t/CLOCKS_PER_SEC); +} + +static void dorunall(allstats *a, dig *s, unsigned i) +{ + dig j; + + if (i >= a->m->k) { + dorunone(a, s); + a->n++; + } else { + for (j = 0; j < a->m->n; j++) { + s[i] = j; + dorunall(a, s, i + 1); + } + } +} + +static void run_all(const mm *m) +{ + dig *s = xmalloc(m->k * sizeof(dig)); + allstats a; + unsigned i; + + a.m = m; + a.f = AF_VERBOSE; + DA_CREATE(&a.gmap); + a.n = 0; + a.g = 0; + a.t = 0; + dorunall(&a, s, 0); + xfree(s); + + for (i = 1; i < DA_LEN(&a.gmap); i++) + printf("%2u guesses: %5u games\n", i, DA(&a.gmap)[i]); + printf("Average: %.4f (%.2fs)\n", + (double)a.g/a.n, (double)a.t/(a.n * CLOCKS_PER_SEC)); } /*----- Main game logic ---------------------------------------------------*/ @@ -544,15 +648,17 @@ int main(int argc, char *argv[]) { "computer", 0, 0, 'C' }, { "human", 0, 0, 'H' }, { "solver", 0, 0, 'S' }, + { "all", 0, 0, 'a' }, { 0, 0, 0, 0 } }; - int i = mdwopt(argc, argv, "CHS", opt, 0, 0, 0); + int i = mdwopt(argc, argv, "CHSa", opt, 0, 0, 0); if (i < 0) break; switch (i) { case 'C': h = 0; break; case 'H': h = 1; break; case 'S': h = 2; break; + case 'a': h = 99; break; default: exit(1); } @@ -595,7 +701,7 @@ int main(int argc, char *argv[]) hpc_free(hh); } break; case 0: { - cpc *cc = cpc_new(&m); + cpc *cc = cpc_new(&m, 0); if (rr) n = play(&m, ratefn, rr, cp_guess, cp_update, cc); else @@ -607,6 +713,10 @@ int main(int argc, char *argv[]) n = play(&m, hp_rate, &m, sp_guess, sp_update, ss); spc_free(ss); } break; + case 99: + run_all(&m); + return (0); + break; default: abort(); }