puzzle.c (4218B)
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 <assert.h> 9 #include <ctype.h> 10 #include <stdbool.h> 11 #include <math.h> 12 #include <unistd.h> 13 14 #include "util.h" 15 16 #define STR_LEN 1024 17 18 struct cucumber_t { 19 enum direction_t { SOUTH, EAST } direction; 20 bool stuck; 21 uint64_t step; 22 }; 23 24 struct tile_t { 25 struct cucumber_t *cucumber; 26 }; 27 28 struct map_t { 29 struct tile_t *tiles; 30 int width; 31 int height; 32 }; 33 34 void print_map(struct map_t *map); 35 int step(struct map_t *map, uint64_t step); 36 37 void puzzle(const char *filename, long long *result1, long long *result2) { 38 FILE *infile = fopen(filename, "r"); 39 if (infile == NULL) { 40 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 41 return; 42 } 43 44 char buf[STR_LEN] = {0}; 45 size_t line = 0; 46 struct map_t map = {0}; 47 48 while (fgets(buf, STR_LEN, infile) != NULL) { 49 int len = strlen(buf); 50 assert(len > 0); 51 if (map.width > 0 && map.width != len-1) { 52 printf("invalid input\n"); 53 exit(1); 54 } 55 map.width = len-1; 56 line = map.height++; 57 map.tiles = realloc(map.tiles, sizeof(struct tile_t) * map.width * map.height); 58 for (int i = 0; i < len-1; ++i) { 59 char c = buf[i]; 60 if (c == '>' || c == 'v') { 61 struct cucumber_t *cucumber = malloc(sizeof(struct cucumber_t)); 62 assert(cucumber != NULL); 63 cucumber->direction = (c == '>') ? EAST : SOUTH; 64 cucumber->stuck = false; 65 cucumber->step = 0; 66 map.tiles[line*map.width+i].cucumber = cucumber; 67 } else { 68 map.tiles[line*map.width+i].cucumber = NULL; 69 } 70 } 71 bzero(buf, STR_LEN); 72 } 73 74 //printf("map width: %d, height: %d\n", map.width, map.height); 75 //print_map(&map); 76 for (uint64_t i = 1;; ++i) { 77 if (step(&map, i) == 0) { 78 *result1 = i; 79 break; 80 } 81 } 82 //print_map(&map); 83 *result2 = 0; 84 85 // mutiny! ignoring feof/ferror. 86 fclose(infile); 87 } 88 89 void print_map(struct map_t *map) { 90 assert(map != NULL); 91 printf("----------\n"); 92 for (int y = 0; y < map->height; ++y) { 93 for (int x = 0; x < map->width; ++x) { 94 struct tile_t *tile = &map->tiles[y*map->width+x]; 95 if (tile->cucumber != NULL) { 96 printf("%c", tile->cucumber->direction == SOUTH ? 'v' : '>'); 97 } else { 98 printf("."); 99 } 100 } 101 printf("\n"); 102 } 103 printf("\n"); 104 } 105 106 int step(struct map_t *map, uint64_t step) { 107 int moved = 0; 108 // eastbound cucumbers 109 for (int y = 0; y < map->height; ++y) { 110 for (int x = 0; x < map->width; ++x) { 111 int nx = (x == map->width-1) ? 0 : x+1; 112 struct tile_t *tile = &map->tiles[map->width*y+x]; 113 struct tile_t *next = &map->tiles[map->width*y+nx]; 114 if (tile->cucumber != NULL && tile->cucumber->direction == EAST && tile->cucumber->step != step) { 115 tile->cucumber->stuck = next->cucumber != NULL; 116 } 117 } 118 } 119 for (int y = 0; y < map->height; ++y) { 120 for (int x = 0; x < map->width; ++x) { 121 int nx = (x == map->width-1) ? 0 : x+1; 122 struct tile_t *tile = &map->tiles[map->width*y+x]; 123 struct tile_t *next = &map->tiles[map->width*y+nx]; 124 if (tile->cucumber != NULL && tile->cucumber->direction == EAST && !tile->cucumber->stuck && tile->cucumber->step != step) { 125 assert(next->cucumber == NULL); 126 tile->cucumber->step = step; 127 next->cucumber = tile->cucumber; 128 tile->cucumber = NULL; 129 moved++; 130 } 131 } 132 } 133 // southbound cucumbers 134 for (int y = 0; y < map->height; ++y) { 135 int ny = (y == map->height-1) ? 0 : y+1; 136 for (int x = 0; x < map->width; ++x) { 137 struct tile_t *tile = &map->tiles[map->width*y+x]; 138 struct tile_t *next = &map->tiles[map->width*ny+x]; 139 if (tile->cucumber != NULL && tile->cucumber->direction == SOUTH && tile->cucumber->step != step) { 140 tile->cucumber->stuck = next->cucumber != NULL; 141 } 142 } 143 } 144 for (int y = 0; y < map->height; ++y) { 145 int ny = (y == map->height-1) ? 0 : y+1; 146 for (int x = 0; x < map->width; ++x) { 147 struct tile_t *tile = &map->tiles[map->width*y+x]; 148 struct tile_t *next = &map->tiles[map->width*ny+x]; 149 if (tile->cucumber != NULL && tile->cucumber->direction == SOUTH && !tile->cucumber->stuck && tile->cucumber->step != step) { 150 assert(next->cucumber == NULL); 151 tile->cucumber->step = step; 152 next->cucumber = tile->cucumber; 153 tile->cucumber = NULL; 154 moved++; 155 } 156 } 157 } 158 return moved; 159 }