diff options
Diffstat (limited to '13.c')
| -rw-r--r-- | 13.c | 251 |
1 files changed, 251 insertions, 0 deletions
@@ -0,0 +1,251 @@ + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> + + +struct node { + int val_int; + struct node * val_list; + struct node * next; +}; + + +struct node list_empty = { 0, &list_empty, NULL }; + +struct node * const LIST_EMPTY = &list_empty; + + +struct node * +node_create_int(int i) +{ + struct node * n = malloc(sizeof(struct node)); + if (!n) + return NULL; + n->val_list = NULL; + n->val_int = i; + n->next = NULL; + return n; +} + + +struct node * +node_create_list(struct node * list) +{ + struct node * n = malloc(sizeof(struct node)); + if (!n) + return NULL; + n->val_list = list ? list : LIST_EMPTY; + n->val_int = 0; + n->next = NULL; + return n; +} + + +void +node_free(struct node * n) +{ + if (!n || n == LIST_EMPTY) + return; + node_free(n->val_list); + node_free(n->next); + free(n); + return; +} + + +int +node_isint(struct node const * n) +{ + return n->val_list == NULL; +} + + +int +node_islist(struct node const * n) +{ + return n->val_list != NULL; +} + + +void +node_dump(struct node * n) +{ + fputc('[', stderr); + + while (n && n != LIST_EMPTY) { + if (node_isint(n)) + fprintf(stderr, "%d", n->val_int); + else + node_dump(n->val_list); + + if (n->next) + fputc(',', stderr); + + n = n->next; + } + + fputc(']', stderr); +} + + +int +node_cmp(struct node * l, struct node * r) +{ + while (l && r) { + int ret; + + if (node_isint(l) && node_isint(r)) { + ret = l->val_int - r->val_int; + } + else if (node_isint(l)) { + struct node * tmp = node_create_list(l); + ret = node_cmp(tmp, r); + free(tmp); // Not node_free(), because we don't want to delete the contents + } + else if (node_isint(r)) { + struct node * tmp = node_create_list(r); + ret = node_cmp(l, tmp); + free(tmp); // Not node_free(), because we don't want to delete the contents + } + else if (l == LIST_EMPTY && r == LIST_EMPTY) { + return 0; + } + else if (l == LIST_EMPTY) { + return -1000; + } + else if (r == LIST_EMPTY) { + return 1000; + } + else { + ret = node_cmp(l->val_list, r->val_list); + } + + if (ret != 0) + return ret; + + l = l->next; + r = r->next; + } + + if (!l && !r) + // Lists were same length + return 0; + + return l ? 2000 : -2000; +} + + +struct node * +node_parse(char ** ppch) +{ + char * pch = *ppch; + struct node * head = NULL, * tail = NULL; + + while (*pch != '\0') { + struct node * n = NULL; + + while (isspace(*pch)) + ++pch; + + if (isdigit(*pch)) { + n = node_create_int(strtol(pch, &pch, 10)); + } + else if (*pch == '[') { + ++pch; + n = node_create_list(node_parse(&pch)); + } + else if (*pch == ']') { + *ppch = ++pch; + return head ? head : LIST_EMPTY; + } + else { + *ppch = pch; + node_free(head); + return NULL; + } + + if (head && tail) { + tail->next = n; + tail = n; + } + else { + head = tail = n; + } + + while (isspace(*pch)) + ++pch; + if (*pch == ',') + ++pch; + } + + *ppch = pch; + return head; +} + + +int +main() +{ + struct node * packets = NULL, * last = NULL, * n; + char buf[BUFSIZ]; + int index_sum = 0, i; + + while (fgets(buf, sizeof(buf), stdin)) { + char * pch; + + if (buf[0] == '\n' || buf[0] == '\0') + continue; + + pch = buf; + n = node_parse(&pch); + if (!n && pch == buf) { + fprintf(stderr, "Invalid input\n"); + node_free(packets); + return -1; + } + if (!n) // Just whitespace or whatever + continue; + if (!node_islist(n)) { + fprintf(stderr, "Got a packet that's not a list?\n"); + node_dump(n); fputc('\n', stderr); + free(n); + node_free(packets); + return -1; + } + + if (last) { + last->next = n; + last = n; + } + else { + packets = last = n; + } + } + + for (n = packets, i = 1; n != NULL && n->next != NULL; n = n->next->next, ++i) { + int j; + + if ((j = node_cmp(n, n->next)) < 0) { + index_sum += i; + } +#if 1 + node_dump(n); fputc('\n', stderr); + node_dump(n->next); fputc('\n', stderr); + fprintf(stderr, "Result: %d (%s)\n", j, j < 0 ? "yes" : "no"); +#endif + + if (j == 0) { + fprintf(stderr, "Got two identical packets?\n"); + node_dump(n); fputc('\n', stderr); + node_dump(n->next); fputc('\n', stderr); + } + } + + printf("Index sum: %d\n", index_sum); + + node_free(packets); + + return 0; +} + |