148 lines
4.1 KiB
C
148 lines
4.1 KiB
C
#include <assert.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
#include <inttypes.h>
|
|
#include <stdio.h>
|
|
#include <math.h>
|
|
|
|
#include "common.c"
|
|
|
|
/// This is a merge of the `fifo` implementation and the `quarter`
|
|
/// one.
|
|
|
|
|
|
typedef struct terrain {
|
|
int width;
|
|
int **cells;
|
|
} terrain;
|
|
|
|
|
|
void propagate_to_quartiles(terrain *quartile, terrain *full)
|
|
{
|
|
for (int x = 0; x <= full->width / 2; x++)
|
|
for (int y = 0; y <= full->width / 2; y++) {
|
|
full->cells[x][y] = quartile->cells[x][y];
|
|
full->cells[full->width-x-1][y] = quartile->cells[x][y];
|
|
full->cells[x][full->width-y-1] = quartile->cells[x][y];
|
|
full->cells[full->width-x-1][full->width-y-1] = quartile->cells[x][y];
|
|
}
|
|
}
|
|
|
|
typedef struct point {
|
|
int x;
|
|
int y;
|
|
} point_t;
|
|
|
|
|
|
typedef struct todo {
|
|
int width;
|
|
int height;
|
|
int size;
|
|
int idx;
|
|
int qty;
|
|
point_t *points;
|
|
bool *dedup; // Used to avoid adding twice the same point, stored as x*width+y
|
|
} todo_t;
|
|
|
|
|
|
// The todo is deduplicated list of points.
|
|
todo_t *todo_new(size_t width, size_t height)
|
|
{
|
|
todo_t *todo = malloc(sizeof(*todo));
|
|
|
|
todo->qty = 0;
|
|
todo->width = width;
|
|
todo->height = height;
|
|
todo->size = width * 4;
|
|
todo->dedup = calloc(todo->width * todo->height, sizeof(bool));
|
|
todo->points = malloc(todo->size * sizeof(point_t));
|
|
return todo;
|
|
}
|
|
|
|
static void todo_write(todo_t *todo, point_t point)
|
|
{
|
|
if (todo->dedup[point.x * todo->width + point.y])
|
|
return;
|
|
if (todo->qty == todo->size - 1) {
|
|
todo->points = realloc(todo->points, sizeof(point_t) * todo->size * 2);
|
|
todo->size *= 4;
|
|
}
|
|
todo->dedup[point.x * todo->width + point.y] = true;
|
|
todo->points[todo->qty] = point;
|
|
todo->qty += 1;
|
|
}
|
|
|
|
static point_t todo_read(todo_t *todo)
|
|
{
|
|
assert(todo->qty > 0);
|
|
todo->qty -= 1;
|
|
todo->dedup[todo->points[todo->qty].x * todo->width + todo->points[todo->qty].y] = false;
|
|
return todo->points[todo->qty];
|
|
}
|
|
|
|
|
|
void apply_gravity(terrain *land, int middle_column, todo_t *todo)
|
|
{
|
|
int div;
|
|
point_t point;
|
|
|
|
while (todo->qty) {
|
|
point = todo_read(todo);
|
|
div = land->cells[point.x][point.y] / 4;
|
|
land->cells[point.x][point.y] = land->cells[point.x][point.y] % 4;
|
|
land->cells[point.x - 1][point.y] += div;
|
|
if (point.x < middle_column)
|
|
land->cells[point.x + 1][point.y] += div;
|
|
if (point.y < middle_column)
|
|
land->cells[point.x][point.y + 1] += div;
|
|
land->cells[point.x][point.y - 1] += div;
|
|
if (point.x == middle_column - 1)
|
|
land->cells[point.x + 1][point.y] += div;
|
|
if (point.y == middle_column - 1)
|
|
land->cells[point.x][point.y + 1] += div;
|
|
if (land->cells[point.x - 1][point.y] > 3)
|
|
todo_write(todo, (point_t){point.x-1, point.y});
|
|
if (point.x < middle_column && land->cells[point.x + 1][point.y] > 3)
|
|
todo_write(todo, (point_t){point.x+1, point.y});
|
|
if (point.y < middle_column && land->cells[point.x][point.y + 1] > 3)
|
|
todo_write(todo, (point_t){point.x, point.y+1});
|
|
if (land->cells[point.x][point.y - 1] > 3)
|
|
todo_write(todo, (point_t){point.x-1, point.y-1});
|
|
}
|
|
}
|
|
|
|
terrain *terrain_new(int width)
|
|
{
|
|
terrain *land = malloc(sizeof(terrain));
|
|
int **lines = calloc(width, sizeof(int*));
|
|
int *cells = calloc(width * width, sizeof(int));
|
|
for (int i = 0; i < width; i++) {
|
|
lines[i] = cells + i * width;
|
|
}
|
|
land->width = width;
|
|
land->cells = lines;
|
|
return land;
|
|
}
|
|
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
args args = {0};
|
|
|
|
if (parse_args(argc, argv, &args))
|
|
return EXIT_FAILURE;
|
|
|
|
int width = sandpile_width(args.height);
|
|
|
|
terrain *land = terrain_new(width);
|
|
terrain *small_land = terrain_new(width / 2 + 1);
|
|
small_land->cells[width / 2][width / 2] = args.height;
|
|
todo_t *todo = todo_new(width, args.height);
|
|
todo_write(todo, (point_t){width/2, width/2});
|
|
apply_gravity(small_land, width/2, todo);
|
|
propagate_to_quartiles(small_land, land);
|
|
save_terrain(land->width, land->cells, &args);
|
|
return EXIT_SUCCESS;
|
|
}
|