Pipe pattern drawing

Makefile

CFLAGS += -Ofast

.PHONY: default
default: refactor

.PHONY: refactor
refactor: out.pbm
	sha256sum $< | diff -q goal.sum -

refactor-set: out.pbm
	sha256sum $< > goal.sum

.PHONY: display
display: out.png
	feh -Z $^

out.png: out.pbm Makefile
	convert $< $@

out.pbm: pipes
	./$^ > $@

pipes: pipes.c
	gcc -std=c99 $< -o $@

.PHONY: clean
clean:
	rm -r out.png out.pbm pipes

pipes.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

#define IMG_WIDTH 100
#define IMG_HEIGHT 100
#define G_WIDTH (IMG_WIDTH/2)
#define G_HEIGHT (IMG_HEIGHT/2)

#define DENSITY 45

enum newcolour {
	COLNEW_BLACK,
	COLNEW_WHITE,
	COLNEW_RED,
	COLNEW_GREEN,
	COLNEW_BLUE,
	COLNEW_PURPLE,
	COLNEW_YELLOW,
	COLNEW_CYAN,
	COLNEW__MAX,
};

char colournew_map[COLNEW__MAX + 1][3] = { /* COL_BLACK  */ {  0,   0,   0},
	                               /* COL_WHITE  */ {255, 255, 255},
	                               /* COL_RED    */ {255,   0,   0},
                                       /* COL_GREEN  */ {  0, 255,   0},
                                       /* COL_BLUE   */ {  0,   0, 255},
                                       /* COL_PURPLE */ {255,   0, 255},
                                       /* COL_YELLOW */ {255, 255,   0},
                                       /* COL_CYAN   */ {  0, 255, 255},
                                        /* ERROR */ {127, 127, 127}};

#define log(...) fprintf(stderr, __VA_ARGS__)

struct position {
	uint32_t y;
	uint32_t x;
};

void
setcomponent(
	uint64_t *comp_p,
	uint32_t width,
	uint32_t height,
	uint32_t y,
	uint32_t x,
	uint64_t old,
	uint64_t new)
{
	/* Idea: if a point should be recoloured, add each of its same-coloured
	 * neighbours to the stack and give them invalid colours, then recolour
	 * the point. Keep popping and recolouring points off the stack until
	 * it's empty.
	 */
	static struct position *stack = NULL;
	if (stack == NULL)
		stack = calloc(width * height, sizeof(*stack));
	if (stack == NULL) {
		log("Allocation failed.\n");
		exit(1);
	}

	uint64_t (*comp)[width] = (uint64_t (*)[width])comp_p;

	size_t stack_sz = 1;
	stack[0].y = y;
	stack[0].x = x;
	struct position p;

	while (stack_sz) {
		p = stack[--stack_sz];
		comp[p.y][p.x] = new;
		if (p.y > 0 && comp[p.y-1][p.x] == old) {
			stack[stack_sz].y = p.y - 1;
			stack[stack_sz].x = p.x;
			stack_sz++;
			comp[p.y-1][p.x] = -1;
		}
		if (p.y < height-1 && comp[p.y+1][p.x] == old) {
			stack[stack_sz].y = p.y + 1;
			stack[stack_sz].x = p.x;
			stack_sz++;
			comp[p.y+1][p.x] = -1;
		}
		if (p.x > 0 && comp[p.y][p.x-1] == old) {
			stack[stack_sz].y = p.y;
			stack[stack_sz].x = p.x - 1;
			stack_sz++;
			comp[p.y][p.x-1] = -1;
		}
		if (p.x < width-1 && comp[p.y][p.x+1] == old) {
			stack[stack_sz].y = p.y;
			stack[stack_sz].x = p.x + 1;
			stack_sz++;
			comp[p.y][p.x+1] = -1;
		}
	}
}

void
sixcolour(char *adj, size_t n, enum newcolour *colouring)
{
	/* We need to find a vertex with degree at most five
	 * (one must exist, since the graph is planar).
	 */
	size_t i, j;
	uint64_t d = -1;

	for (i = 0; i < n; ++i) {
		if (!adj[i * n + i])
			continue;
		d = 0;
		for (j = 0; j < i && d <= 5; ++j)
			d += adj[i * n + j];
		if (d <= 5)
			break;
	}
	/* If no vertices exist, do nothing */
	if (d == -1)
		return;
	/* Delete the ith vertex temporarily, colour the rest of the graph */
	adj[i * n + i] = 0;
	sixcolour(adj, n, colouring);
	adj[i * n + i] = 1;
	/* Pick a colour not used by neighbours */
	enum newcolour c = COLNEW_RED + (i % (COLNEW__MAX - COLNEW_RED));
	/* Todo: make this more efficient using a bitmask */
	do {
		for (j = 0; j < i; ++j) {
			if (adj[i * n + j] && colouring[j] == c) {
				c = COLNEW_RED + ((c + 1 - COLNEW_RED) % (COLNEW__MAX - COLNEW_RED));
				break;
			}
		}
	} while (j != i);
	fprintf(stderr, "%d\n", colouring[i]);
	assert(colouring[i] == 0);
	colouring[i] = c;
	if (c == 206)
		exit(1);
}

