From de7bd8ddbc23a5e4751468c161e3ec7b63a3a883 Mon Sep 17 00:00:00 2001
From: Bond_009 <bond.009@outlook.com>
Date: Mon, 7 Dec 2020 14:16:23 +0100
Subject: Add day 7 part 1

---
 7/part1.c | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100644 7/part1.c

(limited to '7/part1.c')

diff --git a/7/part1.c b/7/part1.c
new file mode 100644
index 0000000..1590854
--- /dev/null
+++ b/7/part1.c
@@ -0,0 +1,158 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <malloc.h>
+#include <string.h>
+
+#define SEARCH_NAME "shiny gold"
+#define MAX_NAMES 1024
+#define MAX_SIZE 600
+#define MAX_INNER_BAGS 4
+
+struct Bag
+{
+    size_t inner_bags_size;
+    char *inner_bags[4];
+    char *bag_color;
+};
+
+char *insert_name(char **names, size_t *names_size, char *new_name)
+{
+    long long low = 0, high = *names_size;
+    while (low < high) {
+        int m = low + (high - low) / 2;
+        int c = strcmp(names[m], new_name);
+        if (c == 0) {
+            /* Name already exists,
+                return pointer to the already existsing string and free the new one.
+            */
+            free(new_name);
+            return names[m];
+        }
+        else if (c < 0) {
+            low = m + 1;
+        }
+        else {
+            high = m;
+        }
+    }
+
+    for (long long i = *names_size - 1; i >= low; i--) {
+        names[i + 1] = names[i];
+    }
+
+    (*names_size)++;
+    return names[low] = new_name;
+}
+
+void insert_name2(char **names, size_t *names_size, char *new_name)
+{
+    long long low = 0, high = *names_size;
+    while (low < high) {
+        int m = low + (high - low) / 2;
+        int c = strcmp(names[m], new_name);
+        if (c == 0) {
+            return;
+        }
+        else if (c < 0) {
+            low = m + 1;
+        }
+        else {
+            high = m;
+        }
+    }
+
+    for (long long i = *names_size - 1; i >= low; i--) {
+        names[i + 1] = names[i];
+    }
+
+    (*names_size)++;
+    names[low] = new_name;
+    return;
+}
+
+char *get_and_insert_name(char *bufstart, char *bufend, char **names, size_t *names_size)
+{
+    size_t bag_name_len = bufend - bufstart;
+    char *new_name = malloc((bag_name_len + 1) * sizeof(char));
+    memcpy(new_name, bufstart, bag_name_len);
+    new_name[bag_name_len] = 0; // null terminate string
+    return insert_name(names, names_size, new_name);
+}
+
+int bags_count(const char *filename)
+{
+    FILE *file = fopen(filename, "r");
+
+    // Include space for newline and string terminator
+    char buffer[128] = { 0 };
+
+    struct Bag *bags = malloc(MAX_SIZE * sizeof(struct Bag));
+    struct Bag *cur_bag = bags;
+    char **names = malloc(MAX_NAMES * sizeof(char *));
+
+    // Already add the name we're searching
+    char *search_name = names[0] = SEARCH_NAME;
+    size_t names_size = 1;
+
+    while (fgets(buffer, 128, file)) {
+        char *end_bag_name = strstr(buffer, " bags");
+        if (!end_bag_name) {
+            break;
+        }
+
+        char* new_name = get_and_insert_name(buffer, end_bag_name, names, &names_size);
+
+        cur_bag++;
+        cur_bag->bag_color = new_name;
+        if (strncmp(end_bag_name, " bags contain no", 16) == 0) {
+            cur_bag->inner_bags_size = 0;
+            continue;
+        }
+
+        char *string_end = strchr(end_bag_name, '.');
+        char *start_bag_name = end_bag_name + 16;
+        while ((end_bag_name = strstr(start_bag_name, " bag"))) {
+            new_name = get_and_insert_name(start_bag_name, end_bag_name, names, &names_size);
+            cur_bag->inner_bags[cur_bag->inner_bags_size++] = new_name;
+            start_bag_name = end_bag_name + (strncmp(end_bag_name, " bags", 5) ? 8 : 9);
+            if (start_bag_name > string_end) {
+                // We're outside the buffer, stop
+                break;
+            }
+        }
+    }
+
+    fclose(file);
+
+    char **outer_bags = malloc(MAX_SIZE * sizeof(char *));
+
+    // Start search with SEARCH_NAME
+    outer_bags[0] = search_name;
+    size_t outer_bags_size = 1;
+
+    size_t old_size = 0;
+    while (old_size != outer_bags_size) {
+        old_size = outer_bags_size;
+        for (size_t i = 0; i < outer_bags_size; i++) {
+            struct Bag *p = bags;
+            while (p <= cur_bag) {
+                for (size_t j = 0; j < p->inner_bags_size; j++) {
+                    if (p->inner_bags[j] == outer_bags[i]) {
+                        insert_name2(outer_bags, &outer_bags_size, p->bag_color);
+                        break;
+                    }
+                }
+
+                p++;
+            }
+        }
+    }
+
+    // Don't count SEARCH_NAME
+    return outer_bags_size - 1;
+}
+
+int main(int argc, char *argv[])
+{
+    printf("%i\n", bags_count(argv[argc - 1]));
+}
-- 
cgit v1.2.3