aocc23

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

uppgb.c (2382B)

      1 #include "common.h"
      2 
      3 #define ZZZ 17575
      4 #define AAA 0
      5 
      6 static inline stack_u64 read_starts(char **lines, size_t nlines) {
      7   size_t i;
      8   stack_u64 r;
      9   stack_u64_init(&r);
     10 
     11   for (i = 2; i < nlines; i++) {
     12     if (lines[i][2] == 'A') {
     13       stack_u64_push(&r, chrs_to_node(lines[i]));
     14     }
     15   }
     16 
     17   return r;
     18 }
     19 
     20 // positition = (value, ins) where 0 <= ins < #instructions
     21 typedef struct {
     22   uint64_t v;
     23   size_t ins;
     24 } pos_t;
     25 
     26 typedef struct {
     27   uint64_t *ls;
     28   uint64_t *rs;
     29 
     30   char *ins;
     31   size_t nins;
     32 } gr_t;
     33 
     34 static inline pos_t stepf(pos_t x, gr_t *g) {
     35   pos_t r;
     36   r.ins = (x.ins + 1) % g->nins;
     37   if (g->ins[x.ins] == 'L') {
     38     r.v = g->ls[x.v];
     39   } else {
     40     r.v = g->rs[x.v];
     41   }
     42 
     43   return r;
     44 }
     45 
     46 static inline void floyd(stack_u64 *mus, stack_u64 *lams, pos_t s, gr_t *g) {
     47   pos_t tortoise = stepf(s, g);
     48   pos_t hare = stepf(tortoise, g);
     49 
     50   while (tortoise.v != hare.v || tortoise.ins != hare.ins) {
     51     tortoise = stepf(tortoise, g);
     52     hare = stepf(stepf(hare, g), g);
     53   }
     54 
     55   uint64_t mu = 0;
     56   tortoise = s;
     57   while (tortoise.v != hare.v || tortoise.ins != hare.ins) {
     58     tortoise = stepf(tortoise, g);
     59     hare = stepf(hare, g);
     60     mu++;
     61   }
     62 
     63   uint64_t lam = 1;
     64   hare = stepf(tortoise, g);
     65   while (tortoise.v != hare.v || tortoise.ins != hare.ins) {
     66     hare = stepf(hare, g);
     67     lam++;
     68   }
     69 
     70   stack_u64_push(mus, mu);
     71   stack_u64_push(lams, lam);
     72 }
     73 
     74 static uint64_t lcm(stack_u64 *s) {
     75   mpz_t l, t1;
     76   mpz_inits(l, t1, NULL);
     77   mpz_set_ui(l, s->data[0]);
     78 
     79   size_t i;
     80   for (i = 1; i < s->nmemb; i++) {
     81     mpz_set_ui(t1, s->data[i]);
     82     mpz_lcm(l, l, t1);
     83   }
     84 
     85   uint64_t r = mpz_get_ui(l);
     86 
     87   mpz_clears(l, t1, NULL);
     88 
     89   return r;
     90 }
     91 
     92 int main(int argc, char **argv) {
     93   size_t i, nins = 0;
     94   char **lines;
     95   size_t nlines = readlines(&lines, "input");
     96 
     97   char *instructions = lines[0];
     98   while (instructions[nins] == 'R' || instructions[nins] == 'L') {
     99     nins++;
    100   }
    101 
    102   uint64_t lefts[ZZZ + 1];
    103   uint64_t rights[ZZZ + 1];
    104   read_graph(lefts, rights, lines, nlines);
    105 
    106   gr_t g = {lefts, rights, instructions, nins};
    107 
    108   stack_u64 starts = read_starts(lines, nlines);
    109   stack_u64 mus, lams;
    110   stack_u64_init(&mus);
    111   stack_u64_init(&lams);
    112 
    113   for (i = 0; i < starts.nmemb; i++) {
    114     pos_t first = {starts.data[i], 0};
    115     floyd(&mus, &lams, first, &g);
    116   }
    117 
    118   uint64_t lcm_lam = lcm(&lams);
    119   printf("%llu\n", lcm_lam);
    120 
    121   stack_u64_clear(&starts);
    122 }