summaryrefslogtreecommitdiff
path: root/7/part2.c
diff options
context:
space:
mode:
Diffstat (limited to '7/part2.c')
-rw-r--r--7/part2.c129
1 files changed, 0 insertions, 129 deletions
diff --git a/7/part2.c b/7/part2.c
deleted file mode 100644
index f4214f5..0000000
--- a/7/part2.c
+++ /dev/null
@@ -1,129 +0,0 @@
-#include <stdio.h>
-#include <stdint.h>
-#include <stdlib.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[MAX_INNER_BAGS];
- int inner_bags_count[MAX_INNER_BAGS];
- 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;
-}
-
-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);
-}
-
-size_t get_num_bags(struct Bag *bags, size_t bags_size, char *bag_color)
-{
- for (size_t i = 0; i < bags_size; i++) {
- if (bags[i].bag_color == bag_color) {
- struct Bag bag = bags[i];
- size_t total = 1;
- for (size_t j = 0; j < bag.inner_bags_size; j++) {
- total += get_num_bags(bags, bags_size, bag.inner_bags[j]) * bag.inner_bags_count[j];
- }
-
- return total;
- }
- }
-
- return 0;
-}
-
-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 + 14;
- while ((end_bag_name = strstr(start_bag_name, " bag"))) {
- int num_bags = atoi(start_bag_name);
- start_bag_name += 2;
- 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;
- cur_bag->inner_bags_count[cur_bag->inner_bags_size++] = num_bags;
- start_bag_name = end_bag_name + (strncmp(end_bag_name, " bags", 5) ? 6 : 7);
- if (start_bag_name > string_end) {
- // We're outside the buffer, stop
- break;
- }
- }
- }
-
- fclose(file);
-
- return get_num_bags(bags, cur_bag - bags + 1, search_name) - 1;
-}
-
-int main(int argc, char *argv[])
-{
- printf("%i\n", bags_count(argv[argc - 1]));
-}