add aoc 2022

10 files changed, 898 insertions, 0 deletions

diff --git a/advent-of-code/2022/lib/crc32.c b/advent-of-code/2022/lib/crc32.c
new file mode 100644
index 0000000..c97a971
--- /dev/null
+++ b/advent-of-code/2022/lib/crc32.c
@@ -0,0 +1,55 @@
+#include "crc32.h"
+
+const uint32_t crc32_tab[] = {
+    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
+    0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
+    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
+    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
+    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
+    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
+    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
+    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
+    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
+    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
+    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
+    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
+    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
+    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
+    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
+    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
+    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
+    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
+    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
+    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
+    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
+    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
+};
+
+uint32_t crc32(uint32_t crc, void *buf, int size){
+    uint8_t *p = buf;
+    crc = ~crc;
+    while (size--)
+        crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
+    return ~crc;
+}
diff --git a/advent-of-code/2022/lib/crc32.h b/advent-of-code/2022/lib/crc32.h
new file mode 100644
index 0000000..86587f1
--- /dev/null
+++ b/advent-of-code/2022/lib/crc32.h
@@ -0,0 +1,9 @@
+#ifndef CRC32_H_
+#define CRC32_H_
+
+#include <stdint.h>
+
+uint32_t crc32(uint32_t r, void* buf, int size);
+
+#endif
+
diff --git a/advent-of-code/2022/lib/htable.c b/advent-of-code/2022/lib/htable.c
new file mode 100644
index 0000000..d4b90a5
--- /dev/null
+++ b/advent-of-code/2022/lib/htable.c
@@ -0,0 +1,106 @@
+#include "htable.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#define HTFL_NUL 0
+#define HTFL_VAL 1
+#define HTFL_DEL 2
+
+static void* htable_end(HTable *ht) {
+    return ht->buf + ht->cap * (ht->elemsz + 1);
+}
+
+static void rebuild(HTable *ht) {
+    HTable newht;
+    htable_init(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq);
+    void *iter = htable_begin(ht);
+    while (iter != NULL) {
+        htable_insert(&newht, iter);
+        iter = htable_next(ht, iter);
+    }
+    free(ht->buf);
+    *ht = newht;
+}
+
+static uint8_t getflag(void *iter) {
+    return *(uint8_t*)(iter - 1);
+}
+
+static void setflag(void *iter, uint8_t flag) {
+    *(uint8_t *)(iter - 1) = flag;
+}
+
+void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void*),
+                 bool (*eq)(void*, void*)) {
+    if (cap < 16) cap = 16;
+    ht->buf = malloc(cap * (elemsz + 1));
+    memset(ht->buf, 0, cap * (elemsz + 1));
+    ht->size = 0;
+    ht->cap = cap;
+    ht->taken = 0;
+    ht->begin = NULL;
+    ht->elemsz = elemsz;
+    ht->hash = hash;
+    ht->eq = eq;
+}
+
+bool htable_insert(HTable *ht, void* elem) {
+    if (ht->taken + 1 > ht->cap / 2) {
+        rebuild(ht);
+    }
+    ht->taken++;
+    ht->size++;
+    int hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return false;
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    memcpy(pos, elem, ht->elemsz);
+    setflag(pos, HTFL_VAL);
+    if (pos < ht->begin || ht->begin == NULL) {
+        ht->begin = pos;
+    }
+    return true;
+}
+
+void htable_del(HTable *ht, void* iter) {
+    ht->size--;
+    setflag(iter, HTFL_DEL);
+    if (iter == ht->begin) {
+        ht->begin = htable_next(ht, iter);
+    }
+}
+
+void* htable_find(HTable *ht, void* elem) {
+    int hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return pos;
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    return NULL;
+}
+
+void* htable_begin(HTable *ht) {
+    return ht->begin;
+}
+
+void* htable_next(HTable *ht, void *iter) {
+    void *pos = iter;
+    do {
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { 
+            return NULL;
+        }
+    } while (getflag(pos) != HTFL_VAL);
+    return pos;
+}
+
diff --git a/advent-of-code/2022/lib/htable.h b/advent-of-code/2022/lib/htable.h
new file mode 100644
index 0000000..3bde74f
--- /dev/null
+++ b/advent-of-code/2022/lib/htable.h
@@ -0,0 +1,29 @@
+#ifndef HTABLE_H_
+#define HTABLE_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+typedef struct {
+    void *buf;
+    int size;
+    int cap;
+    int taken;
+    void* begin;
+    int elemsz;
+    uint32_t (*hash)(void*);
+    bool (*eq)(void*, void*);
+} HTable;
+
+void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void*),
+                 bool (*eq)(void*, void*));
+bool htable_insert(HTable *ht, void* elem);
+void htable_del(HTable *ht, void* iter);
+
+// return a iterator
+void* htable_find(HTable *ht, void* elem);
+void* htable_begin(HTable *ht);
+void* htable_next(HTable *ht, void *iter);
+
+#endif
+
diff --git a/advent-of-code/2022/lib/pque.c b/advent-of-code/2022/lib/pque.c
new file mode 100644
index 0000000..0a9dbc0
--- /dev/null
+++ b/advent-of-code/2022/lib/pque.c
@@ -0,0 +1,72 @@
+#include "pque.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+void pq_init(PQue *pq, int cap, int elem_sz, int (*cmp)(void*, void*)) {
+    pq->cap = cap;
+    pq->size = 0;
+    pq->elemsz = elem_sz;
+    pq->cmp = cmp;
+    pq->buf = malloc(cap * elem_sz);
+}
+
+static void swap(PQue *pq, int a, int b) {
+    char buf[pq->elemsz];
+    void *tmp = buf;
+    int elemsz = pq->elemsz;
+    memcpy(tmp, pq->buf + a*elemsz, elemsz);
+    memcpy(pq->buf + a*elemsz, pq->buf + b*elemsz, elemsz);
+    memcpy(pq->buf + b*elemsz, tmp, elemsz);
+}
+
+static int cmp(PQue *pq, int a, int b) {
+    return pq->cmp(pq->buf + a*pq->elemsz, pq->buf + b*pq->elemsz);
+}
+
+void pq_push(PQue *pq, void *elem) {
+    if (pq->size + 1 > pq->cap) {
+        pq->buf = realloc(pq->buf, 2 * pq->cap * pq->elemsz);
+        pq->cap *= 2;
+    }
+    memcpy(pq->buf + pq->size*pq->elemsz, elem, pq->elemsz);
+    pq->size++;
+    if (pq->size == 0) {
+        return;
+    }
+    int i = pq->size - 1;
+    while (i > 0 && cmp(pq, i, i/2) > 0) {
+        swap(pq, i, i/2);
+        i /= 2;
+    }
+}
+
+static void heapify(PQue *pq, int idx) {
+    int left, right, largest;
+    left = 2 * idx +1;
+    right = 2 * idx + 2;
+    if (left < pq->size && cmp(pq, left, idx) > 0) {
+        largest = left;
+    } else {
+        largest = idx;
+    }
+    if (right < pq->size && cmp(pq, right, largest) > 0) {
+        largest = right;
+    }
+    if (largest != idx) {
+        swap(pq, largest, idx);
+        heapify(pq, largest);
+    }
+}
+
+void pq_pop(PQue *pq) {
+    if (pq->size == 0) return;
+    memcpy(pq->buf, pq->buf+(pq->size - 1)*pq->elemsz, pq->elemsz);
+    pq->size -= 1;
+    heapify(pq, 0);
+}
+
+void* pq_top(PQue *pq) {
+    if (pq->size == 0) return NULL;
+    return pq->buf;
+}
diff --git a/advent-of-code/2022/lib/pque.h b/advent-of-code/2022/lib/pque.h
new file mode 100644
index 0000000..0d86560
--- /dev/null
+++ b/advent-of-code/2022/lib/pque.h
@@ -0,0 +1,18 @@
+#ifndef PQUEUE_H_
+#define PQUEUE_H_
+
+typedef struct {
+    void *buf;
+    int elemsz;
+    int cap;
+    int size;
+    int (*cmp)(void*, void*);
+} PQue;
+
+void pq_init(PQue *pq, int cap, int elemsz, int (*cmp)(void*, void*));
+void pq_push(PQue *pq, void *elem);
+void pq_pop(PQue *pq);
+void* pq_top();
+
+#endif
+
diff --git a/advent-of-code/2022/lib/rbtree.c b/advent-of-code/2022/lib/rbtree.c
new file mode 100644
index 0000000..25a951b
--- /dev/null
+++ b/advent-of-code/2022/lib/rbtree.c
@@ -0,0 +1,396 @@
+/*	$OpenBSD: tree.h,v 1.30 2020/10/10 18:03:41 otto Exp $	*/
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "rbtree.h"
+
+#define RED   1
+#define BLACK 0
+
+static struct rbnode *rbtree_minmax(struct rbtree *, int);
+void* rbtree_min(struct rbtree *head) {
+    return rbtree_minmax(head, -1);
+}
+void* rbtree_max(struct rbtree *head) {
+    return rbtree_minmax(head, 1);
+}
+
+void* rbtree_left(void *node) {
+    struct rbnode *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_left;
+}
+void* rbtree_right(void *node) {
+    struct rbnode *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_right;
+}
+void* rbtree_parent(void *node) {
+    struct rbnode *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_parent;
+}
+
+static void augment(struct rbtree * head, struct rbnode *elm) {
+    if (head->augment != NULL) head->augment(elm);
+}
+
+static void rbtree_insert_color(struct rbtree *head, struct rbnode *elm);
+static void rbtree_remove_color(struct rbtree *head, struct rbnode *parent,
+                                struct rbnode *elm);
+
+static void rotate_left(struct rbtree *head, struct rbnode *elm) {
+    struct rbnode *tmp = elm->entry.rbe_right;
+    if ((elm->entry.rbe_right = tmp->entry.rbe_left)) {
+        tmp->entry.rbe_left->entry.rbe_parent = elm;
+    }
+    augment(head, elm);
+    if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
+        if (elm == elm->entry.rbe_parent->entry.rbe_left)
+          elm->entry.rbe_parent->entry.rbe_left = tmp;
+        else
+          elm->entry.rbe_parent->entry.rbe_right = tmp;
+    } else {
+        head->rbh_root = tmp;
+    }
+    tmp->entry.rbe_left = elm;
+    elm->entry.rbe_parent = tmp;
+    augment(head, tmp);
+    if (tmp->entry.rbe_parent) {
+        augment(head, tmp->entry.rbe_parent);
+    }
+}
+
+static void rotate_right(struct rbtree *head, struct rbnode *elm) {
+    struct rbnode *tmp = elm->entry.rbe_left;
+    if ((elm->entry.rbe_left = tmp->entry.rbe_right)) {
+        tmp->entry.rbe_right->entry.rbe_parent = elm;
+    }
+    augment(head, elm);
+    if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
+        if (elm == elm->entry.rbe_parent->entry.rbe_left)
+          elm->entry.rbe_parent->entry.rbe_left = tmp;
+        else
+          elm->entry.rbe_parent->entry.rbe_right = tmp;
+    } else {
+        head->rbh_root = tmp;
+    }
+    tmp->entry.rbe_right = elm;
+    elm->entry.rbe_parent = tmp;
+    augment(head, tmp);
+    if (tmp->entry.rbe_parent) {
+        augment(head, tmp->entry.rbe_parent);
+    }
+}
+
+static void rbtree_insert_color(struct rbtree *head, struct rbnode *elm) {
+  struct rbnode *parent, *gparent, *tmp;
+  while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) {
+    gparent = parent->entry.rbe_parent;
+    if (parent == gparent->entry.rbe_left) {
+      tmp = gparent->entry.rbe_right;
+      if (tmp && tmp->entry.rbe_color == 1) {
+        tmp->entry.rbe_color = BLACK;
+        parent->entry.rbe_color = BLACK;
+        gparent->entry.rbe_color = RED;
+        elm = gparent;
+        continue;
+      }
+      if (parent->entry.rbe_right == elm) {
+        rotate_left(head, parent);
+        tmp = parent;
+        parent = elm;
+        elm = tmp;
+      }
+      parent->entry.rbe_color = BLACK;
+      gparent->entry.rbe_color = RED;
+      rotate_right(head, gparent);
+    } else {
+      tmp = gparent->entry.rbe_left;
+      if (tmp && tmp->entry.rbe_color == 1) {
+        tmp->entry.rbe_color = BLACK;
+        parent->entry.rbe_color = BLACK;
+        gparent->entry.rbe_color = RED;;
+        elm = gparent;
+        continue;
+      }
+      if (parent->entry.rbe_left == elm) {
+        rotate_right(head, parent);
+        tmp = parent;
+        parent = elm;
+        elm = tmp;
+      }
+      parent->entry.rbe_color = BLACK;
+      gparent->entry.rbe_color = RED;
+      rotate_left(head, gparent);
+    }
+  }
+  head->rbh_root->entry.rbe_color = BLACK;
+}
+
+static void rbtree_remove_color(struct rbtree *head, struct rbnode *parent,
+                            struct rbnode *elm) {
+  struct rbnode *tmp;
+  while ((elm == NULL || elm->entry.rbe_color == 0) &&
+         elm != head->rbh_root) {
+    if (parent->entry.rbe_left == elm) {
+      tmp = parent->entry.rbe_right;
+      if (tmp->entry.rbe_color == 1) {
+        tmp->entry.rbe_color = BLACK;
+        parent->entry.rbe_color = RED;
+        rotate_left(head, parent);
+        tmp = parent->entry.rbe_right;
+      }
+      if ((tmp->entry.rbe_left == NULL ||
+           tmp->entry.rbe_left->entry.rbe_color == 0) &&
+          (tmp->entry.rbe_right == NULL ||
+           tmp->entry.rbe_right->entry.rbe_color == 0)) {
+        tmp->entry.rbe_color = RED;
+        elm = parent;
+        parent = elm->entry.rbe_parent;
+      } else {
+        if (tmp->entry.rbe_right == NULL ||
+            tmp->entry.rbe_right->entry.rbe_color == 0) {
+          struct rbnode *oleft;
+          if ((oleft = tmp->entry.rbe_left))
+            oleft->entry.rbe_color = BLACK;
+          tmp->entry.rbe_color = RED;
+          rotate_right(head, tmp);
+          tmp = parent->entry.rbe_right;
+        }
+        tmp->entry.rbe_color = parent->entry.rbe_color;
+        parent->entry.rbe_color = BLACK;
+        if (tmp->entry.rbe_right)
+          tmp->entry.rbe_right->entry.rbe_color = BLACK;
+        rotate_left(head, parent);
+        elm = head->rbh_root;
+        break;
+      }
+    } else {
+      tmp = parent->entry.rbe_left;
+      if (tmp->entry.rbe_color == 1) {
+        tmp->entry.rbe_color = BLACK;
+        parent->entry.rbe_color = RED;
+        rotate_right(head, parent);
+        tmp = parent->entry.rbe_left;
+      }
+      if ((tmp->entry.rbe_left == NULL ||
+           tmp->entry.rbe_left->entry.rbe_color == 0) &&
+          (tmp->entry.rbe_right == NULL ||
+           tmp->entry.rbe_right->entry.rbe_color == 0)) {
+        tmp->entry.rbe_color = RED;
+        elm = parent;
+        parent = elm->entry.rbe_parent;
+      } else {
+        if (tmp->entry.rbe_left == NULL ||
+            tmp->entry.rbe_left->entry.rbe_color == 0) {
+          struct rbnode *oright;
+          if ((oright = tmp->entry.rbe_right))
+            oright->entry.rbe_color = BLACK;
+          tmp->entry.rbe_color = RED;
+          rotate_left(head, tmp);
+          tmp = parent->entry.rbe_left;
+        }
+        tmp->entry.rbe_color = parent->entry.rbe_color;
+        parent->entry.rbe_color = BLACK;
+        if (tmp->entry.rbe_left)
+          tmp->entry.rbe_left->entry.rbe_color = BLACK;
+        rotate_right(head, parent);
+        elm = head->rbh_root;
+        break;
+      }
+    }
+  }
+  if (elm)
+    elm->entry.rbe_color = BLACK;
+}
+
+void rbtree_remove(struct rbtree *head, void* elmv) {
+  struct rbnode *elm = elmv;
+  struct rbnode *child, *parent;
+  int color;
+  if (elm->entry.rbe_left == NULL)
+    child = elm->entry.rbe_right;
+  else if (elm->entry.rbe_right == NULL)
+    child = elm->entry.rbe_left;
+  else {
+    struct rbnode *old = elm, *left;
+    elm = elm->entry.rbe_right;
+    while ((left = elm->entry.rbe_left))
+      elm = left;
+    child = elm->entry.rbe_right;
+    parent = elm->entry.rbe_parent;
+    color = elm->entry.rbe_color;
+    if (child)
+      child->entry.rbe_parent = parent;
+    if (parent) {
+      if (parent->entry.rbe_left == elm)
+        parent->entry.rbe_left = child;
+      else
+        parent->entry.rbe_right = child;
+      augment(head, parent);
+    } else
+      head->rbh_root = child;
+    if (elm->entry.rbe_parent == old)
+      parent = elm;
+    elm->entry = old->entry;
+    if (old->entry.rbe_parent) {
+      if ((old->entry.rbe_parent)->entry.rbe_left == old)
+        (old->entry.rbe_parent)->entry.rbe_left = elm;
+      else
+        (old->entry.rbe_parent)->entry.rbe_right = elm;
+      augment(head, old->entry.rbe_parent);
+    } else
+      head->rbh_root = elm;
+    old->entry.rbe_left->entry.rbe_parent = elm;
+    if (old->entry.rbe_right)
+      old->entry.rbe_right->entry.rbe_parent = elm;
+    if (parent) {
+      left = parent;
+      if (head->augment != NULL) {
+          do {
+              augment(head, left);
+          } while ((left = left->entry.rbe_parent));
+      }
+    }
+    goto color;
+  }
+  parent = elm->entry.rbe_parent;
+  color = elm->entry.rbe_color;
+  if (child)
+    child->entry.rbe_parent = parent;
+  if (parent) {
+    if (parent->entry.rbe_left == elm)
+      parent->entry.rbe_left = child;
+    else
+      parent->entry.rbe_right = child;
+    struct rbnode* goback = parent;
+    if (head->augment != NULL) {
+        do {
+            augment(head, goback);
+        } while ((goback = goback->entry.rbe_parent));
+    }
+  } else
+    head->rbh_root = child;
+color:
+  if (color == 0)
+    rbtree_remove_color(head, parent, child);
+}
+
+void* rbtree_insert(struct rbtree *head, void *elmv) {
+  struct rbnode *elm = elmv;
+  struct rbnode *tmp;
+  struct rbnode *parent = NULL;
+  int comp = 0;
+  tmp = head->rbh_root;
+  while (tmp) {
+    parent = tmp;
+    comp = head->cmp((void*)elm->content, (void*)parent->content);
+    if (comp < 0)
+      tmp = tmp->entry.rbe_left;
+    else if (comp > 0)
+      tmp = tmp->entry.rbe_right;
+    else
+      return tmp;
+  }
+  elm->entry.rbe_parent = parent;
+  elm->entry.rbe_left = elm->entry.rbe_right = NULL;
+  elm->entry.rbe_color = RED;
+  if (parent != NULL) {
+    if (comp < 0)
+      parent->entry.rbe_left = elm;
+    else
+      parent->entry.rbe_right = elm;
+    struct rbnode* goback = parent;
+    if (head->augment != NULL) {
+        do {
+            augment(head, goback);
+        } while ((goback = goback->entry.rbe_parent));
+    }
+  } else
+    head->rbh_root = elm;
+  rbtree_insert_color(head, elm);
+  return (NULL);
+}
+
+void* rbtree_find(struct rbtree *head, void *key) {
+  struct rbnode *tmp = head->rbh_root;
+  int comp;
+  while (tmp) {
+    comp = head->cmp(key, (void*)tmp->content);
+    if (comp < 0)
+      tmp = tmp->entry.rbe_left;
+    else if (comp > 0)
+      tmp = tmp->entry.rbe_right;
+    else
+      return tmp;
+  }
+  return (NULL);
+}
+
+void* rbtree_next(struct rbtree *head, void *elmv) {
+  struct rbnode *elm = elmv;
+  if (elm->entry.rbe_right) {
+    elm = elm->entry.rbe_right;
+    while (elm->entry.rbe_left)
+      elm = elm->entry.rbe_left;
+  } else {
+    if (elm->entry.rbe_parent &&
+        (elm == (elm->entry.rbe_parent)->entry.rbe_left))
+      elm = elm->entry.rbe_parent;
+    else {
+      while (elm->entry.rbe_parent &&
+             (elm == (elm->entry.rbe_parent)->entry.rbe_right))
+        elm = elm->entry.rbe_parent;
+      elm = elm->entry.rbe_parent;
+    }
+  }
+  return elm;
+}
+
+static struct rbnode *rbtree_minmax(struct rbtree *head, int val) {
+  struct rbnode *tmp = head->rbh_root;
+  struct rbnode *parent = NULL;
+  while (tmp) {
+    parent = tmp;
+    if (val < 0)
+      tmp = tmp->entry.rbe_left;
+    else
+      tmp = tmp->entry.rbe_right;
+  }
+  return parent;
+};
+
+static void rbtree_free_impl(struct rbnode *node, void (*free_cb)(void*)) {
+  if (node == NULL) return;
+  if (free_cb != NULL) free_cb(node->content);
+  rbtree_free_impl(node->entry.rbe_left, free_cb);
+  rbtree_free_impl(node->entry.rbe_right, free_cb);
+  free(node);
+}
+
+void rbtree_free(struct rbtree *head, void (*free_cb)(void*)) {
+  rbtree_free_impl(head->rbh_root, free_cb);  
+}
diff --git a/advent-of-code/2022/lib/rbtree.h b/advent-of-code/2022/lib/rbtree.h
new file mode 100644
index 0000000..4255e84
--- /dev/null
+++ b/advent-of-code/2022/lib/rbtree.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdlib.h>
+
+struct rbnode {
+  struct {
+    struct rbnode *rbe_left;
+    struct rbnode *rbe_right;
+    struct rbnode *rbe_parent;
+    int rbe_color;
+  } entry;
+  char content[0];
+};
+
+struct rbtree {
+  struct rbnode *rbh_root;
+  int (*cmp)(void *k1, void *k2);
+  void (*augment)(void *elm);
+};
+
+typedef struct rbnode RbNode;
+typedef struct rbtree RbTree;
+
+void rbtree_remove(struct rbtree *, void* iter);
+
+// return a iterator
+void* rbtree_insert(struct rbtree *, void *treenode);
+void* rbtree_find(struct rbtree *, void *val);
+void* rbtree_next(struct rbtree *, void* iter);
+void* rbtree_min(struct rbtree *);
+void* rbtree_max(struct rbtree *);
+void* rbtree_left(void *node);
+void* rbtree_right(void *node);
+void* rbtree_parent(void *node);
+
+void rbtree_free(struct rbtree *, void (*free_cb)(void*));
diff --git a/advent-of-code/2022/lib/str.c b/advent-of-code/2022/lib/str.c
new file mode 100644
index 0000000..16968a2
--- /dev/null
+++ b/advent-of-code/2022/lib/str.c
@@ -0,0 +1,130 @@
+#include "str.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include <stdarg.h>
+#include <ctype.h>
+
+char** str_split(char *str, char delim) {
+    char **ret;
+
+    if (str == NULL) return NULL;
+    if (*str == '\n') {
+        ret = malloc(sizeof(char*));
+        *ret = NULL;
+        return ret;
+    }
+    int count = 0;
+    char *begin = str;
+    for (char *p = str; *p != '\0'; p++) {
+        if (*p != delim && !(delim == '\0' && isspace(*p))) {
+            continue;
+        }
+        int size = p - begin;
+        if (size > 0) count++;
+    }
+    count++;
+    ret = malloc((count + 1) * sizeof(char*));
+    memset(ret, 0, (count + 1) * sizeof(char*));
+
+    begin = str;
+    int i = 0;
+    bool finished = false;
+    for (char *p = str; !finished; p++) {
+        if (*p == '\0') finished = true;
+        if (*p != delim && *p != '\0' && !(delim == '\0' && isspace(*p))) {
+            continue;
+        }
+        int size = p - begin;
+        if (size == 0) {
+            begin = p + 1;
+            continue;
+        }
+        char *buf = malloc(sizeof(char) * (size + 1));
+        buf[size] = '\0';
+        memcpy(buf, begin, size * sizeof(char));
+        begin = p + 1;
+        ret[i] = buf;
+        i++;
+    }
+    return ret;
+}
+
+void str_list_free(char **list) {
+    char **p = list;
+    while (*p != NULL) {
+        free(*p);
+        p++;
+    }
+    free(list);
+}
+
+char* str_strip(char *str) {
+    int len = strlen(str);
+    char *begin = str;
+    char *end = str + len - 1;
+    while (isspace(*begin) && begin < end) {
+        begin++;
+    }
+    while (isspace(*end) && end >= begin) {
+        end--;
+    }
+    len = end - begin + 1;
+    char *buf = malloc(sizeof(char) * (len) + 1);
+    buf[len] = '\0';
+    memcpy(buf, begin, len);
+    return buf;
+}
+
+void sb_init(StrBuilder *sb) {
+    *sb = (StrBuilder){.size = 0, .cap = 16};
+    sb->buf = malloc(sizeof(char) * 17);
+}
+
+static void sb_reserve(StrBuilder *sb, int extra) {
+    if (sb->size + extra <= sb->cap) {
+        return;
+    }
+    int new_cap = (sb->size + extra) * 2;
+    sb->buf = realloc(sb->buf, new_cap + 1);
+    memset(sb->buf + sb->cap, 0, new_cap - sb->cap + 1);
+    sb->cap = new_cap;
+}
+
+void sb_append(StrBuilder *sb, char *format, ...) {
+    va_list va1;
+    va_list va2;
+    va_start(va1, format);
+    va_copy(va2, va1);
+    int size = vsnprintf(NULL, 0, format, va1);
+    sb_reserve(sb, size);
+    vsnprintf(sb->buf + sb->size, sb->cap - sb->size + 1, format, va2);
+}
+
+void sb_appendc(StrBuilder *sb, char c) {
+    sb_reserve(sb, 1);
+    sb->buf[sb->size] = c;
+    sb->size++;
+}
+
+char* fgetline(FILE *fp) {
+    StrBuilder sb;
+    sb_init(&sb);
+    while (true) {
+        int c = fgetc(fp);
+        if (c == EOF && sb.size == 0) return NULL;
+        if (c != EOF) sb_appendc(&sb, c);
+        if (c == EOF || c == '\n') return sb.buf;
+    }
+    return NULL;
+}
+
+int fpeek(FILE *fp) {
+    int c = fgetc(fp);
+    if (c == EOF) return c;
+    ungetc(c, fp);
+    return c;
+}
diff --git a/advent-of-code/2022/lib/str.h b/advent-of-code/2022/lib/str.h
new file mode 100644
index 0000000..414adaa
--- /dev/null
+++ b/advent-of-code/2022/lib/str.h
@@ -0,0 +1,24 @@
+#ifndef NEBUTIL_STR_H_
+#define NEBUTIL_STR_H_
+
+#include <stdio.h>
+
+char* str_strip(char *str);
+char** str_split(char *str, char delim);
+void str_list_free(char **list);
+
+typedef struct {
+    char *buf;
+    int size;
+    int cap;
+} StrBuilder;
+
+void sb_init(StrBuilder *sb);
+void sb_append(StrBuilder *sb, char *format, ...);
+void sb_appendc(StrBuilder *sb, char c);
+
+char* fgetline(FILE* fp);
+int   fpeek(FILE *fp);
+
+#endif
+