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 }