solve 22HEADmaster

1 files changed, 150 insertions, 0 deletions

diff --git a/0022/main.c b/0022/main.c
new file mode 100644
index 0000000..760c7d7
--- /dev/null
+++ b/0022/main.c
@@ -0,0 +1,150 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdbool.h>
+
+#define VECTOR_DEF(T) \
+    typedef struct { \
+        T* buffer; \
+        int size; \
+        int cap; \
+    } T##Vector; \
+    \
+    void T##Vector_init(T##Vector *self); \
+    void T##Vector_push_back(T##Vector *self, T elem); \
+    void T##Vector_insert_before(T##Vector *self, int n, T elem); \
+    void T##Vector_pop(T##Vector *self); \
+    bool T##Vector_empty(T##Vector *self); \
+    void T##Vector_remove(T##Vector *self, size_t n); \
+    size_t T##Vector_len(T##Vector *self); \
+    T* T##Vector_begin(T##Vector *self); \
+    T* T##Vector_last(T##Vector *self); \
+    T* T##Vector_end(T##Vector *self); \
+    T* T##Vector_ref(T##Vector *self, size_t n); \
+    void T##Vector_swap(T##Vector *self, int i, int j); \
+    T##Vector T##Vector_move(T##Vector *self); \
+    void T##Vector_show(T##Vector *self, FILE* fp); \
+    void T##Vector_free(T##Vector *self);
+
+#define VECTOR_IMPL(T) \
+    void T##Vector_init(T##Vector *self) { \
+        self->buffer = (T*)malloc(sizeof(T) * 16); \
+        self->cap = 16; \
+        self->size = 0; \
+    } \
+    \
+    void T##Vector_push_back(T##Vector *self, T elem) { \
+        if (self->size + 1 > self->cap) { \
+            self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \
+            self->cap *= 2; \
+        } \
+        self->buffer[self->size] = elem; \
+        self->size += 1; \
+    } \
+    void T##Vector_insert_before(T##Vector *self, int n, T elem) { \
+        if (n < 0 || n > self->size) { \
+            return; \
+        } \
+        if (self->size + 1 > self->cap) { \
+            self->buffer = malloc(sizeof(T) * self->cap * 2); \
+            self->cap *= 2; \
+        } \
+        if (n != self->size) { \
+            memmove(self->buffer + n + 1, \
+                    self->buffer + n, \
+                    sizeof(T) * (self->size - n)); \
+            self->buffer[n] = elem; \
+            self->size += 1; \
+        } \
+    } \
+    void T##Vector_pop(T##Vector *self) { \
+        self->size -= 1; \
+    } \
+    void T##Vector_remove(T##Vector *self, size_t n) { \
+        if (n < 0 || n >= self->size) return; \
+        memmove(self->buffer + n, \
+                self->buffer + n + 1, \
+                sizeof(T) * self->size - n - 1); \
+        self->size -= 1; \
+    } \
+    T* T##Vector_begin(T##Vector *self) { return self->buffer; } \
+    bool T##Vector_empty(T##Vector *self) { return self->size == 0; } \
+    T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \
+    T* T##Vector_last(T##Vector *self) { return self->buffer + self->size - 1; } \
+    T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \
+    void T##Vector_swap(T##Vector *self, int i, int j) { \
+        T buf; \
+        memcpy(&buf, self->buffer + i, sizeof(T)); \
+        memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \
+        memcpy(self->buffer + j, &buf, sizeof(T)); \
+    } \
+    T##Vector T##Vector_move(T##Vector *self) { \
+        T##Vector dup = *self; \
+        self->buffer = NULL; \
+        self->size = 0; \
+        self->cap = 0; \
+        return dup; \
+    } \
+    void T##Vector_show(T##Vector *self, FILE* fp) { \
+        fprintf(fp, "["); \
+        for (int i = 0; i < self->size-1; i++) { \
+            T##_show(&self->buffer[i], fp); \
+            fprintf(fp, ", "); \
+        } \
+        if (self->size > 0) { \
+            T##_show(&self->buffer[self->size - 1], fp); \
+        } \
+        fprintf(fp, "]"); \
+    } \
+    size_t T##Vector_len(T##Vector *self) { return self->size; } \
+    void T##Vector_free(T##Vector *self) { free(self->buffer); }
+
+typedef char *String;
+
+void String_show(String *s, FILE *fp) {
+    fprintf(fp, "%s", *s);
+}
+
+VECTOR_DEF(String);
+VECTOR_IMPL(String);
+
+char *append(char *s, char c) {
+    int len = strlen(s);
+    char *ns = malloc(len + 2);
+    strcpy(ns, s);
+    ns[len] = c;
+    ns[len + 1] = '\0';
+    return ns;
+}
+
+void gen_impl(StringVector *res, char* current, int n, int unclosed, int finished) {
+    if (unclosed == 0 && finished == n) {
+        printf("add: %s\n", current);
+        StringVector_push_back(res, current);
+        StringVector_show(res, stdout);
+        return;
+    }
+    if (unclosed > 0) {
+        gen_impl(res, append(current, ')'), n, unclosed - 1, finished + 1);
+    }
+    if (unclosed + finished < n) {
+        gen_impl(res, append(current, '('), n, unclosed + 1, finished);
+    }
+    free(current);
+}
+
+char** generateParenthesis(int n, int* returnSize) {
+    StringVector result;
+    StringVector_init(&result);
+    char *empty = malloc(1);
+    empty[0] = '\0';
+    gen_impl(&result, empty, n, 0, 0);
+    *returnSize = StringVector_len(&result);
+    return result.buffer;
+}
+
+int main() {
+    int size;
+    generateParenthesis(3, &size);
+    printf("\n");
+}
\ No newline at end of file