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 }