int
main(void)
{
	size_t i, j;

	uint32_t width = IMG_WIDTH;
	uint32_t height = IMG_HEIGHT;

	uint64_t (*comp)[width] = calloc(height, sizeof(*comp));

	srand(2018);

	/* Fill in the grid like this:
	 *  _______________
	 * |  #   -   -   #|
	 * |-   #   #   #  |
	 * |  #   -   #   #|
	 * |#   -   -   #  |
	 * |  #   #   -   -|
	 * |-   #   -   -  |
	 * |  #   -   #   #|
	 * |#   #   #   -  |
	 *  ---------------
	 */
	for (i = 0; i < G_HEIGHT; ++i) {
		for (j = 0; j < G_WIDTH; ++j) {
			comp[2*i+0][2*j+1] = rand() % 100 < DENSITY;
			comp[2*i+1][2*j+0] = rand() % 100 < DENSITY;
		}
	}

	/* Copy the 1st row to the 0th row,
	 * and the 1st column to the 0th column.
	 *  _______________
	 * |# # #   #   # #|
	 * |    #   #   #  |
	 * |# #       #   #|
	 * |#           #  |
	 * |# #   #        |
	 * |    #          |
	 * |# #       #   #|
	 * |#   #   #      |
	 *  ---------------
	 */
	for (i = 0; i < G_HEIGHT; ++i)
		comp[2*i][0] = comp[2*i][1];
	for (j = 0; j < G_WIDTH; ++j)
		comp[0][2*j] = comp[1][2*j];
	/* Then interpolate the remaining corners
	 *  _______________
	 * |# # #   #   # #|
	 * |    #   #   #  |
	 * |# # #   # # # #|
	 * |#           #  |
	 * |# # # # #   #  |
	 * |    #          |
	 * |# # #   # # # #|
	 * |#   #   #      |
	 *  ---------------
	 */
	for (i = 1; i < G_HEIGHT; ++i) {
		for (j = 1; j < G_WIDTH; ++j) {
			comp[2*i][2*j] = comp[2*i-1][2*j+0]
			              | comp[2*i+1][2*j+0]
				      | comp[2*i+0][2*j-1]
				      | comp[2*i+0][2*j+1];
		}
	}

	/* Recolour the segments
	 *  _______________
	 * |R R R   G   G G|
	 * |    R   G   G  |
	 * |R R R   G G G G|
	 * |R           G  |
	 * |R R R R R   G  |
	 * |    R          |
	 * |R R R   B B B B|
	 * |R   R   B      |
	 *  ---------------
	 */
	uint64_t num_components = 0;
	for (i = 0; i < IMG_HEIGHT; ++i) {
		for (j = 0; j < IMG_WIDTH; ++j) {
			if (comp[i][j] == 1)
				setcomponent(comp[0], width, height, i, j, 1, ++num_components + 1);
		}
	}

	uint64_t comp_n, comp_s, comp_e, comp_w;
	/* Form an adjacency matrix of components */
	char *adj = calloc(num_components, num_components);
	enum newcolour *colouring = calloc(num_components, sizeof(*colouring));
	for (i = 0; i < num_components; ++i) {
		adj[i * num_components + i] = 1;
	}
	for (i = 0; i < G_HEIGHT - 1; ++i) {
		for (j = 0; j < G_WIDTH - 1; ++j) {
			comp_n = comp[2*i+0][2*j+1];
			comp_s = comp[2*i+2][2*j+1];
			comp_e = comp[2*i+1][2*j+2];
			comp_w = comp[2*i+1][2*j+0];
			if (comp_n && comp_s) {
				comp_n -= 2;
				comp_s -= 2;
				adj[comp_n * num_components + comp_s] = 1;
				adj[comp_s * num_components + comp_n] = 1;
			}
			if (comp_e && comp_w) {
				comp_e -= 2;
				comp_w -= 2;
				adj[comp_e * num_components + comp_w] = 1;
				adj[comp_w * num_components + comp_e] = 1;
			}
		}
	}
	fprintf(stderr, "Found %lld components\n", num_components);
	sixcolour(adj, num_components, colouring);

	/* Output as ppm */
	printf("P6\n");
	printf("%d %d\n", IMG_WIDTH, IMG_HEIGHT);
	printf("255\n");

	for (i = 0; i < IMG_HEIGHT; ++i) {
		for (j = 0; j < IMG_WIDTH; ++j) {
			if (comp[i][j] > num_components + 1)
				fprintf(stderr, "OVERFLOW: %lld\n", comp[i][j]);
			if (colouring[comp[i][j]] >= COLNEW_WHITE) {
				fprintf(stderr, "WHITE?!?\n");
			}
			if (colouring[comp[i][j]] >= COLNEW__MAX) {
				fprintf(stderr, "COLOUR OVERFLOW: %lld\n", comp[i][j]);
				colouring[comp[i][j]] = COLNEW__MAX;
			}
			fwrite(colournew_map[comp[i][j] ? colouring[comp[i][j] - 2] : 0], 1, 3, stdout);
		}
	}
	fprintf(stderr, "DONE\n");
}