aocc22

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

common.c (2837B)

      1 #include "common.h"
      2 
      3 #define ALPHABET_SIZE ('z' - 'a' + 1)
      4 
      5 size_t monkindex(char *name) {
      6   size_t r = 0;
      7 
      8   size_t i;
      9   for (i = 0; i < 4; i++) {
     10     r *= ALPHABET_SIZE;
     11     r += (size_t)(name[i] - 'a');
     12   }
     13 
     14   return r;
     15 }
     16 
     17 monki *parse(char **lines, size_t nlines) {
     18   monki *m = malloc(ALPHABET_SIZE * ALPHABET_SIZE * ALPHABET_SIZE *
     19                     ALPHABET_SIZE * sizeof(*m));
     20 
     21   size_t i;
     22   for (i = 0; i < nlines; i++) {
     23     char *line = lines[i];
     24     size_t idx = monkindex(line);
     25     uint64_t tmp;
     26     if (sread_next_u64(&tmp, line) != NULL) {
     27       m[idx].v = (int64_t)tmp;
     28       m[idx].op = '\0';
     29       m[idx].opl = SIZE_MAX;
     30       m[idx].opl = SIZE_MAX;
     31     } else {
     32       m[idx].v = 0;
     33       m[idx].op = line[11];
     34       m[idx].opl = monkindex(&line[6]);
     35       m[idx].opr = monkindex(&line[13]);
     36     }
     37   }
     38 
     39   return m;
     40 }
     41 
     42 size_t left_tree_root(const monki *m) {
     43   size_t ri = monkindex("root");
     44   return m[ri].opl;
     45 }
     46 
     47 size_t right_tree_root(const monki *m) {
     48   size_t ri = monkindex("root");
     49   return m[ri].opr;
     50 }
     51 
     52 int humn_subtree(const size_t start, const monki *m) {
     53   if (start == monkindex("humn"))
     54     return 1;
     55   if (m[start].op == '\0')
     56     return 0;
     57   return humn_subtree(m[start].opl, m) || humn_subtree(m[start].opr, m);
     58 }
     59 
     60 int64_t mcompute(const size_t start, const monki *m) {
     61   if (m[start].op == '\0') {
     62     return m[start].v;
     63   } else {
     64     int64_t opera = mcompute(m[start].opl, m);
     65     int64_t operb = mcompute(m[start].opr, m);
     66     switch (m[start].op) {
     67     case '+':
     68       return opera + operb;
     69     case '-':
     70       return opera - operb;
     71     case '*':
     72       return opera * operb;
     73     case '/':
     74       return opera / operb;
     75     default:
     76       fprintf(stderr, "ERROR! Bad operation %c\n", m[start].op);
     77       exit(1);
     78     }
     79   }
     80 }
     81 
     82 int64_t reverse(const size_t start, const monki *m, const int64_t desired) {
     83   if (start == monkindex("humn"))
     84     return desired;
     85 
     86   if (m[start].op == '\0') {
     87     fprintf(stderr, "ERROR! Reverse searching in leaf %zu\n", start);
     88     exit(1);
     89   }
     90 
     91   size_t h_subtree = m[start].opl;
     92   size_t n_subtree = m[start].opr;
     93   int humn_left = 1;
     94   if (!humn_subtree(h_subtree, m)) {
     95     h_subtree = m[start].opr;
     96     n_subtree = m[start].opl;
     97     humn_left = 0;
     98   }
     99 
    100   int64_t opv = mcompute(n_subtree, m);
    101 
    102   switch (m[start].op) {
    103   case '+':
    104     return reverse(h_subtree, m, desired - opv);
    105   case '*':
    106     return reverse(h_subtree, m, desired / opv);
    107   case '/':
    108     if (humn_left) {
    109       return reverse(h_subtree, m, desired * opv);
    110     }
    111     return reverse(h_subtree, m, opv / desired);
    112   case '-':
    113     if (humn_left) {
    114       return reverse(h_subtree, m, desired + opv);
    115     }
    116     return reverse(h_subtree, m, opv - desired);
    117   default:
    118     fprintf(stderr, "ERROR! Reversing with unknown operation %c\n",
    119             m[start].op);
    120     exit(1);
    121   }
    122 
    123   return INT64_MAX;
    124 }