skeeto · June 25, 2024 01:30
diff --git a/quilt.c b/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;
 }
	// 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->widthq->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;
	}