summaryrefslogtreecommitdiff
path: root/Advent-of-Code-2023/aoc-1/main.c
diff options
context:
space:
mode:
Diffstat (limited to 'Advent-of-Code-2023/aoc-1/main.c')
-rw-r--r--Advent-of-Code-2023/aoc-1/main.c259
1 files changed, 259 insertions, 0 deletions
diff --git a/Advent-of-Code-2023/aoc-1/main.c b/Advent-of-Code-2023/aoc-1/main.c
new file mode 100644
index 0000000..559ddab
--- /dev/null
+++ b/Advent-of-Code-2023/aoc-1/main.c
@@ -0,0 +1,259 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <stdbool.h>
+
+#define QUEUE_CAP 128
+#define CHILDREN_CAP 128
+
+#define ARR_SIZE(a) (sizeof(a)/sizeof(*a))
+
+// #define FILENAME "sample.txt"
+#define FILENAME "input.txt"
+
+// #define PART1
+#define PART2
+
+#define NUMS(X) \
+ X(1, 1, 177622) \
+ X(2, 2, 177623) \
+ X(3, 3, 177624) \
+ X(4, 4, 177625) \
+ X(5, 5, 177626) \
+ X(6, 6, 177627) \
+ X(7, 7, 177628) \
+ X(8, 8, 177629) \
+ X(9, 9, 177630) \
+
+#define STRS(X) \
+ X(one, 1, 193501607) \
+ X(two, 2, 193507359) \
+ X(three, 3, 210728981597) \
+ X(four, 4, 6385231329) \
+ X(five, 5, 6385224815) \
+ X(six, 6, 193505817) \
+ X(seven, 7, 210727692230) \
+ X(eight, 8, 210711216854) \
+ X(nine, 9, 6385512047) \
+
+#define TO_STR_ARR(s, v, h) #s,
+
+#define TO_CASE(s, v, h) \
+ case h: \
+ if(num_str[0] == 0) { \
+ num_str[0] = #v[0]; \
+ num_str[1] = #v[0]; \
+ } else { \
+ num_str[1] = #v[0]; \
+ } \
+ break;
+
+
+// https://www.cse.yorku.ca/~oz/hash.html
+unsigned long hash(char *str)
+{
+ unsigned long hash = 5381;
+ int c;
+
+ while ((c = *str++))
+ hash = ((hash << 5) + hash) + c;
+
+ return hash;
+}
+
+// https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
+typedef struct trie_node {
+ struct trie_node *parent;
+ struct trie_node *children[CHILDREN_CAP];
+
+ struct trie_node *suffix;
+ bool end;
+} trie;
+
+trie *trie_init(char **dictionary, size_t nwords);
+void trie_search(trie *root, char *str, void (*callback)(char *str, size_t len));
+void trie_free(trie *root);
+void trie_print(trie *root);
+
+size_t sum = 0;
+char num_str[3] = {0};
+
+void handle_match(char *str, size_t len)
+{
+ char s[len+1]; s[len] = '\0';
+ memcpy(s, str, len);
+
+ switch(hash(s)) {
+ NUMS(TO_CASE)
+#ifdef PART2
+ STRS(TO_CASE)
+#endif
+ default:
+ fprintf(stderr, "bad hash: %lu (of str %s)", hash(s), s);
+ }
+}
+
+int main(void)
+{
+ char *dictionary[] = {
+ NUMS(TO_STR_ARR)
+#ifdef PART2
+ STRS(TO_STR_ARR)
+#endif
+ };
+
+ trie *root = trie_init(dictionary, ARR_SIZE(dictionary));
+ trie_print(root);
+
+ FILE *fp = fopen(FILENAME, "r");
+ if(!fp) {
+ perror("fopen: failed");
+ return 1;
+ }
+
+ char line[256];
+ while(fgets(line, sizeof(line), fp)) {
+ trie_search(root, line, handle_match);
+ sum += atoi(num_str);
+ num_str[0] = 0; num_str[1] = 0;
+ }
+
+ fclose(fp);
+
+ printf("Sum: %ld\n", sum);
+
+ trie_free(root);
+ return 0;
+}
+
+static trie *trie_find_suffix(trie *node, size_t idx);
+static void trie_set_suffix(trie *node, size_t idx);
+
+static void trie_traverse(trie *parent, void (*callback)(trie *node, size_t idx));
+static void trie_add_pattern(trie *node, char *pattern);
+
+trie *trie_init(char **patterns, size_t nwords)
+{
+ trie *root = malloc(sizeof(trie));
+ memset(root, 0, sizeof(trie));
+
+ // generate the basic trie
+ for(size_t i = 0; i < nwords; i++) {
+ trie_add_pattern(root, patterns[i]);
+ }
+
+ // calculate suffix links
+ trie_traverse(root, trie_set_suffix);
+
+ return root;
+}
+
+void trie_search(trie *root, char *str, void (*callback)(char *str, size_t len))
+{
+ trie *node = root;
+ for(size_t i = 0; i < strlen(str)+1; i++) {
+ if(node->children[(size_t)str[i]] != NULL) {
+ node = node->children[(size_t)str[i]];
+ continue;
+ }
+
+ if(node->end) {
+ int len = 0; trie *tmp = node;
+ while(tmp->parent != NULL) {
+ tmp = tmp->parent;
+ len++;
+ }
+ callback(&str[i-len], len);
+ }
+
+ if(node->suffix == NULL) continue;
+
+ node = node->suffix;
+ i--; continue;
+ }
+}
+
+void trie_free(trie *root)
+{
+ for(int i = 0; i < CHILDREN_CAP; i++)
+ if(root->children[i] != NULL) {
+ trie_free(root->children[i]);
+ }
+
+ free(root);
+}
+
+static void trie_print_child(trie *root, trie *node, size_t depth)
+{
+ for(int i = 0; i < CHILDREN_CAP; i++) {
+ if(node->children[i] != NULL) {
+ for(size_t i = 0; i < depth; i++) printf(" ");
+ printf("%c (%p) -> (%p) %s\n", i, (void *)node->children[i],
+ (void *)((node->children[i]->suffix == root) ?
+ 0 : node->children[i]->suffix),
+ (node->children[i]->end ? "END" : ""));
+ trie_print_child(root, node->children[i], depth+2);
+ }
+ }
+}
+
+void trie_print(trie *root)
+{
+ printf("ROOT (%p)\n", (void *)root);
+ trie_print_child(root, root, 2);
+}
+
+static trie *trie_find_suffix(trie *node, size_t idx)
+{
+ if(node->suffix == NULL) return node; // root
+
+ if(node->suffix->children[idx] != NULL) {
+ return node->suffix->children[idx];
+ } else {
+ return trie_find_suffix(node->suffix, idx);
+ }
+}
+
+
+static void trie_set_suffix(trie *node, size_t idx)
+{
+ node->suffix = trie_find_suffix(node->parent, idx);
+}
+
+static void trie_traverse(trie *root, void (*callback)(trie *node, size_t idx))
+{
+ // breadth-first traversal
+
+ trie *queue[QUEUE_CAP] = {0};
+ size_t queue_start = 0, queue_end = 0;
+
+ queue[queue_end++] = root;
+
+ while(queue_start != queue_end) {
+ trie *parent = queue[queue_start++ % QUEUE_CAP];
+ for(size_t i = 0; i < CHILDREN_CAP; i++)
+ if(parent->children[i] != NULL) {
+ callback(parent->children[i], i);
+ queue[queue_end++ % QUEUE_CAP] = parent->children[i];
+ }
+ }
+}
+
+static void trie_add_pattern(trie *node, char *pattern)
+{
+ if(pattern[0] == '\0') {
+ node->end = true;
+ return;
+ }
+
+ if(node->children[(size_t)pattern[0]] == NULL) {
+ trie *child = malloc(sizeof(trie));
+ memset(child, 0, sizeof(trie));
+
+ child->parent = node;
+ node->children[(size_t)pattern[0]] = child;
+ }
+
+ trie_add_pattern(node->children[(size_t)pattern[0]], &pattern[1]);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-23 02:40:25 +0000