sandpile_ladder.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char tile_t;

typedef struct {
	// size is the number of tiles between the center of the pile and any of its edges
	// so, size 0 has one tile, size 1 has 1+8 = 9 tiles, size 2 has 1+8+16=25 tiles, etc.
	int size;
	tile_t *tiles;
} pile_t;

typedef struct {
	signed int x;
	signed int y;
} coord_t;

int pile_dimension(int pile_size) {
	return pile_size * 2 + 1;
}

int pile_array_size(int pile_size) {
	int d = pile_dimension(pile_size);
	return d * d;
}

int pile_array_index(int pile_size, coord_t coord) {
	int d = pile_dimension(pile_size);
	return (coord.y + pile_size) * d + coord.x + pile_size;
}

pile_t make_pile(int size) {
	tile_t *tiles = calloc(pile_array_size(size), sizeof(tile_t));
	pile_t rv = { size, tiles };
	return rv;
}

pile_t copy_pile(pile_t source) {
	int size = source.size;
	int array_size = pile_array_size(source.size);
	tile_t *tiles = malloc(array_size * sizeof(tile_t));
	memcpy(tiles, source.tiles, array_size * sizeof(tile_t));
	pile_t rv = { size, tiles };

	return rv;
}

void increment_pile_size(pile_t *pile, int difference) {
	if (difference <= 0) {
		return;
	}

	int new_size = pile->size + difference;
	tile_t *new_tiles = calloc(pile_array_size(new_size), sizeof(tile_t));

	int old_dimension = pile_dimension(pile->size);
	int new_dimension = pile_dimension(new_size);
	for (int y = 0; y < old_dimension; y++) {
		// the bug(s): Should be multiplying with new_dimension and
		// old_dimension, not new_size and pile->size
		memcpy(&new_tiles[(y + difference) * new_size + difference],
		       &pile->tiles[y * pile->size],
		       old_dimension * sizeof(tile_t));
	}

	free(pile->tiles);
	pile->tiles = new_tiles;
	pile->size = new_size;
}

void drop_v(pile_t *pile, coord_t coord, tile_t v) {
	increment_pile_size(pile, abs(coord.x) - pile->size + 1);
	increment_pile_size(pile, abs(coord.y) - pile->size + 1);

	tile_t *tiles = pile->tiles;
	int size = pile->size;

	int i = pile_array_index(size, coord);
	tile_t r = tiles[i] + v;
	tiles[i] = r;
	if (r < 4) {
		tiles[i] = r;
	} else {
		tiles[i] = r - 4;
		drop_v(pile, (coord_t) { .x = coord.x - 1, .y = coord.y }, 1);
		drop_v(pile, (coord_t) { .x = coord.x + 1, .y = coord.y }, 1);
		drop_v(pile, (coord_t) { .x = coord.x, .y = coord.y - 1 }, 1);
		drop_v(pile, (coord_t) { .x = coord.x, .y = coord.y + 1 }, 1);
	}
}

void drop_onto(pile_t *dest, pile_t source) {
	for (signed int x = -source.size; x <= source.size; x++) {
		for (signed int y = -source.size; y <= source.size; y++) {
			coord_t coord = { x, y };

			drop_v(dest,
			       coord,
			       source.tiles[pile_array_index(source.size, coord)]);
		}
	}
}


void draw(pile_t pile) {
	FILE *out = fopen("out.ppm", "w");
	int d = pile_dimension(pile.size);
	fprintf(out, "P6 %d %d\n255\n", d, d);
	for (int y = -pile.size; y <= pile.size; y++) {
		for (int x = -pile.size; x <= pile.size; x++) {
			unsigned char r;
			unsigned char g;
			unsigned char b;
			tile_t v = pile.tiles[pile_array_index(pile.size, (coord_t) { x, y })];

			switch(v) {
			case 0: r = 0; g = 0; b = 0; break;
			case 1: r = 0; g = 0; b = 255; break;
			case 2: r = 0; g = 255; b = 0; break;
			case 3: r = 255; g = 0; b = 0; break;
			default: r = 255; g = 255; b = 255; break;
			}
			fputc_unlocked(r, out);
			fputc_unlocked(g, out);
			fputc_unlocked(b, out);
		}
	}
	fclose(out);
}

int main(int argc, char** argv) {
	if (argc != 2) {
		fprintf(stderr, "%s scale\n", argv[0]);
		return 0;
	}

	int ladder_length = atoi(argv[1]);
	if (ladder_length == 0) {
		return 0;
	}

	pile_t pile = make_pile(1);
	drop_v(&pile, (coord_t) {0, 0}, 1);

	for (int i = 1; i < ladder_length; i++) {
		pile_t copy = copy_pile(pile);
		printf("%d %d\n", i, pile.size);
		drop_onto(&pile, copy);
		free(copy.tiles);
	}

	draw(pile);
	free(pile.tiles);
}