1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#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]));
}
|
