uppga.c (6384B)
1 #include "common.h" 2 #include <sys/queue.h> 3 4 #define NDIRS 4 5 enum direction { RIGHT, DOWN, LEFT, UP }; 6 7 typedef struct { 8 size_t r; 9 size_t c; 10 enum direction dir; 11 } walker; 12 13 typedef SIMPLEQ_HEAD(listhead, entry) head_t; 14 typedef struct entry { 15 walker v; 16 SIMPLEQ_ENTRY(entry) entries; 17 } entry_t; 18 19 int main(int argc, char **argv) { 20 char **lines; 21 size_t nrows = readlines(&lines, "input"); 22 23 size_t ncols = strnlen(lines[0], 1024); 24 assert(ncols < 1024); 25 ncols--; 26 27 uint8_t hit[NDIRS][nrows][ncols]; 28 size_t i, j, k; 29 for (k = 0; k < NDIRS; k++) { 30 for (i = 0; i < nrows; i++) { 31 for (j = 0; j < ncols; j++) { 32 hit[k][i][j] = 0; 33 } 34 } 35 } 36 37 // init queue 38 head_t head = SIMPLEQ_HEAD_INITIALIZER(head); 39 40 // initialize the start 41 walker start = {.r = 0, .c = 0, .dir = RIGHT}; 42 entry_t *se = malloc(sizeof(*se)); 43 se->v = start; 44 SIMPLEQ_INSERT_HEAD(&head, se, entries); 45 hit[RIGHT][0][0] = 1; 46 47 entry_t *c; 48 while (!SIMPLEQ_EMPTY(&head)) { 49 c = SIMPLEQ_FIRST(&head); 50 SIMPLEQ_REMOVE_HEAD(&head, entries); 51 52 walker t = c->v; 53 printf("Walker (%zu, %zu, %zu)\n", t.dir, t.r, t.c); 54 switch (t.dir) { 55 case RIGHT: 56 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '-') { 57 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 58 (c->v).c++; 59 SIMPLEQ_INSERT_TAIL(&head, c, entries); 60 hit[RIGHT][t.r][t.c + 1] = 1; 61 } else { 62 free(c); 63 } 64 } else if (lines[t.r][t.c] == '\\') { 65 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 66 (c->v).r++; 67 (c->v).dir = DOWN; 68 SIMPLEQ_INSERT_TAIL(&head, c, entries); 69 hit[DOWN][t.r + 1][t.c] = 1; 70 } else { 71 free(c); 72 } 73 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '|') { 74 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 75 (c->v).r--; 76 (c->v).dir = UP; 77 SIMPLEQ_INSERT_TAIL(&head, c, entries); 78 hit[UP][t.r - 1][t.c] = 1; 79 } else { 80 free(c); 81 } 82 83 if (lines[t.r][t.c] == '|' && t.r < nrows - 1 && 84 !hit[DOWN][t.r + 1][t.c]) { 85 entry_t *nc = malloc(sizeof(*nc)); 86 (nc->v).c = t.c; 87 (nc->v).r = t.r + 1; 88 (nc->v).dir = DOWN; 89 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 90 hit[DOWN][t.r + 1][t.c] = 1; 91 } 92 } 93 break; 94 case DOWN: 95 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '|') { 96 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 97 (c->v).r++; 98 SIMPLEQ_INSERT_TAIL(&head, c, entries); 99 hit[DOWN][t.r + 1][t.c] = 1; 100 } else { 101 free(c); 102 } 103 } else if (lines[t.r][t.c] == '\\') { 104 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 105 (c->v).c++; 106 (c->v).dir = RIGHT; 107 SIMPLEQ_INSERT_TAIL(&head, c, entries); 108 hit[RIGHT][t.r][t.c + 1] = 1; 109 } else { 110 free(c); 111 } 112 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '-') { 113 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 114 (c->v).c--; 115 (c->v).dir = LEFT; 116 SIMPLEQ_INSERT_TAIL(&head, c, entries); 117 hit[LEFT][t.r][t.c - 1] = 1; 118 } else { 119 free(c); 120 } 121 122 if (lines[t.r][t.c] == '-' && t.c < ncols - 1 && 123 !hit[RIGHT][t.r][t.c + 1]) { 124 entry_t *nc = malloc(sizeof(*nc)); 125 (nc->v).c = t.c + 1; 126 (nc->v).r = t.r; 127 (nc->v).dir = RIGHT; 128 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 129 hit[RIGHT][t.r][t.c + 1] = 1; 130 } 131 } 132 break; 133 case LEFT: 134 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '-') { 135 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 136 (c->v).c--; 137 SIMPLEQ_INSERT_TAIL(&head, c, entries); 138 hit[LEFT][t.r][t.c - 1] = 1; 139 } else { 140 free(c); 141 } 142 } else if (lines[t.r][t.c] == '\\') { 143 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 144 (c->v).r--; 145 (c->v).dir = UP; 146 SIMPLEQ_INSERT_TAIL(&head, c, entries); 147 hit[UP][t.r - 1][t.c] = 1; 148 } else { 149 free(c); 150 } 151 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '|') { 152 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 153 (c->v).r++; 154 (c->v).dir = DOWN; 155 SIMPLEQ_INSERT_TAIL(&head, c, entries); 156 hit[DOWN][t.r + 1][t.c] = 1; 157 } else { 158 free(c); 159 } 160 161 if (lines[t.r][t.c] == '|' && t.r > 0 && !hit[UP][t.r - 1][t.c]) { 162 entry_t *nc = malloc(sizeof(*nc)); 163 (nc->v).c = t.c; 164 (nc->v).r = t.r - 1; 165 (nc->v).dir = UP; 166 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 167 hit[UP][t.r - 1][t.c] = 1; 168 } 169 } 170 break; 171 case UP: 172 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '|') { 173 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 174 (c->v).r--; 175 SIMPLEQ_INSERT_TAIL(&head, c, entries); 176 hit[UP][t.r - 1][t.c] = 1; 177 } else { 178 free(c); 179 } 180 } else if (lines[t.r][t.c] == '\\') { 181 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 182 (c->v).c--; 183 (c->v).dir = LEFT; 184 SIMPLEQ_INSERT_TAIL(&head, c, entries); 185 hit[LEFT][t.r][t.c - 1] = 1; 186 } else { 187 free(c); 188 } 189 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '-') { 190 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 191 (c->v).c++; 192 (c->v).dir = RIGHT; 193 SIMPLEQ_INSERT_TAIL(&head, c, entries); 194 hit[RIGHT][t.r][t.c + 1] = 1; 195 } else { 196 free(c); 197 } 198 199 if (lines[t.r][t.c] == '-' && t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 200 entry_t *nc = malloc(sizeof(*nc)); 201 (nc->v).c = t.c - 1; 202 (nc->v).r = t.r; 203 (nc->v).dir = LEFT; 204 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 205 hit[LEFT][t.r][t.c - 1] = 1; 206 } 207 } 208 break; 209 } 210 } 211 212 uint64_t count = 0; 213 for (i = 0; i < nrows; i++) { 214 for (j = 0; j < ncols; j++) { 215 if (hit[RIGHT][i][j] || hit[LEFT][i][j] || hit[DOWN][i][j] || 216 hit[UP][i][j]) { 217 printf("#"); 218 count++; 219 } else { 220 printf("."); 221 } 222 } 223 printf("\n"); 224 } 225 226 printf("%llu\n", count); 227 }