aocc23

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

uppgb.c (2096B)

      1 #include "common.h"
      2 
      3 static inline size_t parse_next(uint64_t **rows, size_t *nrows, uint64_t **cols,
      4                                 size_t *ncols, char **lines, size_t nlines,
      5                                 size_t s) {
      6   size_t i, j;
      7   size_t nc = strlen(lines[s]) - 1;
      8 
      9   // find number of rows
     10   size_t nr = 0;
     11   while (s + nr < nlines &&
     12          (lines[s + nr][0] == '.' || lines[s + nr][0] == '#')) {
     13     nr++;
     14   }
     15 
     16   // read rows
     17   uint64_t *r = malloc(nr * sizeof(*r));
     18   for (i = 0; i < nr; i++) {
     19     // read row i
     20     r[i] = 0;
     21     for (j = 0; j < nc; j++) {
     22       r[i] <<= 1;
     23       if (lines[s + i][j] == '#') {
     24         r[i] += 1;
     25       }
     26     }
     27   }
     28 
     29   // read cols
     30   uint64_t *c = malloc(nc * sizeof(*r));
     31   for (i = 0; i < nc; i++) {
     32     c[i] = 0;
     33     for (j = 0; j < nr; j++) {
     34       c[i] <<= 1;
     35       if (lines[s + j][i] == '#') {
     36         c[i] += 1;
     37       }
     38     }
     39   }
     40 
     41   // output
     42   *rows = r;
     43   *cols = c;
     44   *nrows = nr;
     45   *ncols = nc;
     46 
     47   return nr + 1;
     48 }
     49 
     50 /**
     51  * Checks if n is a _positive_ power of 2.
     52  */
     53 static inline int is_power2(const uint64_t n) {
     54   uint64_t t;
     55 
     56   __asm__ volatile("POPCNT %1, %0;" : "=r"(t) : "r"(n) :);
     57 
     58   return t == 1;
     59 }
     60 
     61 static inline int is_refl(uint64_t *v, size_t nv, int i) {
     62   int j = i + 1;
     63 
     64   size_t smuts = 0;
     65   while (0 <= i && j < (int)nv) {
     66     if (v[i] != v[j]) {
     67       if (!is_power2(v[i] ^ v[j]))
     68         return 0;
     69       if (smuts > 0)
     70         return 0;
     71 
     72       smuts++;
     73     }
     74 
     75     i--;
     76     j++;
     77   }
     78 
     79   if (smuts == 0)
     80     return 0;
     81 
     82   return 1;
     83 }
     84 
     85 int main(int argc, char **argv) {
     86   char **lines;
     87   size_t i;
     88   size_t nlines = readlines(&lines, "input");
     89 
     90   size_t cr = 0;
     91   uint64_t summa = 0;
     92   uint64_t *rows, *cols;
     93   size_t nrows, ncols;
     94   while (cr < nlines) {
     95     cr += parse_next(&rows, &nrows, &cols, &ncols, lines, nlines, cr);
     96 
     97     for (i = 0; i < nrows - 1; i++) {
     98       if (is_refl(rows, nrows, (int)i))
     99         summa += 100 * (i + 1);
    100     }
    101 
    102     for (i = 0; i < ncols - 1; i++) {
    103       if (is_refl(cols, ncols, (int)i))
    104         summa += (i + 1);
    105     }
    106 
    107     free(rows);
    108     free(cols);
    109   }
    110 
    111   printf("%llu\n", summa);
    112 }