Quilt layout solver

quilt.c

// Quilt layout solver (example)
// $ cc -o quilt quilt.c
// Ref: https://old.reddit.com/r/algorithms/comments/1dn97c0
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define countof(a) (ptrdiff_t)(sizeof(a) / sizeof(*(a)))

typedef struct {
    int32_t x;
    int32_t y;
} v2;

static v2 dirs[] = {
    {-1,-1}, {+0,-1}, {+1,-1},
    {-1,+0},          {+1,+0},
    {-1,+1}, {+0,+1}, {+1,+1},
};

typedef struct {
    uint16_t *tiles;
    int32_t   width;
    int32_t   height;
} quilt;

static uint16_t get(quilt *q, v2 p)
{
    return q->tiles[p.y*q->width + p.x];
}

static void swap(quilt *q, v2 a, v2 b)
{
    int32_t  i  = a.y*q->width + a.x;
    int32_t  j  = b.y*q->width + b.x;
    uint16_t t  = q->tiles[i];
    q->tiles[i] = q->tiles[j];
    q->tiles[j] = t;
}

static void print(quilt *q)
{
    for (int32_t y = 0; y < q->height; y++) {
        for (int32_t x = 0; x < q->width; x++) {
            uint16_t v = get(q, (v2){x, y});
            putchar('A' + (v&255));
            putchar('A' + (v>>8 ));
            putchar(' ');
        }
        putchar('\n');
    }
}

static v2 move(v2 p, int32_t d)
{
    p.x += dirs[d].x;
    p.y += dirs[d].y;
    return p;
}

static _Bool inbounds(quilt *q, v2 p)
{
    return p.x>=0 && p.x<q->width && p.y>=0 && p.y<q->height;
}

static int32_t evalat(quilt *q, v2 p)
{
    int32_t score = 0;
    for (int32_t d = 0; d < countof(dirs); d++) {
        v2 n = move(p, d);
        if (inbounds(q, n)) {
            uint16_t a = get(q, p);
            uint16_t b = get(q, n);
            score += (a&255) == (b&255);
            score += (a&255) ==  b>>8;
            score +=  a>>8   == (b&255);
            score +=  a>>8   ==  b>>8;
        }
    }
    return score;
}

static int32_t eval(quilt *q)
{
    int32_t score = 0;
    for (int32_t y = 0; y < q->height; y++) {
        for (int32_t x = 0; x < q->width; x++) {
            score += evalat(q, (v2){x, y});
        }
    }
    return score;
}

static int32_t rand32(uint64_t *s, int32_t n)
{
    *s = *s*0x3243f6a8885a308d + 1;
    return (int32_t)(((*s>>32) * n)>>32);
}

static void shuffle(quilt *q, uint64_t *rng)
{
    for (int32_t i = q->width*q->height-1; i > 0; i--) {
        int32_t  j = rand32(rng, i+1);
        uint16_t t = q->tiles[i];
        q->tiles[i] = q->tiles[j];
        q->tiles[j] = t;
    }
}

static int cmp(const void *a, const void *b)
{
    return *(uint16_t *)a - *(uint16_t *)b;
}

static void sort(quilt *q)
{
    qsort(q->tiles, q->width*q->height, sizeof(*q->tiles), cmp);
}

static v2 randv2(uint64_t *rng, quilt *q)
{
    v2 r = {0};
    r.x  = rand32(rng, q->width);
    r.y  = rand32(rng, q->height);
    return r;
}

static int64_t solve(quilt *q, uint64_t *rng)
{
    int64_t swaps = 0;

    shuffle(q, rng);

    // TODO: track the score and update intelligently from the swap info
    for (; eval(q); swaps++) {
        v2 p = randv2(rng, q);
        v2 n = move(p, rand32(rng, countof(dirs)));

        if (inbounds(q, n)) {
            int32_t old = 0;
            old += evalat(q, p);
            old += evalat(q, n);

            swap(q, n, p);

            int32_t new = 0;
            new += evalat(q, p);
            new += evalat(q, n);

            if (new > old) {
                swap(q, n, p);
                swaps--;
            }
        }
    }

    return swaps;
}

int main(void)
{
    enum { width = 9, height = 10, colors = 17, };

    quilt q  = {0};
    q.tiles  = (uint16_t[width*height]){0};
    q.width  = width;
    q.height = height;

    // Generate a random tile selection
    uint64_t rng = 1234;
    int32_t hist[colors] = {0};
    for (int32_t i = 0; i < width*height; i++) {
        uint16_t hi = (uint16_t)rand32(&rng, colors);
        uint16_t lo;
        do {
            lo = (uint16_t)rand32(&rng, colors);
        } while (lo == hi);
        q.tiles[i]  = (uint16_t)(hi<<8 | lo);
        hist[hi]++;
        hist[hi]++;
    }
    sort(&q);

    for (int32_t i = 0; i < colors; i++) {
        printf("%c =%3d%c", 'A'+i, hist[i], "\t\n"[i==colors-1 || i%9==8]);
    }
    print(&q);
    putchar('\n');

    int64_t swaps = solve(&q, &rng);
    print(&q);
    printf("score = %d\n", eval(&q));
    printf("swaps = %lld\n", (long long)swaps);
    b: return 0;
}