1 files changed, 271 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/hat-internal.h b/apps/plugins/puzzles/src/hat-internal.h
new file mode 100644
index 0000000000..2be96327a8
--- /dev/null
+++ b/apps/plugins/puzzles/src/hat-internal.h
@@ -0,0 +1,271 @@
+/*
+ * Internal definitions for the hat.c tiling generator, shared between
+ * hat.c itself and hat-test.c.
+ */
+
+#include "puzzles.h"
+
+/*
+ * Coordinate system:
+ *
+ * The output of this code lives on the tiling known to grid.c as
+ * 'Kites', which can be viewed as a tiling of hexagons each of which
+ * is subdivided into six kites sharing their pointy vertex, or
+ * (equivalently) a tiling of equilateral triangles each subdivided
+ * into three kits sharing their blunt vertex.
+ *
+ * We express coordinates in this system relative to the basis (1, r)
+ * where r = (1 + sqrt(3)i) / 2 is a primitive 6th root of unity. This
+ * gives us a system in which two integer coordinates can address any
+ * grid point, provided we scale up so that the side length of the
+ * equilateral triangles in the tiling is 6.
+ */
+
+typedef struct Point {
+    int x, y;                          /* represents x + yr */
+} Point;
+
+static inline Point pointscale(int scale, Point a)
+{
+    Point r = { scale * a.x, scale * a.y };
+    return r;
+}
+
+static inline Point pointadd(Point a, Point b)
+{
+    Point r = { a.x + b.x, a.y + b.y };
+    return r;
+}
+
+/*
+ * We identify a single kite by the coordinates of its four vertices.
+ * This allows us to construct the coordinates of an adjacent kite by
+ * taking affine transformations of the original kite's vertices.
+ *
+ * This is a useful way to do it because it means that if you reflect
+ * the kite (by swapping its left and right vertices) then these
+ * transformations also perform in a reflected way. This will be
+ * useful in the code below that outputs the coordinates of each hat,
+ * because this way it can work by walking around its 8 kites using a
+ * fixed set of steps, and if the hat is reflected, then we just
+ * reflect the starting kite before doing that, and everything still
+ * works.
+ */
+
+typedef struct Kite {
+    Point centre, left, right, outer;
+} Kite;
+
+static inline Kite kite_left(Kite k)
+{
+    Kite r;
+    r.centre = k.centre;
+    r.right = k.left;
+    r.outer = pointadd(pointscale(2, k.left), pointscale(-1, k.outer));
+    r.left = pointadd(pointadd(k.centre, k.left), pointscale(-1, k.right));
+    return r;
+}
+
+static inline Kite kite_right(Kite k)
+{
+    Kite r;
+    r.centre = k.centre;
+    r.left = k.right;
+    r.outer = pointadd(pointscale(2, k.right), pointscale(-1, k.outer));
+    r.right = pointadd(pointadd(k.centre, k.right), pointscale(-1, k.left));
+    return r;
+}
+
+static inline Kite kite_forward_left(Kite k)
+{
+    Kite r;
+    r.outer = k.outer;
+    r.right = k.left;
+    r.centre = pointadd(pointscale(2, k.left), pointscale(-1, k.centre));
+    r.left = pointadd(pointadd(k.right, k.left), pointscale(-1, k.centre));
+    return r;
+}
+
+static inline Kite kite_forward_right(Kite k)
+{
+    Kite r;
+    r.outer = k.outer;
+    r.left = k.right;
+    r.centre = pointadd(pointscale(2, k.right), pointscale(-1, k.centre));
+    r.right = pointadd(pointadd(k.left, k.right), pointscale(-1, k.centre));
+    return r;
+}
+
+typedef enum KiteStep { KS_LEFT, KS_RIGHT, KS_F_LEFT, KS_F_RIGHT } KiteStep;
+
+static inline Kite kite_step(Kite k, KiteStep step)
+{
+    switch (step) {
+      case KS_LEFT: return kite_left(k);
+      case KS_RIGHT: return kite_right(k);
+      case KS_F_LEFT: return kite_forward_left(k);
+      default /* case KS_F_RIGHT */: return kite_forward_right(k);
+    }
+}
+
+/*
+ * Functiond to enumerate the kites in a rectangular region, in a
+ * serpentine-raster fashion so that every kite delivered shares an
+ * edge with a recent previous one.
+ */
+#define KE_NKEEP 3
+typedef struct KiteEnum {
+    /* Fields private to the enumerator */
+    int state;
+    int x, y, w, h;
+    unsigned curr_index;
+
+    /* Fields the client can legitimately read out */
+    Kite *curr;
+    Kite recent[KE_NKEEP];
+    unsigned last_index;
+    KiteStep last_step; /* step that got curr from recent[last_index] */
+} KiteEnum;
+void hat_kiteenum_first(KiteEnum *s, int w, int h);
+bool hat_kiteenum_next(KiteEnum *s);
+
+/*
+ * Assorted useful definitions.
+ */
+typedef enum TileType { TT_H, TT_T, TT_P, TT_F, TT_KITE, TT_HAT } TileType;
+static const char tilechars[] = "HTPF";
+
+#define HAT_KITES 8     /* number of kites in a hat */
+#define MT_MAXEXPAND 13 /* largest number of metatiles in any expansion */
+
+/*
+ * Definitions for the autogenerated hat-tables.h header file that
+ * defines all the lookup tables.
+ */
+typedef struct KitemapEntry {
+    int kite, hat, meta;               /* all -1 if impossible */
+} KitemapEntry;
+
+typedef struct MetamapEntry {
+    int meta, meta2;
+} MetamapEntry;
+
+static inline size_t kitemap_index(KiteStep step, unsigned kite,
+                                   unsigned hat, unsigned meta)
+{
+    return step + 4 * (kite + 8 * (hat + 4 * meta));
+}
+
+static inline size_t metamap_index(unsigned meta, unsigned meta2)
+{
+    return meta2 * MT_MAXEXPAND + meta;
+}
+
+/*
+ * Coordinate system for tracking kites within a randomly selected
+ * part of the recursively expanded hat tiling.
+ *
+ * HatCoords will store an array of HatCoord, in little-endian
+ * arrangement. So hc->c[0] will always have type TT_KITE and index a
+ * single kite within a hat; hc->c[1] will have type TT_HAT and index
+ * a hat within a first-order metatile; hc->c[2] will be the smallest
+ * metatile containing this hat, and hc->c[3, 4, 5, ...] will be
+ * higher-order metatiles as needed.
+ *
+ * The last coordinate stored, hc->c[hc->nc-1], will have a tile type
+ * but no index (represented by index==-1). This means "we haven't
+ * decided yet what this level of metatile needs to be". If we need to
+ * refer to this level during the hatctx_step algorithm, we make it up
+ * at random, based on a table of what metatiles each type can
+ * possibly be part of, at what index.
+ */
+typedef struct HatCoord {
+    int index; /* index within that tile, or -1 if not yet known */
+    TileType type;  /* type of this tile */
+} HatCoord;
+
+typedef struct HatCoords {
+    HatCoord *c;
+    size_t nc, csize;
+} HatCoords;
+
+HatCoords *hat_coords_new(void);
+void hat_coords_free(HatCoords *hc);
+void hat_coords_make_space(HatCoords *hc, size_t size);
+HatCoords *hat_coords_copy(HatCoords *hc_in);
+
+#ifdef HAT_COORDS_DEBUG
+static inline void hat_coords_debug(const char *prefix, HatCoords *hc,
+                                    const char *suffix)
+{
+    const char *sep = "";
+    static const char *const types[] = {"H","T","P","F","kite","hat"};
+
+    fputs(prefix, stderr);
+    for (size_t i = 0; i < hc->nc; i++) {
+        fprintf(stderr, "%s %s ", sep, types[hc->c[i].type]);
+        sep = " .";
+        if (hc->c[i].index == -1)
+            fputs("?", stderr);
+        else
+            fprintf(stderr, "%d", hc->c[i].index);
+    }
+    fputs(suffix, stderr);
+}
+#else
+#define hat_coords_debug(p,c,s) ((void)0)
+#endif
+
+/*
+ * HatContext is the shared context of a whole run of the algorithm.
+ * Its 'prototype' HatCoords object represents the coordinates of the
+ * starting kite, and is extended as necessary; any other HatCoord
+ * that needs extending will copy the higher-order values from
+ * ctx->prototype as needed, so that once each choice has been made,
+ * it remains consistent.
+ *
+ * When we're inventing a random piece of tiling in the first place,
+ * we append to ctx->prototype by choosing a random (but legal)
+ * higher-level metatile for the current topmost one to turn out to be
+ * part of. When we're replaying a generation whose parameters are
+ * already stored, we don't have a random_state, and we make fixed
+ * decisions if not enough coordinates were provided.
+ *
+ * (Of course another approach would be to reject grid descriptions
+ * that didn't define enough coordinates! But that would involve a
+ * whole extra iteration over the whole grid region just for
+ * validation, and that seems like more timewasting than really
+ * needed. So we tolerate short descriptions, and do something
+ * deterministic with them.)
+ */
+
+typedef struct HatContext {
+    random_state *rs;
+    HatCoords *prototype;
+} HatContext;
+
+void hatctx_init_random(HatContext *ctx, random_state *rs);
+void hatctx_cleanup(HatContext *ctx);
+HatCoords *hatctx_initial_coords(HatContext *ctx);
+void hatctx_extend_coords(HatContext *ctx, HatCoords *hc, size_t n);
+HatCoords *hatctx_step(HatContext *ctx, HatCoords *hc_in, KiteStep step);
+
+/*
+ * Subroutine of hat_tiling_generate, called for each kite in the grid
+ * as we iterate over it, to decide whether to generate an output hat
+ * and pass it to the client. Exposed in this header file so that
+ * hat-test can reuse it.
+ *
+ * We do this by starting from kite #0 of each hat, and tracing round
+ * the boundary. If the whole boundary is within the caller's bounding
+ * region, we return it; if it goes off the edge, we don't.
+ *
+ * (Of course, every hat we _do_ want to return will have all its
+ * kites inside the rectangle, so its kite #0 will certainly be caught
+ * by this iteration.)
+ */
+
+typedef void (*internal_hat_callback_fn)(void *ctx, Kite kite0, HatCoords *hc,
+                                         int *coords);
+void maybe_report_hat(int w, int h, Kite kite, HatCoords *hc,
+                      internal_hat_callback_fn cb, void *cbctx);