1 files changed, 599 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/spectre.c b/apps/plugins/puzzles/src/spectre.c
new file mode 100644
index 0000000000..ba72304ff2
--- /dev/null
+++ b/apps/plugins/puzzles/src/spectre.c
@@ -0,0 +1,599 @@
+/*
+ * Code to generate patches of the aperiodic 'spectre' tiling
+ * discovered in 2023.
+ *
+ * Resources about the tiling from its discoverers:
+ * https://cs.uwaterloo.ca/~csk/spectre/
+ * https://arxiv.org/abs/2305.17743
+ *
+ * Writeup of the generation algorithm:
+ * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-spectre/
+ */
+
+#include <assert.h>
+#include <string.h>
+
+#include "puzzles.h"
+#include "tree234.h"
+
+#include "spectre-internal.h"
+
+#include "spectre-tables-manual.h"
+#include "spectre-tables-auto.h"
+
+static const char *const letters =
+    #define STRINGIFY(x) #x
+    HEX_LETTERS(STRINGIFY)
+    #undef STRINGIFY
+    ;
+
+bool spectre_valid_hex_letter(char letter)
+{
+    return strchr(letters, letter) != NULL;
+}
+
+static Hex hex_from_letter(char letter)
+{
+    char buf[2];
+    buf[0] = letter;
+    buf[1] = '\0';
+    return strcspn(letters, buf);
+}
+
+static Hex hex_to_letter(unsigned char letter)
+{
+    return letters[letter];
+}
+
+struct HexData {
+    const struct MapEntry *hexmap, *hexin, *specmap, *specin;
+    const struct MapEdge *hexedges, *specedges;
+    const Hex *subhexes;
+    const struct Possibility *poss;
+    size_t nposs;
+};
+
+static const struct HexData hexdata[] = {
+    #define HEXDATA_ENTRY(x) { hexmap_##x, hexin_##x, specmap_##x, \
+            specin_##x, hexedges_##x, specedges_##x, subhexes_##x, \
+            poss_##x, lenof(poss_##x) },
+    HEX_LETTERS(HEXDATA_ENTRY)
+    #undef HEXDATA_ENTRY
+};
+
+static const struct Possibility *choose_poss(
+    random_state *rs, const struct Possibility *poss, size_t nposs)
+{
+    /*
+     * If we needed to do this _efficiently_, we'd rewrite all those
+     * tables above as cumulative frequency tables and use binary
+     * search. But this happens about log n times in a grid of area n,
+     * so it hardly matters, and it's easier to keep the tables
+     * legible.
+     */
+    unsigned long limit = 0, value;
+    size_t i;
+
+    for (i = 0; i < nposs; i++)
+        limit += poss[i].prob;
+
+    value = random_upto(rs, limit);
+
+    for (i = 0; i+1 < nposs; i++) {
+        if (value < poss[i].prob)
+            return &poss[i];
+        value -= poss[i].prob;
+    }
+
+    assert(i == nposs - 1);
+    assert(value < poss[i].prob);
+    return &poss[i];
+}
+
+SpectreCoords *spectre_coords_new(void)
+{
+    SpectreCoords *sc = snew(SpectreCoords);
+    sc->nc = sc->csize = 0;
+    sc->c = NULL;
+    return sc;
+}
+
+void spectre_coords_free(SpectreCoords *sc)
+{
+    if (sc) {
+        sfree(sc->c);
+        sfree(sc);
+    }
+}
+
+void spectre_coords_make_space(SpectreCoords *sc, size_t size)
+{
+    if (sc->csize < size) {
+        sc->csize = sc->csize * 5 / 4 + 16;
+        if (sc->csize < size)
+            sc->csize = size;
+        sc->c = sresize(sc->c, sc->csize, HexCoord);
+    }
+}
+
+SpectreCoords *spectre_coords_copy(SpectreCoords *sc_in)
+{
+    SpectreCoords *sc_out = spectre_coords_new();
+    spectre_coords_make_space(sc_out, sc_in->nc);
+    memcpy(sc_out->c, sc_in->c, sc_in->nc * sizeof(*sc_out->c));
+    sc_out->nc = sc_in->nc;
+    sc_out->index = sc_in->index;
+    sc_out->hex_colour = sc_in->hex_colour;
+    sc_out->prev_hex_colour = sc_in->prev_hex_colour;
+    sc_out->incoming_hex_edge = sc_in->incoming_hex_edge;
+    return sc_out;
+}
+
+void spectre_place(Spectre *spec, Point u, Point v, int index_of_u)
+{
+    size_t i;
+    Point disp;
+
+    /* Vector from u to v */
+    disp = point_sub(v, u);
+
+    for (i = 0; i < 14; i++) {
+        spec->vertices[(i + index_of_u) % 14] = u;
+        u = point_add(u, disp);
+        disp = point_mul(disp, point_rot(
+                             spectre_angles[(i + 1 + index_of_u) % 14]));
+    }
+}
+
+Spectre *spectre_initial(SpectreContext *ctx)
+{
+    Spectre *spec = snew(Spectre);
+    spectre_place(spec, ctx->start_vertices[0], ctx->start_vertices[1], 0);
+    spec->sc = spectre_coords_copy(ctx->prototype);
+    return spec;
+}
+
+Spectre *spectre_adjacent(SpectreContext *ctx, const Spectre *src_spec,
+                          unsigned src_edge, unsigned *dst_edge_out)
+{
+    unsigned dst_edge;
+    Spectre *dst_spec = snew(Spectre);
+    dst_spec->sc = spectre_coords_copy(src_spec->sc);
+    spectrectx_step(ctx, dst_spec->sc, src_edge, &dst_edge);
+    spectre_place(dst_spec, src_spec->vertices[(src_edge+1) % 14],
+                  src_spec->vertices[src_edge], dst_edge);
+    if (dst_edge_out)
+        *dst_edge_out = dst_edge;
+    return dst_spec;
+}
+
+static int spectre_cmp(void *av, void *bv)
+{
+    Spectre *a = (Spectre *)av, *b = (Spectre *)bv;
+    size_t i, j;
+
+    /* We should only ever need to compare the first two vertices of
+     * any Spectre, because those force the rest */
+    for (i = 0; i < 2; i++) {
+        for (j = 0; j < 4; j++) {
+            int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j];
+            if (ac < bc)
+                return -1;
+            if (ac > bc)
+                return +1;
+        }
+    }
+
+    return 0;
+}
+
+void spectre_free(Spectre *spec)
+{
+    spectre_coords_free(spec->sc);
+    sfree(spec);
+}
+
+static void spectrectx_start_vertices(SpectreContext *ctx, int orientation)
+{
+    Point minus_sqrt3 = point_add(point_rot(5), point_rot(-5));
+    Point basicedge = point_mul(point_add(point_rot(0), point_rot(-3)),
+                                point_rot(orientation));
+    Point diagonal = point_add(basicedge, point_mul(basicedge, point_rot(-3)));
+    ctx->start_vertices[0] = point_mul(diagonal, minus_sqrt3);
+    ctx->start_vertices[1] = point_add(ctx->start_vertices[0], basicedge);
+    ctx->orientation = orientation;
+}
+
+void spectrectx_init_random(SpectreContext *ctx, random_state *rs)
+{
+    const struct Possibility *poss;
+
+    ctx->rs = rs;
+    ctx->must_free_rs = false;
+    ctx->prototype = spectre_coords_new();
+    spectre_coords_make_space(ctx->prototype, 1);
+    poss = choose_poss(rs, poss_spectre, lenof(poss_spectre));
+    ctx->prototype->index = poss->lo;
+    ctx->prototype->c[0].type = poss->hi;
+    ctx->prototype->c[0].index = -1;
+    ctx->prototype->nc = 1;
+
+    /*
+     * Choose a random orientation for the starting Spectre.
+     *
+     * The obvious thing is to choose the orientation out of all 12
+     * possibilities. But we do it a more complicated way.
+     *
+     * The Spectres in a tiling can be partitioned into two
+     * equivalence classes under the relation 'orientation differs by
+     * a multiple of 1/6 turn'. One class is much more common than the
+     * other class: the 'odd'-orientation Spectres occur rarely (very
+     * like the rare reflected hats in the hats tiling).
+     *
+     * I think it's nicer to arrange that there's a consistent
+     * orientation for the _common_ class of Spectres, so that there
+     * will always be plenty of them in the 'canonical' orientation
+     * with the head upwards. So if the starting Spectre is in the
+     * even class, we pick an even orientation for it, and if it's in
+     * the odd class, we pick an odd orientation.
+     *
+     * An odd-class Spectre is easy to identify from SpectreCoords.
+     * They're precisely the ones expanded from a G hex with index 1,
+     * which means they're the ones that have index 1 _at all_.
+     */
+    spectrectx_start_vertices(ctx, random_upto(rs, 6) * 2 +
+                              ctx->prototype->index);
+
+    /* Initialiise the colouring fields deterministically but unhelpfully.
+     * spectre-test will set these up properly if it wants to */
+    ctx->prototype->hex_colour = 0;
+    ctx->prototype->prev_hex_colour = 0;
+    ctx->prototype->incoming_hex_edge = 0;
+}
+
+void spectrectx_init_from_params(
+    SpectreContext *ctx, const struct SpectrePatchParams *ps)
+{
+    size_t i;
+
+    ctx->rs = NULL;
+    ctx->must_free_rs = false;
+    ctx->prototype = spectre_coords_new();
+    spectre_coords_make_space(ctx->prototype, ps->ncoords);
+
+    ctx->prototype->index = ps->coords[0];
+    for (i = 1; i < ps->ncoords; i++)
+        ctx->prototype->c[i-1].index = ps->coords[i];
+    ctx->prototype->c[ps->ncoords-1].index = -1;
+    ctx->prototype->nc = ps->ncoords;
+
+    ctx->prototype->c[ps->ncoords-1].type = hex_from_letter(ps->final_hex);
+    for (i = ps->ncoords - 1; i-- > 0 ;) {
+        const struct HexData *h = &hexdata[ctx->prototype->c[i+1].type];
+        ctx->prototype->c[i].type = h->subhexes[ctx->prototype->c[i].index];
+    }
+
+    spectrectx_start_vertices(ctx, ps->orientation);
+
+    ctx->prototype->hex_colour = 0;
+    ctx->prototype->prev_hex_colour = 0;
+    ctx->prototype->incoming_hex_edge = 0;
+}
+
+void spectrectx_cleanup(SpectreContext *ctx)
+{
+    if (ctx->must_free_rs)
+        random_free(ctx->rs);
+    spectre_coords_free(ctx->prototype);
+}
+
+SpectreCoords *spectrectx_initial_coords(SpectreContext *ctx)
+{
+    return spectre_coords_copy(ctx->prototype);
+}
+
+/*
+ * Extend sc until it has at least n coordinates in, by copying from
+ * ctx->prototype if needed, and extending ctx->prototype if needed in
+ * order to do that.
+ */
+void spectrectx_extend_coords(SpectreContext *ctx, SpectreCoords *sc, size_t n)
+{
+    if (ctx->prototype->nc < n) {
+        spectre_coords_make_space(ctx->prototype, n);
+        while (ctx->prototype->nc < n) {
+            const struct HexData *h = &hexdata[
+                ctx->prototype->c[ctx->prototype->nc-1].type];
+            const struct Possibility *poss;
+
+            if (!ctx->rs) {
+                /*
+                 * If there's no random_state available, it must be
+                 * because we were given an explicit coordinate string
+                 * and ran off the end of it.
+                 *
+                 * The obvious thing to do here would be to make up an
+                 * answer non-randomly. But in fact there's a danger
+                 * that this leads to endless recursion within a
+                 * single coordinate step, if the hex edge we were
+                 * trying to traverse turns into another copy of
+                 * itself at the higher level. That happened in early
+                 * testing before I put the random_state in at all.
+                 *
+                 * To avoid that risk, in this situation - which
+                 * _shouldn't_ come up at all in sensibly play - we
+                 * make up a random_state, and free it when the
+                 * context goes away.
+                 */
+                ctx->rs = random_new("dummy", 5);
+                ctx->must_free_rs = true;
+            }
+
+            poss = choose_poss(ctx->rs, h->poss, h->nposs);
+            ctx->prototype->c[ctx->prototype->nc-1].index = poss->lo;
+            ctx->prototype->c[ctx->prototype->nc].type = poss->hi;
+            ctx->prototype->c[ctx->prototype->nc].index = -1;
+            ctx->prototype->nc++;
+        }
+    }
+
+    spectre_coords_make_space(sc, n);
+    while (sc->nc < n) {
+        assert(sc->c[sc->nc - 1].index == -1);
+        assert(sc->c[sc->nc - 1].type == ctx->prototype->c[sc->nc - 1].type);
+        sc->c[sc->nc - 1].index = ctx->prototype->c[sc->nc - 1].index;
+        sc->c[sc->nc].index = -1;
+        sc->c[sc->nc].type = ctx->prototype->c[sc->nc].type;
+        sc->nc++;
+    }
+}
+
+void spectrectx_step_hex(SpectreContext *ctx, SpectreCoords *sc,
+                         size_t depth, unsigned edge, unsigned *outedge)
+{
+    const struct HexData *h;
+    const struct MapEntry *m;
+
+    spectrectx_extend_coords(ctx, sc, depth+2);
+
+    assert(0 <= sc->c[depth].index);
+    assert(sc->c[depth].index < num_subhexes(sc->c[depth].type));
+    assert(0 <= edge);
+    assert(edge < 6);
+
+    h = &hexdata[sc->c[depth+1].type];
+    m = &h->hexmap[6 * sc->c[depth].index + edge];
+    if (!m->internal) {
+        unsigned recedge;
+        const struct MapEdge *me;
+        spectrectx_step_hex(ctx, sc, depth+1, m->hi, &recedge);
+        assert(recedge < 6);
+        h = &hexdata[sc->c[depth+1].type];
+        me = &h->hexedges[recedge];
+        assert(m->lo < me->len);
+        m = &h->hexin[me->startindex + me->len - 1 - m->lo];
+        assert(m->internal);
+    }
+    sc->c[depth].index = m->hi;
+    sc->c[depth].type = h->subhexes[sc->c[depth].index];
+    *outedge = m->lo;
+
+    if (depth == 0) {
+        /*
+         * Update the colouring fields to track the colour of the new
+         * hexagon.
+         */
+        unsigned char new_hex_colour;
+
+        if (!((edge ^ sc->incoming_hex_edge) & 1)) {
+            /* We're going out via the same parity of edge we came in
+             * on, so the new hex colour is the same as the previous
+             * one. */
+            new_hex_colour = sc->prev_hex_colour;
+        } else {
+            /* We're going out via the opposite parity of edge, so the
+             * new colour is the one of {0,1,2} that is neither this
+             * _nor_ the previous colour. */
+            new_hex_colour = 0+1+2 - sc->hex_colour - sc->prev_hex_colour;
+        }
+
+        sc->prev_hex_colour = sc->hex_colour;
+        sc->hex_colour = new_hex_colour;
+        sc->incoming_hex_edge = m->lo;
+    }
+}
+
+void spectrectx_step(SpectreContext *ctx, SpectreCoords *sc,
+                     unsigned edge, unsigned *outedge)
+{
+    const struct HexData *h;
+    const struct MapEntry *m;
+
+    assert(0 <= sc->index);
+    assert(sc->index < num_spectres(sc->c[0].type));
+    assert(0 <= edge);
+    assert(edge < 14);
+
+    h = &hexdata[sc->c[0].type];
+    m = &h->specmap[14 * sc->index + edge];
+
+    while (!m->internal) {
+        unsigned recedge;
+        const struct MapEdge *me;
+        spectrectx_step_hex(ctx, sc, 0, m->hi, &recedge);
+        assert(recedge < 6);
+        h = &hexdata[sc->c[0].type];
+        me = &h->specedges[recedge];
+        assert(m->lo < me->len);
+        m = &h->specin[me->startindex + me->len - 1 - m->lo];
+    }
+    sc->index = m->hi;
+    *outedge = m->lo;
+}
+
+void spectrectx_generate(SpectreContext *ctx,
+                         bool (*callback)(void *cbctx, const Spectre *spec),
+                         void *cbctx)
+{
+    tree234 *placed = newtree234(spectre_cmp);
+    Spectre *qhead = NULL, *qtail = NULL;
+
+    {
+        Spectre *spec = spectre_initial(ctx);
+
+        add234(placed, spec);
+
+        spec->next = NULL;
+
+        if (callback(cbctx, spec))
+            qhead = qtail = spec;
+    }
+
+    while (qhead) {
+        unsigned edge;
+        Spectre *spec = qhead;
+
+        for (edge = 0; edge < 14; edge++) {
+            Spectre *new_spec;
+
+            new_spec = spectre_adjacent(ctx, spec, edge, NULL);
+
+            if (find234(placed, new_spec, NULL)) {
+                spectre_free(new_spec);
+                continue;
+            }
+
+            if (!callback(cbctx, new_spec)) {
+                spectre_free(new_spec);
+                continue;
+            }
+
+            add234(placed, new_spec);
+            qtail->next = new_spec;
+            qtail = new_spec;
+            new_spec->next = NULL;
+        }
+
+        qhead = qhead->next;
+    }
+
+    {
+        Spectre *spec;
+        while ((spec = delpos234(placed, 0)) != NULL)
+            spectre_free(spec);
+        freetree234(placed);
+    }
+}
+
+const char *spectre_tiling_params_invalid(
+    const struct SpectrePatchParams *params)
+{
+    size_t i;
+    Hex h;
+
+    if (params->ncoords == 0)
+        return "expected at least one numeric coordinate";
+    if (!spectre_valid_hex_letter(params->final_hex))
+        return "invalid final hexagon type";
+
+    h = hex_from_letter(params->final_hex);
+    for (i = params->ncoords; i-- > 0 ;) {
+        unsigned limit = (i == 0) ? num_spectres(h) : num_subhexes(h);
+        if (params->coords[i] >= limit)
+            return "coordinate out of range";
+
+        if (i > 0)
+            h = hexdata[h].subhexes[params->coords[i]];
+    }
+
+    return NULL;
+}
+
+struct SpectreCallbackContext {
+    int xoff, yoff;
+    Coord xmin, xmax, ymin, ymax;
+
+    spectre_tile_callback_fn external_cb;
+    void *external_cbctx;
+};
+
+static bool spectre_internal_callback(void *vctx, const Spectre *spec)
+{
+    struct SpectreCallbackContext *ctx = (struct SpectreCallbackContext *)vctx;
+    size_t i;
+    int output_coords[4*14];
+
+    for (i = 0; i < 14; i++) {
+        Point p = spec->vertices[i];
+        Coord x = point_x(p), y = point_y(p);
+        if (coord_cmp(x, ctx->xmin) < 0 || coord_cmp(x, ctx->xmax) > 0 ||
+            coord_cmp(y, ctx->ymin) < 0 || coord_cmp(y, ctx->ymax) > 0)
+            return false;
+
+        output_coords[4*i + 0] = ctx->xoff + x.c1;
+        output_coords[4*i + 1] = x.cr3;
+        output_coords[4*i + 2] = ctx->yoff - y.c1;
+        output_coords[4*i + 3] = -y.cr3;
+    }
+
+    if (ctx->external_cb)
+        ctx->external_cb(ctx->external_cbctx, output_coords);
+
+    return true;
+}
+
+static void spectre_set_bounds(struct SpectreCallbackContext *cbctx,
+                               int w, int h)
+{
+    cbctx->xoff = w/2;
+    cbctx->yoff = h/2;
+    cbctx->xmin.c1 = -cbctx->xoff;
+    cbctx->xmax.c1 = -cbctx->xoff + w;
+    cbctx->ymin.c1 = cbctx->yoff - h;
+    cbctx->ymax.c1 = cbctx->yoff;
+    cbctx->xmin.cr3 = 0;
+    cbctx->xmax.cr3 = 0;
+    cbctx->ymin.cr3 = 0;
+    cbctx->ymax.cr3 = 0;
+}
+
+void spectre_tiling_randomise(struct SpectrePatchParams *ps, int w, int h,
+                              random_state *rs)
+{
+    SpectreContext ctx[1];
+    struct SpectreCallbackContext cbctx[1];
+    size_t i;
+
+    spectre_set_bounds(cbctx, w, h);
+    cbctx->external_cb = NULL;
+    cbctx->external_cbctx = NULL;
+
+    spectrectx_init_random(ctx, rs);
+    spectrectx_generate(ctx, spectre_internal_callback, cbctx);
+
+    ps->orientation = ctx->orientation;
+    ps->ncoords = ctx->prototype->nc;
+    ps->coords = snewn(ps->ncoords, unsigned char);
+    ps->coords[0] = ctx->prototype->index;
+    for (i = 1; i < ps->ncoords; i++)
+        ps->coords[i] = ctx->prototype->c[i-1].index;
+    ps->final_hex = hex_to_letter(ctx->prototype->c[ps->ncoords-1].type);
+
+    spectrectx_cleanup(ctx);
+}
+
+void spectre_tiling_generate(
+    const struct SpectrePatchParams *params, int w, int h,
+    spectre_tile_callback_fn external_cb, void *external_cbctx)
+{
+    SpectreContext ctx[1];
+    struct SpectreCallbackContext cbctx[1];
+
+    spectre_set_bounds(cbctx, w, h);
+    cbctx->external_cb = external_cb;
+    cbctx->external_cbctx = external_cbctx;
+
+    spectrectx_init_from_params(ctx, params);
+    spectrectx_generate(ctx, spectre_internal_callback, cbctx);
+    spectrectx_cleanup(ctx);
+}