advent2023

Advent of Code 2023 solutions
git clone git://bsandro.tech/advent2023
Log | Files | Refs | LICENSE

puzzle.c (7803B)

      1 #define _DEFAULT_SOURCE
      2 
      3 #include <limits.h>
      4 #include <stdio.h>
      5 #include <stdlib.h>
      6 #include <errno.h>
      7 #include <string.h>
      8 #include <strings.h>
      9 #include <assert.h>
     10 #include <stdbool.h>
     11 #include <inttypes.h>
     12 
     13 #define STR_LEN 2048
     14 
     15 typedef struct Stack {
     16 	char *data;
     17 	int len;
     18 } Stack;
     19 
     20 void stack_push(Stack *s, char c) {
     21 	assert(s!=NULL);
     22 	s->len += sizeof(char);
     23 	s->data = realloc(s->data, s->len);
     24 	s->data[s->len-1] = c;
     25 }
     26 
     27 char stack_pop(Stack *s) {
     28 	assert(s!=NULL);
     29 	if (s->len==0) return 0;
     30 	s->len--;
     31 	char r = s->data[s->len];
     32 	s->data = realloc(s->data, s->len);
     33 	return r;
     34 }
     35 
     36 char stack_last(Stack *s) {
     37 	assert(s!=NULL);
     38 	if (s->len==0) return 0;
     39 	return s->data[s->len-1];
     40 }
     41 
     42 void stack_free(Stack *s) {
     43 	assert(s!=NULL);
     44 	free(s->data);
     45 	s->len = 0;
     46 }
     47 
     48 typedef enum Dir {
     49 	DIR_INVALID,
     50 	DIR_NORTH,
     51 	DIR_SOUTH,
     52 	DIR_WEST,
     53 	DIR_EAST
     54 } Dir;
     55 
     56 typedef struct Pos {
     57 	int x, y;
     58 	Dir dir;
     59 } Pos;
     60 
     61 typedef struct Map {
     62 	int w, h;
     63 	char *area;
     64 	size_t size; // essentially width*height*sizeof(char)
     65 } Map;
     66 
     67 void map_print(Map *map) {
     68 	for (int y=0; y<map->h; ++y) {
     69 		for (int x=0; x<map->w; ++x) {
     70 			printf("%c", map->area[map->w*y+x]);
     71 		}
     72 		printf("\n");
     73 	}
     74 }
     75 
     76 bool is_valid(Map *map, Pos p) {
     77 	return p.dir!=DIR_INVALID && p.x>=0 && p.x<map->w && p.y>=0 && p.y<map->h;
     78 }
     79 
     80 Pos get_next(Map *map, Pos from) {
     81 	static Pos invalid = {.x=-1,.y=-1,.dir=DIR_INVALID};
     82 	if (!is_valid(map, from)) {
     83 		return invalid;
     84 	}
     85 	char sym = map->area[map->w*from.y+from.x];
     86 	Pos next = from;
     87 	switch (sym) {
     88 	case '|':
     89 		if (from.dir==DIR_NORTH) {
     90 			next.y--;
     91 		} else if (from.dir==DIR_SOUTH) {
     92 			next.y++;
     93 		} else {
     94 			return invalid;
     95 		}
     96 	break;
     97 	case 'J':
     98 		if (from.dir==DIR_SOUTH) {
     99 			next.x -= 1;
    100 			next.dir = DIR_WEST;
    101 		} else if (from.dir==DIR_EAST) {
    102 			next.y -= 1;
    103 			next.dir = DIR_NORTH;
    104 		} else {
    105 			return invalid;
    106 		}
    107 	break;
    108 	case 'L':
    109 		if (from.dir==DIR_SOUTH) {
    110 			next.x++;
    111 			next.dir = DIR_EAST;
    112 		} else if (from.dir==DIR_WEST) {
    113 			next.y--;
    114 			next.dir = DIR_NORTH;
    115 		} else {
    116 			return invalid;
    117 		}
    118 	break;
    119 	case '-':
    120 		if (from.dir==DIR_WEST) {
    121 			next.x--;
    122 		} else if (from.dir==DIR_EAST) {
    123 			next.x++;
    124 		} else {
    125 			return invalid;
    126 		}
    127 	break;
    128 	case '7':
    129 		if (from.dir==DIR_NORTH) {
    130 			next.x--;
    131 			next.dir = DIR_WEST;
    132 		} else if (from.dir==DIR_EAST) {
    133 			next.y++;
    134 			next.dir = DIR_SOUTH;
    135 		} else {
    136 			return invalid;
    137 		}
    138 	break;
    139 	case 'F':
    140 		if (from.dir==DIR_NORTH) {
    141 			next.x++;
    142 			next.dir = DIR_EAST;
    143 		} else if (from.dir==DIR_WEST) {
    144 			next.y++;
    145 			next.dir = DIR_SOUTH;
    146 		} else {
    147 			return invalid;
    148 		}
    149 	break;
    150 	case '.':
    151 		return invalid;
    152 	case 'S':
    153 		//printf("found start again\n");
    154 		return invalid;
    155 	default:
    156 		printf("invalid symbol %c at %d:%d\n", sym, from.x, from.y);
    157 		return invalid;
    158 	}
    159 
    160 	return next;
    161 }
    162 
    163 int traverse(Map *map, Pos start, Map *loop) {
    164 	int len = 1;
    165 	Pos p = start;
    166 	while (is_valid(map, p)) {
    167 		int offset = p.y*map->w+p.x;
    168 		loop->area[offset] = map->area[offset];
    169 		len++;
    170 		if (map->area[offset]=='S') {
    171 			// we need to transform S into real pipe type
    172 			loop->area[offset] = 'S';
    173 			return len;
    174 		}
    175 		p = get_next(map, p);
    176 	}
    177 	return -1;
    178 }
    179 
    180 /*
    181 | -> |,F,L
    182 L -> J
    183 F -> 7
    184 7 -> |,F,L
    185  */
    186 bool is_wall_toggles(char cur, char prev) {
    187 	if (cur=='-') return false;
    188 
    189 	if (cur=='J') return prev=='L';
    190 	if (cur=='L') return prev=='J';
    191 
    192 	if (cur=='7') return prev=='F';
    193 	if (cur=='F') return prev=='7';
    194 
    195 	return false;
    196 }
    197 
    198 /*
    199 F -> J
    200 L -> 7
    201  */
    202 bool is_wall_continues(char cur, char prev) {
    203 	if (cur=='J') return prev=='F';
    204 	if (cur=='7') return prev=='L';
    205 	return false;
    206 }
    207 
    208 // | L J F 7 S
    209 int calc_area(Map *loop) {
    210 	int area = 0;
    211 	for (int y=0; y<loop->h; ++y) {
    212 		Stack walls={.data=NULL,.len=0};
    213 		bool is_open = false;
    214 		for (int x=0; x<loop->w; ++x) {
    215 			char sym = loop->area[loop->w*y+x];
    216 			char prev = stack_last(&walls);
    217 
    218 			if (sym=='.') {
    219 			 	if (is_open) {
    220 					loop->area[loop->w*y+x] = 'I';
    221 					area++;
    222 				}
    223 				continue;
    224 			}
    225 
    226 			if (is_wall_continues(sym, prev)) {
    227 				stack_push(&walls, sym);
    228 			} else if (sym!='-') {
    229 				is_open = !is_open;
    230 				stack_push(&walls, sym);
    231 			}
    232 		}
    233 	}
    234 	return area;
    235 }
    236 
    237 char dir2sym(Dir dir) {
    238 	if (dir==DIR_NORTH) return 'n';
    239 	if (dir==DIR_SOUTH) return 's';
    240 	if (dir==DIR_WEST) return 'w';
    241 	if (dir==DIR_EAST) return 'e';
    242 
    243 	return 'z';
    244 }
    245 
    246 char dirs2sym(Dir dir1, Dir dir2) {
    247 	if (dir1==DIR_NORTH&&dir2==DIR_SOUTH) return '|';
    248 	if (dir2==DIR_NORTH&&dir1==DIR_SOUTH) return '|';
    249 
    250 	if (dir1==DIR_NORTH&&dir2==DIR_WEST) return 'F';
    251 	if (dir2==DIR_NORTH&&dir1==DIR_WEST) return 'F';
    252 
    253 	if (dir1==DIR_NORTH&&dir2==DIR_EAST) return '7';
    254 	if (dir2==DIR_NORTH&&dir1==DIR_EAST) return '7';
    255 
    256 	if (dir1==DIR_SOUTH&&dir2==DIR_WEST) return 'L';
    257 	if (dir2==DIR_SOUTH&&dir1==DIR_WEST) return 'L';
    258 
    259 	if (dir1==DIR_SOUTH&&dir2==DIR_EAST) return 'J';
    260 	if (dir2==DIR_SOUTH&&dir1==DIR_EAST) return 'J';
    261 
    262 	if (dir1==DIR_WEST&&dir2==DIR_EAST) return '-';
    263 	if (dir2==DIR_WEST&&dir1==DIR_EAST) return '-';
    264 
    265 	printf("invalid dirs %c and %c\n", dir2sym(dir1), dir2sym(dir2));
    266 	return 'E';
    267 }
    268 
    269 void save_dir(Dir *save1, Dir *save2, Dir dir) {
    270 	printf("save_dir() s1:%c s2:%c save:%c\n", dir2sym(*save1), dir2sym(*save2), dir2sym(dir));
    271 	Dir *save = ((*save1)==DIR_INVALID)?save1:save2;
    272 	*save = dir;
    273 }
    274 
    275 void puzzle(const char *filename, long long *result1, long long *result2) {
    276 	FILE *infile = fopen(filename, "r");
    277 	if (infile == NULL) {
    278 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
    279 		return;
    280 	}
    281 
    282 	char buf[STR_LEN] = {0};
    283 	unsigned int line_num = 0;
    284 
    285 	Map map = {0};
    286 	Pos start = {0};
    287 
    288 	while (fgets(buf, STR_LEN, infile) != NULL) {
    289 		// first line is always instructions
    290 		size_t len = strlen(buf);
    291 		int w = len-1;
    292 		if (map.w==0) map.w=w;
    293 		if (map.w!=w) printf("width mismatch!\n");
    294 
    295 		map.size += map.w * sizeof(char);
    296 		map.area = realloc(map.area, map.size);
    297 		for (int i=0; i<map.w; ++i) {
    298 			map.area[map.w*line_num+i] = buf[i];
    299 			if (buf[i]=='S') {
    300 				start.x = i;
    301 				start.y = line_num;
    302 			}
    303 		}
    304 
    305 		++line_num;
    306 		bzero(buf, STR_LEN);
    307 	}
    308 	map.h = line_num;
    309 
    310 	//printf("map %dx%d (%zu)\nstart: x:%d,y:%d\n", map.w, map.h, map.size, start.x, start.y);
    311 	Map loop = {0};
    312 	loop.w = map.w;
    313 	loop.h = map.h;
    314 	loop.size = map.size;
    315 	loop.area = malloc(loop.size);
    316 	memset(loop.area, '.', loop.size);
    317 
    318 	Dir start_dir1 = DIR_INVALID, start_dir2 = DIR_INVALID;
    319 	int valids = 0;
    320 	Pos init = start;
    321 
    322 	printf("traverse west...\n");
    323 	init.x--;
    324 	init.dir = DIR_WEST;
    325 	int r = traverse(&map, init, &loop);
    326 	if (r!=-1) {
    327 		*result1 = r/2;
    328 		save_dir(&start_dir1, &start_dir2, DIR_EAST);
    329 		valids++;
    330 		printf("-> west %d\n", valids);
    331 	}
    332 
    333 	if (valids<2) {
    334 		memset(loop.area, '.', loop.size);
    335 		printf("traverse east...\n");
    336 		init = start;
    337 		init.x++;
    338 		init.dir = DIR_EAST;
    339 		r = traverse(&map, init, &loop);
    340 		if (r!=-1) {
    341 			*result1 = r/2;
    342 			save_dir(&start_dir1, &start_dir2, DIR_WEST);
    343 			valids++;
    344 			printf("-> east %d\n", valids);
    345 		}
    346 	}
    347 
    348 	if (valids<2) {
    349 		memset(loop.area, '.', loop.size);
    350 		printf("traverse south...\n");
    351 		init = start;
    352 		init.y++;
    353 		init.dir = DIR_SOUTH;
    354 		r = traverse(&map, init, &loop);
    355 		if (r!=-1) {
    356 			*result1 = r/2;
    357 			save_dir(&start_dir1, &start_dir2, DIR_NORTH);
    358 			valids++;
    359 			printf("-> south %d\n", valids);
    360 		}
    361 	}
    362 
    363 	if (valids<2) {
    364 		memset(loop.area, '.', loop.size);
    365 		printf("traverse north...\n");
    366 		init = start;
    367 		init.y--;
    368 		init.dir = DIR_NORTH;
    369 		r = traverse(&map, init, &loop);
    370 		if (r!=-1) {
    371 			*result1 = r/2;
    372 			save_dir(&start_dir1, &start_dir2, DIR_SOUTH);
    373 			valids++;
    374 			printf("-> north %d\n", valids);
    375 		}
    376 	}
    377 
    378 	printf("(%d) start_dir1: %c, start_dir2: %c, sym: %c\n", valids, dir2sym(start_dir1), dir2sym(start_dir2), dirs2sym(start_dir1, start_dir2));
    379 
    380 	loop.area[loop.w*start.y+start.x] = dirs2sym(start_dir1, start_dir2);
    381 
    382 	*result2 = calc_area(&loop);
    383 	map_print(&loop);
    384 
    385 	// mutiny! ignoring feof/ferror.
    386 	fclose(infile);
    387 }