commit 7cb3f5e9385a2e2a359c9b0216d405211b46afe9
parent 8c79cf09b68ad7bc23efb3b93abf60e36fa0d28e
Author: bsandro <email@bsandro.tech>
Date: Tue, 12 Dec 2023 00:04:16 +0200
day 11 p2
Diffstat:
| M | day11/puzzle.c | | | 225 | +++++++++++++++++++++++++------------------------------------------------------ |
1 file changed, 71 insertions(+), 154 deletions(-)
diff --git a/day11/puzzle.c b/day11/puzzle.c
@@ -14,47 +14,11 @@
#define STR_LEN 2048
-// either row or column
-typedef struct Line {
- char *tiles;
- size_t tiles_size;
- struct Line *next;
-} Line;
-
-Line * make_line() {
- Line *l = malloc(sizeof(Line));
- memset(l, 0, sizeof(Line));
- return l;
-}
-void print_lines(Line *first) {
- Line *l = first;
- while (l!=NULL) {
- for (size_t i=0; i<l->tiles_size; ++i) {
- printf("%c", l->tiles[i]);
- }
- printf("(%zu)\n", l->tiles_size);
- l = l->next;
- }
-}
-void free_lines(Line *first) {
- Line *l = first;
- while (l!=NULL) {
- Line *l1 = l->next;
- free(l);
- l = l1;
- }
-}
-bool is_line_empty(Line *line) {
- for (size_t i=0; i<line->tiles_size; ++i) {
- if (line->tiles[i]!='.') return false;
- }
- return true;
-}
-
typedef struct Vec2 {
int x, y;
struct Vec2 *next;
} Vec2;
+
Vec2 * make_vec2(int x, int y) {
Vec2 *v = malloc(sizeof(Vec2));
v->x = x;
@@ -62,16 +26,54 @@ Vec2 * make_vec2(int x, int y) {
v->next = NULL;
return v;
}
-void print_vec2(Vec2 *v) {
- Vec2 *v1 = v;
+
+typedef struct List {
+ Vec2 *first;
+ Vec2 *last;
+} List;
+void list_add(List *l, int x, int y) {
+ Vec2 *v = make_vec2(x, y);
+ if (l->first==NULL) l->first = v;
+ if (l->last!=NULL) l->last->next = v;
+ l->last = v;
+}
+bool list_has(List *l, int x, int y) {
+ Vec2 *v1 = l->first;
+ while (v1!=NULL) {
+ if (v1->x==x && v1->y==y) {
+ return true;
+ }
+ v1 = v1->next;
+ }
+ return false;
+}
+void list_print(List *l) {
+ Vec2 *v1 = l->first;
while (v1!=NULL) {
printf("x:%2d,y:%2d (%p)\n",v1->x, v1->y, v1);
v1 = v1->next;
}
}
-int calc_dist(Vec2 *v1, Vec2 *v2) {
- int dx = MAX(v1->x, v2->x) - MIN(v1->x, v2->x);
- int dy = MAX(v1->y, v2->y) - MIN(v1->y, v2->y);
+
+int calc_dist(Vec2 *v1, Vec2 *v2, List *emptiness, int incr) {
+ int min_x = MIN(v1->x, v2->x);
+ int max_x = MAX(v1->x, v2->x);
+ int min_y = MIN(v1->y, v2->y);
+ int max_y = MAX(v1->y, v2->y);
+ int dx = max_x - min_x;
+ int dy = max_y - min_y;
+ for (int x=min_x; x<max_x; ++x) {
+ if (list_has(emptiness, x, -1)) {
+ dx+=incr-1;
+ }
+ }
+
+ for (int y=min_y; y<max_y; ++y) {
+ if (list_has(emptiness, -1, y)) {
+ dy+=incr-1;
+ }
+ }
+
return dx+dy;
}
@@ -86,33 +88,18 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
unsigned int line_num = 0;
int cols = 0;
int rows = 0;
- Line *rows_list = NULL;
- Line *rows_last = NULL;
+ char *map = NULL;
+ size_t map_size = 0;
while (fgets(buf, STR_LEN, infile) != NULL) {
int len = strlen(buf)-1; // ignore \n
if (cols==0) cols = len;
if (cols!=len) printf("width mismatch\n");
- // filling and expanding rows
- Line *row = make_line();
- row->tiles = malloc(len*sizeof(char));
- row->tiles_size = len;
- memcpy(row->tiles, buf, len*sizeof(char));
- if (rows_list==NULL) rows_list=row;
- if (rows_last!=NULL) rows_last->next = row;
- rows_last = row;
-
- // dupe if needed (also meh copypasta)
- if (is_line_empty(row)) {
- Line *row = make_line();
- row->tiles = malloc(len*sizeof(char));
- row->tiles_size = len;
- memcpy(row->tiles, buf, len*sizeof(char));
- if (rows_list==NULL) rows_list=row;
- if (rows_last!=NULL) rows_last->next = row;
- rows_last = row;
- ++line_num;
+ map_size += cols*(line_num+1)*sizeof(char);
+ map = realloc(map, map_size);
+ for (int x=0; x<cols; ++x) {
+ map[line_num*cols+x] = buf[x];
}
++line_num;
@@ -120,111 +107,42 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
}
rows = line_num;
- //printf("field: %dx%d\n", rows, cols);
- //print_lines(rows_list);
-
- // make some 2d area
- size_t map_size = rows*cols*sizeof(char);
- //printf("map_size: %zu\n", map_size);
- char *map = malloc(map_size);
- memset(map, 0, map_size);
- Line *l = rows_list;
- int cur_row = 0;
- while (l!=NULL) {
- for (size_t i=0; i<l->tiles_size; ++i) {
- map[cur_row*l->tiles_size+i] = l->tiles[i];
- }
- l = l->next;
- ++cur_row;
- }
+ List galaxies = {0};
+ List emptiness = {0};
- // fill cols_list and expand
- Line *cols_list = NULL;
- Line *cols_last = NULL;
- int cols_new = 0;
- for (int x=0; x<cols; ++x) {
- Line *col = make_line();
- col->tiles = malloc(rows*sizeof(char));
- col->tiles_size = rows;
- for (int y=0; y<rows; ++y) {
- if (y*cols+x>=(int)map_size) {
- printf("x:%d,y:%d,offset:%d invalid\n", x, y, y*cols+x);
+ for (int y=0;y<rows;++y) {
+ bool y_empty = true;
+ for (int x=0;x<cols;++x) {
+ if (map[y*cols+x]=='#') {
+ list_add(&galaxies, x, y);
+ y_empty = false;
}
- col->tiles[y] = map[y*cols+x];
}
- if (cols_list==NULL) cols_list = col;
- if (cols_last!=NULL) cols_last->next = col;
- cols_last = col;
- ++cols_new;
-
- // dupe if needed (also meh copypasta)
- if (is_line_empty(col)) {
- Line *col1 = make_line();
- col1->tiles = malloc(rows*sizeof(char));
- col1->tiles_size = rows;
- memcpy(col1->tiles, col->tiles, rows*sizeof(char));
- if (cols_list==NULL) cols_list=col1;
- if (cols_last!=NULL) cols_last->next = col1;
- cols_last = col1;
- ++cols_new;
+ if (y_empty) {
+ list_add(&emptiness, -1, y);
}
}
- cols = cols_new;
- //printf("field: %dx%d\n", rows, cols);
-
- map_size = rows*cols*sizeof(char);
- map = realloc(map, map_size);
- memset(map, 0, map_size);
-
- //printf("------\n");
- //print_lines(cols_list);
-
- l = cols_list;
- int cur_col = 0;
- while (l!=NULL) {
- for (size_t y=0; y<l->tiles_size; ++y) {
- assert(y*cols+cur_col<map_size);
- map[y*cols+cur_col] = l->tiles[y];
- }
- l = l->next;
- ++cur_col;
- }
-
- Vec2 *galaxies = NULL;
- Vec2 *galaxies_last = NULL;
-
- // print map
- // collect galaxies
- //printf("map:\n");
- for (int y=0;y<rows;++y) {
- for (int x=0;x<cols;++x) {
- //printf("%c", map[y*cols+x]);
+ for (int x=0; x<cols; ++x) {
+ bool x_empty = true;
+ for (int y=0; y<rows; ++y) {
if (map[y*cols+x]=='#') {
- Vec2 *g = make_vec2(x, y);
- if (galaxies==NULL) galaxies = g;
- if (galaxies_last!=NULL) galaxies_last->next = g;
- galaxies_last = g;
+ x_empty = false;
}
}
- //printf("\n");
+ if (x_empty) {
+ list_add(&emptiness, x, -1);
+ }
}
- // clean stuff
- free_lines(rows_list);
- free_lines(cols_list);
- rows_list = NULL;
- rows_last = NULL;
- cols_list = NULL;
- cols_last = NULL;
-
- //print_vec2(galaxies);
*result1 = 0;
- Vec2 *g1 = galaxies;
+ *result2 = 0;
+ Vec2 *g1 = galaxies.first;
while (g1!=NULL) {
Vec2 *g2 = g1;
while (g2!=NULL) {
if (g1!=g2) {
- *result1 += calc_dist(g1, g2);
+ *result1 += calc_dist(g1, g2, &emptiness, 1);
+ *result2 += calc_dist(g1, g2, &emptiness, 1000000);
}
g2 = g2->next;
}
@@ -234,6 +152,5 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
// mutiny! ignoring feof/ferror.
fclose(infile);
- (void)result1;
(void)result2;
}
