advent2023

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

puzzle.c (6414B)


      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 enum Dir {
     16 	DIR_UP,
     17 	DIR_DOWN,
     18 	DIR_LEFT,
     19 	DIR_RIGHT
     20 } Dir;
     21 
     22 typedef struct Pos {
     23 	int x, y;
     24 	Dir dir;
     25 	struct Pos *next;
     26 } Pos;
     27 
     28 typedef struct Map {
     29 	int w, h;
     30 	char *area;
     31 	size_t size; // essentially width*height*sizeof(char)
     32 	Pos start;
     33 } Map;
     34 
     35 typedef struct Pair {
     36 	Pos one;
     37 	Pos two;
     38 } Pair;
     39 
     40 // standard issue linked list;
     41 typedef struct Visited {
     42 	Pos *first;
     43 	Pos *last;
     44 } Visited;
     45 
     46 void visited_add(Visited *visited, Pos p) {
     47 	Pos *add = malloc(sizeof(Pos));
     48 	memset(add, 0, sizeof(Pos));
     49 	*add = p;
     50 	if (visited->first==NULL) visited->first = add;
     51 	if (visited->last!=NULL) visited->last->next = add;
     52 	visited->last = add;
     53 }
     54 
     55 bool visited_has(Visited *visited, Pos p) {
     56 	Pos *cur = visited->first;
     57 	while (cur!=NULL) {
     58 		if (cur->x==p.x && cur->y==p.y && cur->dir==p.dir) {
     59 			return true;
     60 		}
     61 		cur = cur->next;
     62 	}
     63 	return false;
     64 }
     65 
     66 void visited_destroy(Visited *visited) {
     67 	Pos *cur = visited->first;
     68 	while (cur!=NULL) {
     69 		Pos *next = cur->next;
     70 		free(cur);
     71 		cur = next;
     72 	}
     73 	visited->first = NULL;
     74 	visited->last = NULL;
     75 }
     76 
     77 Pos get_next_empty(Pos cur) {
     78 	Pos p = cur;
     79 	switch (cur.dir) {
     80 	case DIR_RIGHT:
     81 		p.x++;
     82 	break;
     83 	case DIR_LEFT:
     84 		p.x--;
     85 	break;
     86 	case DIR_UP:
     87 		p.y--;
     88 	break;
     89 	case DIR_DOWN:
     90 		p.y++;
     91 	break;
     92 	}
     93 	return p;
     94 }
     95 
     96 Pos get_next_mirror(Pos cur, char sym) {
     97 	Pos p = {0};
     98 	if (sym == '\\') {
     99 		switch (cur.dir) {
    100 		case DIR_RIGHT:
    101 			p.dir = DIR_DOWN;
    102 			p.x = cur.x;
    103 			p.y = cur.y + 1;
    104 		break;
    105 		case DIR_LEFT:
    106 			p.dir = DIR_UP;
    107 			p.x = cur.x;
    108 			p.y = cur.y - 1;
    109 		break;
    110 		case DIR_UP:
    111 			p.dir = DIR_LEFT;
    112 			p.x = cur.x - 1;
    113 			p.y = cur.y;
    114 		break;
    115 		case DIR_DOWN:
    116 			p.dir = DIR_RIGHT;
    117 			p.x = cur.x + 1;
    118 			p.y = cur.y;
    119 		break;
    120 		}
    121 	} else if (sym == '/') {
    122 		switch (cur.dir) {
    123 		case DIR_RIGHT:
    124 			p.dir = DIR_UP;
    125 			p.x = cur.x;
    126 			p.y = cur.y - 1;
    127 		break;
    128 		case DIR_LEFT:
    129 			p.dir = DIR_DOWN;
    130 			p.x = cur.x;
    131 			p.y = cur.y + 1;
    132 		break;
    133 		case DIR_UP:
    134 			p.dir = DIR_RIGHT;
    135 			p.x = cur.x + 1;
    136 			p.y = cur.y;
    137 		break;
    138 		case DIR_DOWN:
    139 			p.dir = DIR_LEFT;
    140 			p.x = cur.x - 1;
    141 			p.y = cur.y;
    142 		break;
    143 		}
    144 	}
    145 	return p;
    146 }
    147 
    148 Pair get_next_splitter(Pos cur, char sym) {
    149 	Pair p = {.one={-1},.two={-1}};
    150 	if (sym=='-') {
    151 		switch (cur.dir) {
    152 		case DIR_RIGHT:
    153 			p.one = cur;
    154 			p.one.x++;
    155 		break;
    156 		case DIR_LEFT:
    157 			p.one = cur;
    158 			p.one.x--;
    159 		break;
    160 		case DIR_UP:
    161 		case DIR_DOWN:
    162 			p.one = cur;
    163 			p.one.x++;
    164 			p.one.dir = DIR_RIGHT;
    165 			p.two = cur;
    166 			p.two.x--;
    167 			p.two.dir = DIR_LEFT;
    168 		break;
    169 		}
    170 	} else if (sym=='|') {
    171 		switch (cur.dir) {
    172 		case DIR_RIGHT:
    173 		case DIR_LEFT:
    174 			p.one = cur;
    175 			p.one.y--;
    176 			p.one.dir = DIR_UP;
    177 			p.two = cur;
    178 			p.two.y++;
    179 			p.two.dir = DIR_DOWN;
    180 		break;
    181 		case DIR_UP:
    182 			p.one = cur;
    183 			p.one.y--;
    184 		break;
    185 		case DIR_DOWN:
    186 			p.one = cur;
    187 			p.one.y++;
    188 		break;
    189 		}
    190 	}
    191 	return p;
    192 }
    193 
    194 bool is_valid(Map *map, Visited *visited, Pos cur) {
    195 	return cur.x>=0 && cur.y>=0 && cur.x<map->w && cur.y<map->h && !visited_has(visited, cur);
    196 }
    197 
    198 Pair get_next(Map *map, Pos cur) {
    199 	char sym = map->area[map->w*cur.y+cur.x];
    200 	Pair p = {.one={-1},.two={-1}};
    201 	switch (sym) {
    202 	case '.':
    203 		p.one = get_next_empty(cur);
    204 		break;
    205 	case '/':
    206 	case '\\':
    207 		p.one = get_next_mirror(cur, sym);
    208 		break;
    209 	case '|':
    210 	case '-':
    211 		p = get_next_splitter(cur, sym);
    212 		break;
    213 	default:
    214 		printf("invalid symbol %c\n", sym);
    215 		exit(-1);
    216 	}
    217 	return p;
    218 }
    219 
    220 void traverse(Map *map, Map *energized, Visited *visited, Pos start) {
    221 	if (visited_has(visited, start)) {
    222 		return;
    223 	}
    224 	// mark entry as energized
    225 	energized->area[energized->w*start.y+start.x] = '#';
    226 	visited_add(visited, start);
    227 	while (1) {
    228 		Pair p = get_next(map, start);
    229 		bool valid1 = is_valid(map, visited, p.one);
    230 		bool valid2 = is_valid(map, visited, p.two);
    231 		if (valid1 && valid2) {
    232 			visited_add(visited, p.one);
    233 			energized->area[energized->w*p.one.y+p.one.x] = '#';
    234 			start = p.one;
    235 			//traverse(map, energized, visited, p.one);
    236 			traverse(map, energized, visited, p.two);
    237 		} else if (valid1) {
    238 			visited_add(visited, p.one);
    239 			energized->area[energized->w*p.one.y+p.one.x] = '#';
    240 			start = p.one;
    241 		} else if (valid2) {
    242 			visited_add(visited, p.two);
    243 			energized->area[energized->w*p.two.y+p.two.x] = '#';
    244 			start = p.two;
    245 		} else {
    246 			break;
    247 		}
    248 	}
    249 }
    250 
    251 long long count_energized(Map *map) {
    252 	long long result = 0;
    253 	Map energized = {0};
    254 	energized.size = map->size;
    255 	energized.w = map->w;
    256 	energized.h = map->h;
    257 	energized.area = malloc(energized.size);
    258 	memset(energized.area, '.', energized.size);
    259 
    260 	Visited visited = {0};
    261 	traverse(map, &energized, &visited, map->start);
    262 
    263 	for (int y=0; y<energized.h; ++y) {
    264 		for (int x=0; x<energized.w; ++x) {
    265 			if (energized.area[y*energized.w+x]=='#') {
    266 				result++;
    267 			}
    268 		}
    269 	}
    270 
    271 	free(energized.area);
    272 	visited_destroy(&visited);
    273 
    274 	return result;
    275 }
    276 
    277 void puzzle(const char *filename, long long *result1, long long *result2) {
    278 	FILE *infile = fopen(filename, "r");
    279 	if (infile == NULL) {
    280 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
    281 		return;
    282 	}
    283 
    284 	char buf[STR_LEN] = {0};
    285 	unsigned int line_num = 0;
    286 	Map map = {0};
    287 
    288 	while (fgets(buf, STR_LEN, infile) != NULL) {
    289         int w = strlen(buf)-1;
    290         if (map.w==0) map.w=w;
    291         if (map.w!=w) printf("width mismatch!\n");
    292         map.size += map.w*sizeof(char);
    293         map.area = realloc(map.area, map.size);
    294         memcpy(map.area+map.w*line_num, buf, w);
    295 
    296 		++line_num;
    297 		bzero(buf, STR_LEN);
    298 	}
    299 	map.h = line_num;
    300 
    301 	map.start = (Pos){.x=0,.y=0,.dir=DIR_RIGHT};
    302 	*result1 = count_energized(&map);
    303 	*result2 = 0;
    304 
    305 	for (int x=0; x<map.w; ++x) {
    306 		// top row
    307 		map.start = (Pos){.x=x,.y=0,.dir=DIR_DOWN};
    308 		long long res = count_energized(&map);
    309 		if (res>*result2) *result2 = res;
    310 
    311 		// bottom row
    312 		map.start = (Pos){.x=x,.y=map.h-1,.dir=DIR_UP};
    313 		res = count_energized(&map);
    314 		if (res>*result2) *result2 = res;
    315 	}
    316 
    317 	for (int y=0; y<map.h; ++y) {
    318 		// leftmost column
    319 		map.start = (Pos){.x=0,.y=y,.dir=DIR_RIGHT};
    320 		long long res = count_energized(&map);
    321 		if (res>*result2) *result2 = res;
    322 
    323 		// rightmost column
    324 		map.start = (Pos){.x=map.w-1,.y=y,.dir=DIR_RIGHT};
    325 		res = count_energized(&map);
    326 		if (res>*result2) *result2 = res;
    327 	}
    328 
    329 	// mutiny! ignoring feof/ferror.
    330 	fclose(infile);
    331 }