114 lines
2.9 KiB
C
114 lines
2.9 KiB
C
/// This is my fastest implemtation, it relies on the 8-fold symetry
|
|
/// of flattening a centered pile. I in fact only rely on a 4-fold
|
|
/// symmetry for simplicity, so it could be enchanced again.
|
|
|
|
/*
|
|
|
|
Some performance measures:
|
|
|
|
+--------+---------+
|
|
| height | time |
|
|
+--------+---------+
|
|
| 2**16 | 0.1s |
|
|
| 2**17 | 0.4s |
|
|
| 2**18 | 1.5s |
|
|
| 2**19 | 6.5s |
|
|
| 2**20 | 19s |
|
|
| 2**21 | 1m14s |
|
|
| 2**22 | 5 min |
|
|
| 2**23 | 20 min |
|
|
| 2**24 | 74 min |
|
|
| 2**25 | 5h |
|
|
| 2**26 | 22h |
|
|
+--------+---------+
|
|
|
|
*/
|
|
|
|
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
#include <inttypes.h>
|
|
#include <stdio.h>
|
|
#include <math.h>
|
|
|
|
#include "common.c"
|
|
|
|
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];
|
|
}
|
|
}
|
|
|
|
void apply_gravity(terrain *land)
|
|
{
|
|
bool did_something;
|
|
int div;
|
|
|
|
while (1) {
|
|
did_something = false;
|
|
for (int x = 0; x <= land->width - 2; x++) {
|
|
for (int y = 0; y <= land->width - 2; y++) {
|
|
if (land->cells[x][y] >= 4) {
|
|
did_something = true;
|
|
div = land->cells[x][y] / 4;
|
|
land->cells[x][y] = land->cells[x][y] % 4;
|
|
land->cells[x - 1][y] += div;
|
|
land->cells[x + 1][y] += div;
|
|
land->cells[x][y + 1] += div;
|
|
land->cells[x][y - 1] += div;
|
|
if (x == land->width - 3)
|
|
land->cells[x + 1][y] += div;
|
|
if (y == land->width - 3)
|
|
land->cells[x][y + 1] += div;
|
|
}
|
|
}
|
|
}
|
|
if (!did_something)
|
|
return;
|
|
}
|
|
}
|
|
|
|
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 + 2);
|
|
small_land->cells[width / 2][width / 2] = args.height;
|
|
apply_gravity(small_land);
|
|
propagate_to_quartiles(small_land, land);
|
|
save_terrain(land->width, land->cells, &args);
|
|
return EXIT_SUCCESS;
|
|
}
|