aocc22

uppgb.c (5687B)

---

 #include "common.h"
 
 #define SEC 30ULL
 #define NOTCOMPUTED UINT64_MAX
 #define NONBR SIZE_MAX
 
 #define ASIZE ((uint64_t)('Z' - 'A' + 1))
 #define MAP_SIZE (ASIZE * ASIZE)
 
 typedef struct {
   size_t n;
   size_t m;
 
   size_t nv;
   uint64_t *v; // store computed values
 
   uint64_t *flows;
   size_t *nzflows; // maps position to index of nonzero flow (in e.g. state)
   size_t **nbrs;
 } valves;
 
 static inline size_t statelen(valves v) { return v.m + 2; }
 
 static inline size_t statemax(valves v) { return ((v.n) * (v.n) << v.m) - 1; }
 
 static inline char *goto_nbrs(char *s) {
   size_t i = 0, c = 0;
   while (c != 9) {
     if (s[i] == ' ')
       c++;
     i++;
   }
   return &(s[i]);
 }
 
 static inline size_t map_index(char *x) {
   return ASIZE * ((uint64_t)(x[0] - 'A')) + ((uint64_t)(x[1] - 'A'));
 }
 
 void init_valves(valves *v, char **lines, const size_t n) {
   v->n = n;
   v->m = 0;
 
   v->flows = malloc((v->n) * sizeof(*(v->flows)));
   v->nzflows = malloc((v->n) * sizeof(*(v->nzflows)));
   v->nbrs = malloc((v->n) * sizeof(*(v->nbrs)));
 
   size_t i, j;
   size_t map[MAP_SIZE];
   for (i = 0; i < MAP_SIZE; i++)
     map[i] = SIZE_MAX;
   for (i = 0; i < n; i++) {
     char *line = lines[i];
     map[map_index(&line[6])] = i;
   }
 
   for (i = 0; i < n; i++) {
     char *line = lines[i];
 
     char *flowstr = &line[23];
     uint64_t flow;
     sread_next_u64(&flow, flowstr);
     v->flows[i] = flow;
     if (flow != 0) {
       v->nzflows[i] = v->m;
       v->m++;
     } else {
       v->nzflows[i] = SIZE_MAX;
     }
 
     v->nbrs[i] = malloc((v->n) * sizeof(*(v->nbrs[i])));
     char *nbrs = goto_nbrs(line);
     char *cn = nbrs;
     j = 0;
     while (cn[0] != '\n' && cn[0] != '\0') {
       assert(cn[0] <= 'Z' && cn[0] >= 'A');
       assert(cn[1] <= 'Z' && cn[1] >= 'A');
       v->nbrs[i][j] = map[map_index(cn)];
       if (strlen(cn) < 4) {
         j++;
         break;
       }
       j++;
       cn = &cn[4];
     }
     while (j < v->n) {
       v->nbrs[i][j] = NONBR;
       j++;
     }
   }
 
   v->nv = statemax(*v) + 1;
   v->v = malloc((v->nv) * sizeof(*(v->v)));
 }
 
 size_t f(const uint8_t *state, const valves *v) {
   size_t r = ((unsigned long)state[0]) * (v->n) + (unsigned long)state[1];
   size_t i;
   for (i = 0; i < v->m; i++) {
     r <<= 1;
     if (state[i + 2])
       r++;
   }
   return r;
 }
 
 void f_inv(uint8_t *state, const size_t y, const valves *v) {
   size_t i;
   size_t slen = statelen(*v);
 
   size_t x = y;
 
   for (i = 1; i <= v->m; i++) {
     if ((x & 0x01) != 0) {
       state[slen - i] = 1;
     } else {
       state[slen - i] = 0;
     }
     x >>= 1;
   }
 
   assert(x < (v->n) * (v->n));
 
   state[1] = (uint8_t)(x % (v->n));
   state[0] = (uint8_t)(x / (v->n));
 }
 
 uint8_t *init_starting_state(valves v) {
   uint8_t *r = malloc(statelen(v));
 
   r[0] = 0; // posituon AA == 0
   r[1] = 0; // elephant position same
 
   size_t i;
   for (i = 2; i < v.m + 2; i++)
     r[i] = 0; // no valves on
 
   return r;
 }
 
 static inline uint64_t stateflow(uint64_t b, const valves *v) {
   uint64_t r = 0;
   size_t i;
   for (i = 0; i < v->n; i++) {
     if (v->flows[i] != 0 && (b & (0x1 << v->nzflows[i])) != 0) {
       r += v->flows[i];
     }
   }
   return r;
 }
 
 void print_state(const uint8_t *state, const valves *v) {
   printf("%u : %u : ", state[0], state[1]);
   size_t i;
   for (i = 0; i < v->m; i++) {
     printf("%u ", state[i + 2]);
   }
   printf("\n");
 }
 
 static inline uint64_t vss(size_t s, valves *v) {
   return 0x01 << (v->m - s - 1);
 }
 
 static inline uint64_t fss(uint64_t py, uint64_t pe, uint64_t b, valves *v) {
   uint64_t r = py * (v->n) + pe;
   size_t i;
   for (i = 0; i < v->m; i++) {
     r <<= 1;
     if ((b & vss(i, v)) != 0)
       r++;
   }
   return r;
 }
 
 uint64_t *compute_level(valves *v, int level) {
   size_t i, j;
   uint64_t b;
   uint64_t *new = malloc((v->nv) * sizeof(*new));
 
   if (level <= 0) {
     for (i = 0; i < v->nv; i++)
       new[i] = 0;
   } else {
     size_t blim = (1 << v->m);
     for (i = 0; i < v->n; i++) {   // you pos
       for (j = 0; j < v->n; j++) { // E pos
         for (b = 0; b < blim; b++) {
           uint64_t best = 0;
           if (v->flows[i] != 0 && v->flows[j] != 0) {
             best = v->v[fss(
                 i, j, (b | (0x01 << v->nzflows[i]) | (0x01 << v->nzflows[j])),
                 v)];
           }
 
           uint64_t bprim;
           size_t k = 0, l;
           uint64_t t;
           if (v->flows[i] != 0) {
             k = 0;
             bprim = b | (0x01 << v->nzflows[i]);
             while (v->nbrs[j][k] != NONBR) {
               t = v->v[fss(i, v->nbrs[j][k], bprim, v)];
               if (t > best)
                 best = t;
               k++;
             }
           }
 
           if (v->flows[j] != 0) {
             bprim = b | (0x01 << v->nzflows[j]);
             k = 0;
             while (v->nbrs[i][k] != NONBR) {
               t = v->v[fss(v->nbrs[i][k], j, bprim, v)];
               if (t > best)
                 best = t;
               k++;
             }
           }
 
           k = 0;
           while (v->nbrs[i][k] != NONBR) {
             l = 0;
             while (v->nbrs[j][l] != NONBR) {
               t = v->v[fss(v->nbrs[i][k], v->nbrs[j][l], b, v)];
               if (t > best)
                 best = t;
               l++;
             }
             k++;
           }
 
           new[fss(i, j, b, v)] = stateflow(b, v) + best;
         }
       }
     }
   }
 
   return new;
 }
 
 int main(int argc, char **argv) {
   char **lines;
   valves v;
   size_t nlines = readlines(&lines, "sinput");
 
   init_valves(&v, lines, nlines);
   uint64_t *r;
   size_t i;
   for (i = 0; i < 27; i++) {
     printf("--- LEVEL %zu ---\n", i);
     r = compute_level(&v, i);
     free(v.v);
     v.v = r;
   }
 
   printf("%llu\n", v.v[fss(0, 0, 0, &v)]);
 }