diff options
Diffstat (limited to '11')
| -rw-r--r-- | 11/part2.c | 154 |
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 |