day 12 part two wrong, day 13 done

[advent21.git] / 12b.c

diff --git a/12b.c b/12b.c
new file mode 100644 (file)
index 0000000..5be7962
--- /dev/null
+++ b/12b.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include <ctype.h>
+#include <stdbool.h>
+
+#include <uthash.h>
+
+struct conn {
+       char key[10];
+       struct node *node;
+       UT_hash_handle hh;
+};
+struct node {
+       char key[10];
+       struct conn *connections;
+       UT_hash_handle hh;
+};
+
+struct node *get_or_create(struct node **graph, char name[])
+{
+       struct node *n;
+       HASH_FIND_STR(*graph, name, n);
+       if (n) {
+               return n;
+       } else {
+               n = malloc(sizeof(struct node));
+               strcpy(n->key, name);
+               n->connections = NULL;
+               HASH_ADD_STR(*graph, key, n);
+       }
+       return n;
+}
+
+void add_connection(struct node *from, struct node *to)
+{
+       //to
+       struct conn *c = malloc(sizeof(struct conn));
+       strcpy(c->key, to->key);
+       c->node = to;
+       HASH_ADD_STR(from->connections, key, c);
+       //fro
+       c = malloc(sizeof(struct conn));
+       strcpy(c->key, from->key);
+       c->node = from;
+       HASH_ADD_STR(to->connections, key, c);
+}
+
+char **copy_visited(char **visited, int nvisited)
+{
+       char **r = malloc(sizeof(char *)*nvisited);
+       memcpy(r, visited, sizeof(char *)*nvisited);
+       return r;
+}
+
+int find_end(struct node *node, char **visited, int nvisited, bool twice)
+{
+       if (strcmp(node->key, "end") == 0)
+               return 1;
+       if (islower(node->key[0])) {
+               for (int i = 0; i<nvisited; i++)
+                       if (strcmp(node->key, visited[i]) == 0)
+                               return 0;
+               visited = realloc(visited, sizeof(char *)*(nvisited+1));
+               visited[nvisited++] = node->key;
+       }
+       int r = 0;
+       for (struct conn *c = node->connections; c != NULL; c = c->hh.next) {
+               if (twice && strcmp(node->key, "start") != 0 && islower(node->key[0]))
+                       r += find_end(c->node, copy_visited(visited, nvisited-1), nvisited-1, false);
+               r += find_end(c->node, copy_visited(visited, nvisited), nvisited, twice);
+       }
+       free(visited);
+       return r;
+}
+
+int main()
+{
+       struct node *graph = NULL;
+       char *buf = NULL;
+       size_t len = 0;
+       while (getline(&buf, &len, stdin) != -1) {
+               char *toname = strchr(buf, '-');
+               *(toname++)= '\0';
+               if (toname[strlen(toname)-1] == '\n')
+                       toname[strlen(toname)-1] = '\0';
+               add_connection(get_or_create(&graph, buf),
+                              get_or_create(&graph, toname));
+       }
+
+       printf("%d\n", find_end(get_or_create(&graph, "start"), NULL, 0, true));
+}