aocc23

Advent of Code 2023
git clone git://www.tkruger.se/aocc23.git
Log | Files | Refs | README

uppgb.c (6820B)

      1 #include "common.h"
      2 
      3 typedef struct {
      4   size_t na;
      5   size_t nb;
      6 } pos_t;
      7 
      8 static inline pos_t compute_nbrs(size_t row, size_t col, char **lines,
      9                                  size_t nrows, size_t ncols) {
     10   pos_t r;
     11 
     12   switch (lines[row][col]) {
     13   case '|':
     14     if (row == 0 || row == nrows - 1) {
     15       r.na = SIZE_MAX;
     16       r.nb = SIZE_MAX;
     17     } else {
     18       r.na = (row - 1) * ncols + col;
     19       r.nb = (row + 1) * ncols + col;
     20     }
     21     break;
     22   case '-':
     23     if (col == 0 || col == ncols - 1) {
     24       r.na = SIZE_MAX;
     25       r.nb = SIZE_MAX;
     26     } else {
     27       r.na = row * ncols + col - 1;
     28       r.nb = row * ncols + col + 1;
     29     }
     30     break;
     31   case 'F':
     32     if (col == ncols - 1 || row == nrows - 1) {
     33       r.na = SIZE_MAX;
     34       r.nb = SIZE_MAX;
     35     } else {
     36       r.na = row * ncols + col + 1;
     37       r.nb = (row + 1) * ncols + col;
     38     }
     39     break;
     40   case '7':
     41     if (col == 0 || row == nrows - 1) {
     42       r.na = SIZE_MAX;
     43       r.nb = SIZE_MAX;
     44     } else {
     45       r.na = row * ncols + col - 1;
     46       r.nb = (row + 1) * ncols + col;
     47     }
     48     break;
     49   case 'L':
     50     if (col == ncols - 1 || row == 0) {
     51       r.na = SIZE_MAX;
     52       r.nb = SIZE_MAX;
     53     } else {
     54       r.na = (row - 1) * ncols + col;
     55       r.nb = row * ncols + col + 1;
     56     }
     57     break;
     58   case 'J':
     59     if (col == 0 || row == 0) {
     60       r.na = SIZE_MAX;
     61       r.nb = SIZE_MAX;
     62     } else {
     63       r.na = (row - 1) * ncols + col;
     64       r.nb = row * ncols + col - 1;
     65     }
     66     break;
     67   default: // S or .
     68     r.na = SIZE_MAX;
     69     r.nb = SIZE_MAX;
     70   }
     71 
     72   return r;
     73 }
     74 
     75 static inline size_t traverse(char *type, size_t start, size_t next, pos_t *ns,
     76                               uint8_t *visited, size_t nn) {
     77   size_t head = next;
     78   size_t tail = start;
     79   size_t steps = 0;
     80 
     81   int exit = 0;
     82   if (head > tail) {
     83     if (head - tail == 1) {
     84       exit = 1; // east
     85     } else {
     86       exit = 2; // south
     87     }
     88   } else {
     89     if (tail - head == 1) {
     90       exit = 3; // west
     91     } else {
     92       exit = 4; // north
     93     }
     94   }
     95 
     96   memset(visited, nn, sizeof(*visited));
     97   visited[head] = 1;
     98   visited[tail] = 1;
     99 
    100   if (ns[head].na != tail && ns[head].nb != tail) {
    101     return SIZE_MAX;
    102   }
    103 
    104   while (head != start && ns[head].na != SIZE_MAX) {
    105     size_t tmp = head;
    106     if (ns[head].na == tail) {
    107       head = ns[head].nb;
    108     } else {
    109       head = ns[head].na;
    110     }
    111     tail = tmp;
    112     visited[head] = 1;
    113     steps++;
    114   }
    115 
    116   int enter = 0;
    117   if (head > tail) {
    118     if (head - tail == 1) {
    119       enter = 3; // east
    120     } else {
    121       enter = 4; // south
    122     }
    123   } else {
    124     if (tail - head == 1) {
    125       enter = 1; // west
    126     } else {
    127       enter = 2; // north
    128     }
    129   }
    130 
    131   if (exit == 1) {
    132     if (enter == 2) {
    133       *type = 'F';
    134     } else if (enter == 3) {
    135       *type = '-';
    136     } else if (enter == 4) {
    137       *type = 'L';
    138     }
    139   } else if (exit == 2) {
    140     if (enter == 1) {
    141       *type = 'F';
    142     } else if (enter == 3) {
    143       *type = '7';
    144     } else if (enter == 4) {
    145       *type = '|';
    146     }
    147   } else if (exit == 3) {
    148     if (enter == 1) {
    149       *type = '-';
    150     } else if (enter == 2) {
    151       *type = '7';
    152     } else if (enter == 4) {
    153       *type = 'J';
    154     }
    155   } else if (exit == 4) {
    156     if (enter == 1) {
    157       *type = 'L';
    158     } else if (enter == 2) {
    159       *type = '|';
    160     } else if (enter == 3) {
    161       *type = 'J';
    162     }
    163   }
    164 
    165   if (head == start)
    166     return steps;
    167 
    168   return SIZE_MAX;
    169 }
    170 
    171 #define IDX(r, c, n) ((3 * n) * (3 * r + 1) + (3 * c) + 1)
    172 
    173 int main(int argc, char **argv) {
    174   char **lines;
    175   size_t i, j;
    176   size_t nlines = readlines(&lines, "input");
    177 
    178   size_t ncols = strlen(lines[0]) - 1;
    179 
    180   size_t start;
    181   pos_t ns[nlines * ncols];
    182   for (i = 0; i < nlines; i++) {
    183     for (j = 0; j < ncols; j++) {
    184       ns[i * ncols + j] = compute_nbrs(i, j, lines, nlines, ncols);
    185       if (lines[i][j] == 'S') {
    186         start = i * ncols + j;
    187       }
    188     }
    189   }
    190 
    191   uint8_t visited[nlines * ncols];
    192   size_t r;
    193   char type;
    194   if ((r = traverse(&type, start, start + 1, ns, visited, nlines * ncols)) !=
    195       SIZE_MAX) {
    196   } else if ((r = traverse(&type, start, start - 1, ns, visited,
    197                            nlines * ncols)) != SIZE_MAX) {
    198   } else if ((r = traverse(&type, start, start + ncols, ns, visited,
    199                            nlines * ncols)) != SIZE_MAX) {
    200   } else {
    201     printf("bad\n");
    202     exit(1);
    203   }
    204   visited[0] = 0;
    205 
    206   for (i = 0; i < nlines; i++) {
    207     for (j = 0; j < ncols; j++) {
    208       if (!visited[i * ncols + j]) {
    209         lines[i][j] = '.';
    210       }
    211       if (lines[i][j] == 'S')
    212         lines[i][j] = type;
    213     }
    214   }
    215 
    216   uint8_t *expander = calloc((3 * ncols * 3 * nlines), sizeof(*expander));
    217 
    218   for (i = 0; i < nlines; i++) {
    219     for (j = 0; j < ncols; j++) {
    220       switch (lines[i][j]) {
    221       case '-':
    222         expander[IDX(i, j, ncols)] = 1;
    223         expander[IDX(i, j, ncols) - 1] = 1;
    224         expander[IDX(i, j, ncols) + 1] = 1;
    225         break;
    226       case '|':
    227         expander[IDX(i, j, ncols)] = 1;
    228         expander[IDX(i, j, ncols) - 3 * ncols] = 1;
    229         expander[IDX(i, j, ncols) + 3 * ncols] = 1;
    230         break;
    231       case 'F':
    232         expander[IDX(i, j, ncols)] = 1;
    233         expander[IDX(i, j, ncols) + 1] = 1;
    234         expander[IDX(i, j, ncols) + 3 * ncols] = 1;
    235         break;
    236       case '7':
    237         expander[IDX(i, j, ncols)] = 1;
    238         expander[IDX(i, j, ncols) - 1] = 1;
    239         expander[IDX(i, j, ncols) + 3 * ncols] = 1;
    240         break;
    241       case 'L':
    242         expander[IDX(i, j, ncols)] = 1;
    243         expander[IDX(i, j, ncols) + 1] = 1;
    244         expander[IDX(i, j, ncols) - 3 * ncols] = 1;
    245         break;
    246       case 'J':
    247         expander[IDX(i, j, ncols)] = 1;
    248         expander[IDX(i, j, ncols) - 1] = 1;
    249         expander[IDX(i, j, ncols) - 3 * ncols] = 1;
    250         break;
    251       default:
    252         expander[IDX(i, j, ncols)] = 0;
    253         break;
    254       }
    255     }
    256   }
    257 
    258   stack_u64 stack;
    259   stack_u64_init(&stack);
    260   stack_u64_push(&stack, 0);
    261   expander[0] = 1;
    262 
    263   size_t x;
    264   while (stack.nmemb > 0) {
    265     x = stack_u64_pop(&stack);
    266 
    267     if (x % (3 * ncols) != 0 && expander[x - 1] == 0) {
    268       stack_u64_push(&stack, x - 1);
    269       expander[x - 1] = 1;
    270     }
    271 
    272     if ((x + 1) % (3 * ncols) != 0 && expander[x + 1] == 0) {
    273       stack_u64_push(&stack, x + 1);
    274       expander[x + 1] = 1;
    275     }
    276 
    277     if ((x >= 3 * ncols) && expander[x - 3 * ncols] == 0) {
    278       stack_u64_push(&stack, x - 3 * ncols);
    279       expander[x - 3 * ncols] = 1;
    280     }
    281 
    282     if ((x < (3 * nlines - 1) * (3 * ncols)) && expander[x + 3 * ncols] == 0) {
    283       stack_u64_push(&stack, x + 3 * ncols);
    284       expander[x + 3 * ncols] = 1;
    285     }
    286   }
    287 
    288   uint64_t count = 0;
    289   for (i = 0; i < 3 * nlines; i++) {
    290     for (j = 0; j < 3 * ncols; j++) {
    291       if (!expander[(3 * ncols) * i + j]) {
    292         if (i % 3 == 1 && j % 3 == 1) {
    293           count++;
    294         }
    295       }
    296     }
    297   }
    298 
    299   printf("%llu\n", count);
    300 
    301   free(expander);
    302 }