aocc23

uppgb.c (5036B)

---

 #include "common.h"
 
 #define ALPHSIZE 26
 #define BUTT 676
 #define BRDC 677
 
 #define QZ 441
 #define CQ 68
 #define JX 257
 #define TT 513
 
 typedef SIMPLEQ_HEAD(listhead, entry) head_t;
 
 typedef struct entry {
   size_t from;
   size_t to;
   uint8_t val;
 
   SIMPLEQ_ENTRY(entry) entries;
 } sig_t;
 
 typedef struct {
   char *name;
   uint8_t type;
 
   uint64_t state;
   size_t *inshift;
   size_t nstate;
 
   stack_u64 nbrs;
 } gate_t;
 
 static inline size_t pure_name_idx(char *s) {
   return ((s[0] - 'a') * ALPHSIZE + (s[1] - 'a'));
 }
 
 static inline size_t name_idx(char *s) {
   if (s[0] == 'b') {
     if (s[1] == 'r') {
       return BRDC;
     } else {
       return BUTT;
     }
   }
 
   return pure_name_idx(&s[1]);
 }
 
 static inline void init_gate(gate_t *gt, char *line) {
   gt->state = 0;
   gt->name = line;
 
   switch (line[0]) {
   case '&':
     gt->type = '&';
     break;
   case '%':
     gt->type = '%';
     break;
   default:
     gt->type = 'x';
   }
 
   stack_u64_init(&gt->nbrs);
 
   char *cp = line;
   while (*cp != ' ')
     cp++;
   cp++;
 
   while (*cp != '\n' && *cp != EOF) {
     while (*cp != ' ' && *cp != '\n' && *cp != EOF)
       cp++;
     if (*cp != ' ')
       break;
     cp++;
 
     stack_u64_push(&gt->nbrs, pure_name_idx(cp));
 
     cp++;
   }
 }
 
 static inline void init_states(gate_t *gates) {
   size_t i, j, to;
   size_t countin[BRDC + 1] = {0};
 
   for (i = 0; i < BRDC + 1; i++) {
     if (gates[i].name != NULL) {
       if (gates[i].type == '&') {
         gates[i].inshift = malloc((BRDC + 1) * sizeof(*(gates[i].inshift)));
       } else {
         gates[i].inshift = NULL;
       }
     }
   }
 
   for (i = 0; i < BRDC + 1; i++) {
     if (gates[i].name != NULL) {
       for (j = 0; j < gates[i].nbrs.nmemb; j++) {
         to = gates[i].nbrs.data[j];
         if (gates[to].type == '&')
           gates[to].inshift[i] = countin[to];
         countin[to]++;
       }
     }
   }
 
   for (i = 0; i < BRDC + 1; i++) {
     if (gates[i].name != NULL) {
       switch (gates[i].type) {
       case '%':
         gates[i].nstate = 1;
         break;
       case '&':
         gates[i].nstate = countin[i];
         break;
       default:
         gates[i].nstate = SIZE_MAX;
       }
     }
   }
 }
 
 static inline void send_pulses(gate_t *gate, size_t from, head_t *head,
                                uint8_t pulse) {
   size_t i;
   for (i = 0; i < gate->nbrs.nmemb; i++) {
     sig_t *n = malloc(sizeof(*n));
     n->from = from;
     n->to = gate->nbrs.data[i];
     n->val = pulse;
     SIMPLEQ_INSERT_TAIL(head, n, entries);
   }
 }
 
 static inline void set_bit(uint64_t *out, size_t i, uint8_t val) {
   assert(i < 63);
 
   if (val) {
     *out |= (1ULL << i);
   } else {
     *out &= (0xffffffffffffffffULL ^ (1ULL << i));
   }
 }
 
 static inline void push(gate_t *gates, size_t idx, size_t *cycla,
                         size_t *cyclb) {
   size_t i;
   head_t head = SIMPLEQ_HEAD_INITIALIZER(head);
 
   sig_t *s = malloc(sizeof(*s));
   s->from = BUTT;
   s->to = BRDC;
   s->val = 0;
 
   SIMPLEQ_INSERT_HEAD(&head, s, entries);
 
   uint64_t clow = 0;
   uint64_t chig = 0;
 
   while (!SIMPLEQ_EMPTY(&head)) {
     s = SIMPLEQ_FIRST(&head);
     SIMPLEQ_REMOVE_HEAD(&head, entries);
 
     if (s->val == 0) {
       clow++;
     } else {
       chig++;
     }
 
     if (s->val == 1 && s->to == 429) {
       if (cycla[s->from] == SIZE_MAX) {
         cycla[s->from] = idx + 1;
       } else if (cyclb[s->from] == SIZE_MAX && idx + 1 != cycla[s->from]) {
         cyclb[s->from] = idx + 1;
       }
     }
 
     switch (gates[s->to].type) {
     case '%':
       if (s->val == 0) {
         gates[s->to].state ^= 1;
         send_pulses(&gates[s->to], s->to, &head, (uint8_t)gates[s->to].state);
       }
       break;
     case '&':
       set_bit(&(gates[s->to].state), gates[s->to].inshift[s->from], s->val);
 
       uint8_t spulse = 0;
       for (i = 0; i < gates[s->to].nstate; i++) {
         if ((gates[s->to].state & (1ULL << i)) == 0) {
           spulse = 1;
           break;
         }
       }
 
       send_pulses(&gates[s->to], s->to, &head, spulse);
       break;
     case 'x':
       assert(s->from == BUTT);
       assert(s->to == BRDC);
       send_pulses(&gates[s->to], s->to, &head, 0);
       break;
     default:
       assert(s->to == 465); // rx the only one
     }
 
     free(s);
   }
 }
 
 int main(int argc, char **argv) {
   char **lines;
   size_t nlines = readlines(&lines, "input");
 
   gate_t gates[BRDC + 1];
   size_t i;
   for (i = 0; i < BRDC + 1; i++)
     gates[i].name = NULL;
 
   size_t g;
   for (i = 0; i < nlines; i++) {
     g = name_idx(lines[i]);
     init_gate(&gates[g], lines[i]);
   }
 
   init_states(gates);
 
   size_t cycla[BRDC + 1];
   size_t cyclb[BRDC + 1];
   for (i = 0; i < BRDC + 1; i++) {
     cycla[i] = SIZE_MAX;
     cyclb[i] = SIZE_MAX;
   }
 
   for (i = 0; i < 10000; i++) {
     push(gates, i, cycla, cyclb);
   }
 
   mpz_t p;
   mpz_init_set_ui(p, 1);
 
   for (i = 0; i < BRDC + 1; i++) {
     if (cycla[i] != SIZE_MAX) {
       assert(cyclb[i] == cycla[i] * 2); // this makes the cycle possible
       mpz_lcm_ui(p, p, cycla[i]);
     }
   }
 
   gmp_printf("%Zd\n", p);
 
   mpz_clear(p);
 }