advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs | README | LICENSE

puzzle.c (4955B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <errno.h>
      6 #include <string.h>
      7 #include <strings.h>
      8 #include <stdbool.h>
      9 #include <assert.h>
     10 #include <time.h>
     11 
     12 #include "util.h"
     13 
     14 #define STR_LEN 16384
     15 #define MAP_SIZE 1000
     16 
     17 // being tad lazy here - assume that the map sides are no larger than MAP_SIZE
     18 static short map1[MAP_SIZE][MAP_SIZE];
     19 static short map2[MAP_SIZE][MAP_SIZE];
     20 
     21 struct vec2_t {
     22 	int x;
     23 	int y;
     24 };
     25 
     26 struct vec2_pair_t {
     27 	struct vec2_t a;
     28 	struct vec2_t b;
     29 };
     30 
     31 // I'll try to push stack values back and forth to see how it impacts performance
     32 struct vec2_pair_t make_pair(const char *str);
     33 struct vec2_t make_vec2(const char *str);
     34 void swap_vec2(struct vec2_t *a, struct vec2_t *b); // swap a and b
     35 void print_pair(const struct vec2_pair_t *pair);
     36 bool is_pair_diagonal(const struct vec2_pair_t *pair);
     37 void normalize_pair(struct vec2_pair_t *pair); // ensure begin is always smaller number
     38 int mark_map1(const struct vec2_pair_t *pair);
     39 int mark_map2(const struct vec2_pair_t *pair);
     40 void print_map();
     41 
     42 /* ****************************************************************** */
     43 
     44 void puzzle(const char *filename, int *result1, int *result2) {
     45 	FILE *infile = fopen(filename, "r");
     46 	if (infile == NULL) {
     47 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     48 		return;
     49 	}
     50 
     51 	char buf[STR_LEN] = {0};
     52 	unsigned int line_num = 0;
     53 
     54 	*result1 = 0;
     55 	*result2 = 0;
     56 
     57 	while (fgets(buf, STR_LEN, infile) != NULL) {
     58 		struct vec2_pair_t pair = make_pair(buf);
     59 		// only straight and 45deg diagonal lines
     60 		if (pair.a.x == pair.b.x || pair.a.y == pair.b.y || is_pair_diagonal(&pair)) {
     61 			normalize_pair(&pair);
     62 			*result1 += mark_map1(&pair);
     63 			*result2 += mark_map2(&pair);
     64 		}
     65 
     66 		++line_num;
     67 		bzero(buf, STR_LEN);
     68 	}
     69 
     70 	//print_map();
     71 
     72 	// mutiny! ignoring feof/ferror.
     73 	fclose(infile);
     74 }
     75 
     76 struct vec2_pair_t make_pair(const char *str) {
     77 	char *tmp = strndup(str, STR_LEN);
     78 	char *token = NULL;
     79 	struct vec2_pair_t pair = {0};
     80 	struct vec2_t *vectors[2] = { &pair.a, &pair.b };
     81 	int count = 0;
     82 
     83 	assert(tmp != NULL);
     84 
     85 	while ((token = strsep(&tmp, " ->\n")) != NULL) {
     86 		if (*token != '\0') {
     87 			assert(count < 2);
     88 			*vectors[count++] = make_vec2(token);
     89 		}
     90 	}
     91 
     92 	free(tmp);
     93 	return pair;
     94 }
     95 
     96 struct vec2_t make_vec2(const char *str) {
     97 	struct vec2_t vec2 = {0};
     98 	char *tmp = strndup(str, STR_LEN);
     99 	char *token = NULL;
    100 	assert(tmp != NULL);
    101 	int *coords[2] = { &vec2.x, &vec2.y };
    102 	int count = 0;
    103 
    104 	while ((token = strsep(&tmp, ",")) != NULL) {
    105 		if (*token != '\0') {
    106 			assert(count < 2);
    107 			int val = atoi(token);
    108 			assert(val < MAP_SIZE);
    109 			*coords[count++] = val;
    110 		}
    111 	}
    112 
    113 	return vec2;
    114 }
    115 
    116 void swap_vec2(struct vec2_t *a, struct vec2_t *b) {
    117 	struct vec2_t tmp = *a;
    118 	*a = *b;
    119 	*b = tmp;
    120 }
    121 
    122 void print_pair(const struct vec2_pair_t *pair) {
    123 	printf("%d,%d -> %d,%d\n", pair->a.x, pair->a.y, pair->b.x, pair->b.y);
    124 }
    125 
    126 void print_map() {
    127 	printf("\n--------MAP-----------\n");
    128 	for (int y = 0; y < MAP_SIZE; ++y) {
    129 		for (int x = 0; x < MAP_SIZE; ++x) {
    130 			if (map2[x][y] == 0) {
    131 				printf(".");
    132 			} else {
    133 				printf("%d", map2[x][y]);
    134 			}
    135 		}
    136 		printf("\n");
    137 	}
    138 	printf("\n-----------------------\n");
    139 }
    140 
    141 bool is_pair_diagonal(const struct vec2_pair_t *pair) {
    142 	return abs(pair->a.x - pair->b.x) == abs(pair->a.y - pair->b.y);
    143 }
    144 
    145 void normalize_pair(struct vec2_pair_t *pair) {
    146 	if (pair->a.x == pair->b.x && pair->a.y > pair->b.y) {
    147 		// straight verticals
    148 		swap_vec2(&pair->a, &pair->b);
    149 	} else if (pair->a.y == pair->b.y && pair->a.x > pair->b.x) {
    150 		// straight horizontals
    151 		swap_vec2(&pair->a, &pair->b);
    152 	} else if (is_pair_diagonal(pair) && pair->a.x > pair->b.x) {
    153 		// normalize diagonals only by x axis
    154 		swap_vec2(&pair->a, &pair->b);
    155 	}
    156 }
    157 
    158 int mark_map1(const struct vec2_pair_t *pair) {
    159 	int count = 0;
    160 
    161 	if (pair->a.x == pair->b.x) { // vertical lines
    162 		int x = pair->a.x;
    163 		for (int y = pair->a.y; y <= pair->b.y; ++y) {
    164 			if (++map1[x][y] == 2) {
    165 				++count;
    166 			}
    167 		}
    168 	} else if (pair->a.y == pair->b.y) { // horizontal lines
    169 		int y = pair->a.y;
    170 		for (int x = pair->a.x; x <= pair->b.x; ++x) {
    171 			if (++map1[x][y] == 2) {
    172 				++count;
    173 			}
    174 		}
    175 	}
    176 
    177 	return count;
    178 }
    179 
    180 int mark_map2(const struct vec2_pair_t *pair) {
    181 	int count = 0;
    182 
    183 	if (pair->a.x == pair->b.x) { // vertical lines
    184 		int x = pair->a.x;
    185 		for (int y = pair->a.y; y <= pair->b.y; ++y) {
    186 			if (++map2[x][y] == 2) {
    187 				++count;
    188 			}
    189 		}
    190 	} else if (pair->a.y == pair->b.y) { // horizontal lines
    191 		int y = pair->a.y;
    192 		for (int x = pair->a.x; x <= pair->b.x; ++x) {
    193 			if (++map2[x][y] == 2) {
    194 				++count;
    195 			}
    196 		}
    197 	} else if (is_pair_diagonal(pair)) { // diagonal lines
    198 		int x = pair->a.x;
    199 		int y = pair->a.y;
    200 		if (pair->a.y < pair->b.y) {
    201 			for (; x <= pair->b.x && y <= pair->b.y;) {
    202 				if (++map2[x][y] == 2) {
    203 					++count;
    204 				}
    205 				++x;
    206 				++y;
    207 			}
    208 		} else {
    209 			for (; x <= pair->b.x && y >= pair->b.y;) {
    210 				if (++map2[x][y] == 2) {
    211 					++count;
    212 				}
    213 				++x;
    214 				--y;
    215 			}
    216 		}
    217 	}
    218 
    219 	return count;
    220 }