advent2023

puzzle.c (6414B)

---

 #define _DEFAULT_SOURCE
 
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <assert.h>
 #include <stdbool.h>
 #include <inttypes.h>
 
 #define STR_LEN 2048
 
 typedef enum Dir {
 	DIR_UP,
 	DIR_DOWN,
 	DIR_LEFT,
 	DIR_RIGHT
 } Dir;
 
 typedef struct Pos {
 	int x, y;
 	Dir dir;
 	struct Pos *next;
 } Pos;
 
 typedef struct Map {
 	int w, h;
 	char *area;
 	size_t size; // essentially width*height*sizeof(char)
 	Pos start;
 } Map;
 
 typedef struct Pair {
 	Pos one;
 	Pos two;
 } Pair;
 
 // standard issue linked list;
 typedef struct Visited {
 	Pos *first;
 	Pos *last;
 } Visited;
 
 void visited_add(Visited *visited, Pos p) {
 	Pos *add = malloc(sizeof(Pos));
 	memset(add, 0, sizeof(Pos));
 	*add = p;
 	if (visited->first==NULL) visited->first = add;
 	if (visited->last!=NULL) visited->last->next = add;
 	visited->last = add;
 }
 
 bool visited_has(Visited *visited, Pos p) {
 	Pos *cur = visited->first;
 	while (cur!=NULL) {
 		if (cur->x==p.x && cur->y==p.y && cur->dir==p.dir) {
 			return true;
 		}
 		cur = cur->next;
 	}
 	return false;
 }
 
 void visited_destroy(Visited *visited) {
 	Pos *cur = visited->first;
 	while (cur!=NULL) {
 		Pos *next = cur->next;
 		free(cur);
 		cur = next;
 	}
 	visited->first = NULL;
 	visited->last = NULL;
 }
 
 Pos get_next_empty(Pos cur) {
 	Pos p = cur;
 	switch (cur.dir) {
 	case DIR_RIGHT:
 		p.x++;
 	break;
 	case DIR_LEFT:
 		p.x--;
 	break;
 	case DIR_UP:
 		p.y--;
 	break;
 	case DIR_DOWN:
 		p.y++;
 	break;
 	}
 	return p;
 }
 
 Pos get_next_mirror(Pos cur, char sym) {
 	Pos p = {0};
 	if (sym == '\\') {
 		switch (cur.dir) {
 		case DIR_RIGHT:
 			p.dir = DIR_DOWN;
 			p.x = cur.x;
 			p.y = cur.y + 1;
 		break;
 		case DIR_LEFT:
 			p.dir = DIR_UP;
 			p.x = cur.x;
 			p.y = cur.y - 1;
 		break;
 		case DIR_UP:
 			p.dir = DIR_LEFT;
 			p.x = cur.x - 1;
 			p.y = cur.y;
 		break;
 		case DIR_DOWN:
 			p.dir = DIR_RIGHT;
 			p.x = cur.x + 1;
 			p.y = cur.y;
 		break;
 		}
 	} else if (sym == '/') {
 		switch (cur.dir) {
 		case DIR_RIGHT:
 			p.dir = DIR_UP;
 			p.x = cur.x;
 			p.y = cur.y - 1;
 		break;
 		case DIR_LEFT:
 			p.dir = DIR_DOWN;
 			p.x = cur.x;
 			p.y = cur.y + 1;
 		break;
 		case DIR_UP:
 			p.dir = DIR_RIGHT;
 			p.x = cur.x + 1;
 			p.y = cur.y;
 		break;
 		case DIR_DOWN:
 			p.dir = DIR_LEFT;
 			p.x = cur.x - 1;
 			p.y = cur.y;
 		break;
 		}
 	}
 	return p;
 }
 
 Pair get_next_splitter(Pos cur, char sym) {
 	Pair p = {.one={-1},.two={-1}};
 	if (sym=='-') {
 		switch (cur.dir) {
 		case DIR_RIGHT:
 			p.one = cur;
 			p.one.x++;
 		break;
 		case DIR_LEFT:
 			p.one = cur;
 			p.one.x--;
 		break;
 		case DIR_UP:
 		case DIR_DOWN:
 			p.one = cur;
 			p.one.x++;
 			p.one.dir = DIR_RIGHT;
 			p.two = cur;
 			p.two.x--;
 			p.two.dir = DIR_LEFT;
 		break;
 		}
 	} else if (sym=='|') {
 		switch (cur.dir) {
 		case DIR_RIGHT:
 		case DIR_LEFT:
 			p.one = cur;
 			p.one.y--;
 			p.one.dir = DIR_UP;
 			p.two = cur;
 			p.two.y++;
 			p.two.dir = DIR_DOWN;
 		break;
 		case DIR_UP:
 			p.one = cur;
 			p.one.y--;
 		break;
 		case DIR_DOWN:
 			p.one = cur;
 			p.one.y++;
 		break;
 		}
 	}
 	return p;
 }
 
 bool is_valid(Map *map, Visited *visited, Pos cur) {
 	return cur.x>=0 && cur.y>=0 && cur.x<map->w && cur.y<map->h && !visited_has(visited, cur);
 }
 
 Pair get_next(Map *map, Pos cur) {
 	char sym = map->area[map->w*cur.y+cur.x];
 	Pair p = {.one={-1},.two={-1}};
 	switch (sym) {
 	case '.':
 		p.one = get_next_empty(cur);
 		break;
 	case '/':
 	case '\\':
 		p.one = get_next_mirror(cur, sym);
 		break;
 	case '|':
 	case '-':
 		p = get_next_splitter(cur, sym);
 		break;
 	default:
 		printf("invalid symbol %c\n", sym);
 		exit(-1);
 	}
 	return p;
 }
 
 void traverse(Map *map, Map *energized, Visited *visited, Pos start) {
 	if (visited_has(visited, start)) {
 		return;
 	}
 	// mark entry as energized
 	energized->area[energized->w*start.y+start.x] = '#';
 	visited_add(visited, start);
 	while (1) {
 		Pair p = get_next(map, start);
 		bool valid1 = is_valid(map, visited, p.one);
 		bool valid2 = is_valid(map, visited, p.two);
 		if (valid1 && valid2) {
 			visited_add(visited, p.one);
 			energized->area[energized->w*p.one.y+p.one.x] = '#';
 			start = p.one;
 			//traverse(map, energized, visited, p.one);
 			traverse(map, energized, visited, p.two);
 		} else if (valid1) {
 			visited_add(visited, p.one);
 			energized->area[energized->w*p.one.y+p.one.x] = '#';
 			start = p.one;
 		} else if (valid2) {
 			visited_add(visited, p.two);
 			energized->area[energized->w*p.two.y+p.two.x] = '#';
 			start = p.two;
 		} else {
 			break;
 		}
 	}
 }
 
 long long count_energized(Map *map) {
 	long long result = 0;
 	Map energized = {0};
 	energized.size = map->size;
 	energized.w = map->w;
 	energized.h = map->h;
 	energized.area = malloc(energized.size);
 	memset(energized.area, '.', energized.size);
 
 	Visited visited = {0};
 	traverse(map, &energized, &visited, map->start);
 
 	for (int y=0; y<energized.h; ++y) {
 		for (int x=0; x<energized.w; ++x) {
 			if (energized.area[y*energized.w+x]=='#') {
 				result++;
 			}
 		}
 	}
 
 	free(energized.area);
 	visited_destroy(&visited);
 
 	return result;
 }
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
 	if (infile == NULL) {
 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
 		return;
 	}
 
 	char buf[STR_LEN] = {0};
 	unsigned int line_num = 0;
 	Map map = {0};
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
         int w = strlen(buf)-1;
         if (map.w==0) map.w=w;
         if (map.w!=w) printf("width mismatch!\n");
         map.size += map.w*sizeof(char);
         map.area = realloc(map.area, map.size);
         memcpy(map.area+map.w*line_num, buf, w);
 
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 	map.h = line_num;
 
 	map.start = (Pos){.x=0,.y=0,.dir=DIR_RIGHT};
 	*result1 = count_energized(&map);
 	*result2 = 0;
 
 	for (int x=0; x<map.w; ++x) {
 		// top row
 		map.start = (Pos){.x=x,.y=0,.dir=DIR_DOWN};
 		long long res = count_energized(&map);
 		if (res>*result2) *result2 = res;
 
 		// bottom row
 		map.start = (Pos){.x=x,.y=map.h-1,.dir=DIR_UP};
 		res = count_energized(&map);
 		if (res>*result2) *result2 = res;
 	}
 
 	for (int y=0; y<map.h; ++y) {
 		// leftmost column
 		map.start = (Pos){.x=0,.y=y,.dir=DIR_RIGHT};
 		long long res = count_energized(&map);
 		if (res>*result2) *result2 = res;
 
 		// rightmost column
 		map.start = (Pos){.x=map.w-1,.y=y,.dir=DIR_RIGHT};
 		res = count_energized(&map);
 		if (res>*result2) *result2 = res;
 	}
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }