finish!

1 files changed, 154 insertions, 0 deletions

diff --git a/11/part2.c b/11/part2.c
new file mode 100644
index 0000000..edc67ba
--- /dev/null
+++ b/11/part2.c
@@ -0,0 +1,154 @@
+#include <stdint.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <errno.h>
+#include <ctype.h>
+
+#include <algds/str.h>
+#include <algds/vec.h>
+#include <algds/hash_table.h>
+#include <algds/mmhash.h>
+#include <time.h>
+
+#define PANIC do { \
+    fprintf(stderr, "panic at %s:%d\n", __FILE__, __LINE__); \
+    abort(); \
+} while (0)
+
+void expect_char(char e) {
+    int c = fpeek(stdin);
+    if (c != e) {
+        PANIC;
+    }
+    fgetc(stdin);
+}
+
+typedef struct {
+    char name[3];
+} Tag;
+
+void Tag_show(Tag self, FILE *fp) {
+    printf("%c%c%c", self.name[0], self.name[1], self.name[2]);
+}
+
+VECTOR_DEF(Tag)
+VECTOR_IMPL(Tag)
+
+uint64_t Tag_hash(Tag self) {
+    return mmhash(self.name, 3, 0);
+}
+
+bool Tag_eq(Tag a, Tag b) {    
+    return a.name[0] == b.name[0]
+        && a.name[1] == b.name[1]
+        && a.name[2] == b.name[2];
+}
+
+HASH_TABLE_DEF(Tag, TagVector);
+HASH_TABLE_IMPL(Tag, TagVector);
+
+Tag parse_tag() {
+    Tag t;
+    t.name[0] = getchar();
+    t.name[1] = getchar();
+    t.name[2] = getchar();
+    return t;
+}
+
+Tag Tag_new(const char *s) {
+    Tag t;
+    t.name[0] = s[0];
+    t.name[1] = s[1];
+    t.name[2] = s[2];
+    return t;
+}
+
+Tag2TagVectorHashTable dag;
+
+typedef struct {
+    Tag t;
+    int fft;
+    int dac;
+} CacheEntry;
+
+uint64_t CacheEntry_hash(CacheEntry self) {
+    uint64_t ret = Tag_hash(self.t);
+    ret = mmhash(&self.dac, sizeof(int), ret);
+    return mmhash(&self.fft, sizeof(int), ret);
+}
+
+bool CacheEntry_eq(CacheEntry a, CacheEntry b) {    
+    return Tag_eq(a.t, b.t)
+        && a.dac == b.dac
+        && a.fft == b.fft;
+}
+
+HASH_TABLE_DEF(CacheEntry, Long);
+HASH_TABLE_IMPL(CacheEntry, Long);
+
+CacheEntry2LongHashTable cache;
+
+long search(Tag src, int fft, int dac) {
+    if (Tag_eq(src, Tag_new("out"))) {
+        return fft * dac;
+    }
+    if (Tag_eq(src, Tag_new("fft"))) {
+        fft = 1;
+    }
+    if (Tag_eq(src, Tag_new("dac"))) {
+        dac = 1;
+    }
+    CacheEntry2LongHashTableIter cache_it =
+        CacheEntry2LongHashTable_find(
+            &cache,
+            (CacheEntry){.t = src, .dac = dac, .fft = fft});
+    if (cache_it != NULL) {
+        return cache_it->val;
+    }
+    long res = 0;
+    Tag2TagVectorHashTableIter dag_it = Tag2TagVectorHashTable_find(&dag, src);
+    TagVector nexthops = dag_it->val;
+    for (int i = 0; i < nexthops.size; i++) {
+        res += search(nexthops.buffer[i], fft, dac);
+    }
+    CacheEntry2LongHashTable_insert(&cache, (CacheEntry){.t = src, .dac = dac, .fft = fft}, res);
+    return res;
+}
+
+int main() {
+    Tag2TagVectorHashTable_init(&dag);
+    CacheEntry2LongHashTable_init(&cache);
+    while (1) {
+        int c = fpeek(stdin);
+        if (isalpha(c)) {
+            Tag t = parse_tag();
+            expect_char(':');
+            expect_char(' ');
+            TagVector next;
+            TagVector_init(&next);
+            while (1) {
+                int c = fpeek(stdin);
+                if(!isalpha(c)) {
+                    break;
+                }
+                TagVector_push_back(&next, parse_tag());
+                c = fpeek(stdin);
+                if (c == ' ') {
+                    getchar();
+                }
+            }
+            int c = fpeek(stdin);
+            if (c == '\n') {
+                getchar();
+            }
+            Tag2TagVectorHashTable_insert(&dag, t, next);
+        } else {
+            break;
+        }
+    }
+    long ret = search(Tag_new("svr"), 0, 0);
+    printf("%ld\n", ret);
+    return 0;
+}
\ No newline at end of file