init

4 files changed, 433 insertions, 0 deletions

diff --git a/advent-of-code/2023/03/Makefile b/advent-of-code/2023/03/Makefile
new file mode 100644
index 0000000..44480b6
--- /dev/null
+++ b/advent-of-code/2023/03/Makefile
@@ -0,0 +1,14 @@
+all: run
+
+run: part1 part2
+	./part1
+	./part2
+
+part1: part1.c
+	gcc -g -I../lib/ ../lib/*.c part1.c -o part1
+
+part2: part2.c
+	gcc -g -I../lib/ ../lib/*.c part2.c -o part2
+
+clean:
+	rm part1 part2
diff --git a/advent-of-code/2023/03/input b/advent-of-code/2023/03/input
new file mode 100644
index 0000000..28e848f
--- /dev/null
+++ b/advent-of-code/2023/03/input
@@ -0,0 +1,140 @@
+..975..95..................717..........................................747................................................622..............
+................/47...........@....701...610.........252.660*.............*..236.....323..........108........653............................
+.......69............313..............$...$...*....@.........640........81.....*................................*332..92....................
+........................*...210.............767...912...367.......505.......817..................*.........478.........=....223.....568.....
+..76...968............108...@.....556.....................=..........*...............412..313...575......../...........................*107.
+............773/..891............*....................744.....805...14................../..../................320&.567..#...................
+.962..708............&........399....146.....385.................*..........825.......................................-..655....485...-.....
+...*.........+..........................*76...+..................242....997..*......185..........207.390..870...883............*.......337..
+....929...299....................*.................249........-...........*.373.....*.............*.....*.*....*.............549............
+................196.745.996...364..............409...-.926.....273.....580.........31...........545..547...862......810.....................
+................*.......*..............900+....*..........*........586.........936...................................*.........673..........
+.../..........864.683.215....*......%.........702..166..46..........&....341..........694..496.......528.%...........839...105..*...887.....
+....506...617.....*........51.807....942..424...............................*..........@..+............@.84...................*......=......
+...........@....594.........................*..........*675...........345..52...$..................-..............899.........804.$.........
+.362*366.................487+.48&.......600..180....845........................535...18...........397.#908....432*........229......346......
+.................*................835....................578......*502...............*..416.............................................391.
+....610&...514...501......./........*....*71.........../.......674......925...............*.869.....966........393................/.687.*...
+............*...............786...248.104........92.633.....%..............*104...&466..138..@.........*.525...+......974......339..=...260.
+....372/.889..............................55.406........134..250.=228..609...........................69...............*.....................
+...........................................*........976...*...........=.......357...........................191.....150.....................
+...-...........595.634.........*396......592..594......*......411.856...760....../..................201.....#...709................168......
+.936..236.........*....@....436.....100....../......35...../.....*........*....................917%............*.....................*..#63.
+.......*..............542..........................*........689.........26....667.&...................738....831..$.............513.53......
+........10.....529........*250..........162.......390...........................*..70.............................701..........*............
+..355.........&........394......301@..........542..............................142..........%..............%..........*.....507.............
+.....*.........................................*.....%..283.....*.........997&.......@670....402..........808......308.459.......712...152..
+..291......246.@....+986.....336/.......976...468.264...*....739.187.............................................................*.....*....
+........../....46...................186.$..............674............................227......-............975...............436.......492.
+.491........................810.......*........................772*.........742........%....198.....*702.......*.596=....64.......=.........
+...................706......=......415..................=.199......235......*...47........................72.607...................443......
+.214..............*.....771.............302...........230..+..............810.....*219.606........912.....................=.................
+......277......320.............937.....*.....+....632...........&374..............................*....................898.....642%.........
+.........#....................*.......716....229./.........................$................934...233...............98............../.......
+.....*........-659..457.........964...................659....786....619.666........277...@.....*......930*460..618...........910..265.......
+..845.877.343......................*537.../120.......*.......*.....*.................&...175..631.............=.................#...........
+............*....................+................@...35.949..34.381......273...880......................451........326.....................
+............876..880......827..733.......645.......38......*.........402.....+..........902....459.775........837.....*.185.......813.......
+........578................/............*...............622..18.........*234..............+....%..........448.......935....#.............350
+..........*...468.....546................588....146=.........*..142.795..............*424................../.....................=..........
+........245............@...746.......362..................970......*..............593...............487.......+.............709..593........
+...990......&415..............*381......*.....................435.......214..908..................*....*.....351.....876.25....*............
+......*............293*.....%...........271.............135......*......=........540............177....604...........&.....-.46..........166
+...609.....................910.................@........$.......321..........141....+.45.....................750......................98....
+.......#....779........944.....653...........797...........788.................*......+....164.724....475&...+.............-.471......&.....
+..794...487....&..81...........*...................@............666@.....*981.937.............*.....%..........888....+...81................
+.....*...........+......694.............748...104..859..............................675.434.......290.............*..352........353=..$.....
+...619.977.........859..#....235....230*......*..............429........335....-.......*......631.......=.......27...................192....
+.......*............=...........&.........121..680.195.959......*417.....*..938.............../..........739..#..............194.750........
+....309...439.............14...............*..........*...............723.........163..748...........853.....885.........175*........487....
+.............*707..-626..........464.....382................356...........868#....*...*.....13......*............450............#.....*.....
+........216......................*...619......$..270........*.....892............25.494.841*.....971.............*............157.+...119...
+...#40...../............343..559.425.......536........718....739...#.......284...............726.....985..136...597.621.173.......203.......
+................383............/......................*...................@....348............*.....*.......*........./...*...811.......*158
+...=..............$......@....................776.829.85...&........541.......*....*...&....700......341.995.....73......114....*....267....
+.700.203....591.*.....924..........$217.......@.....*.......590....*.........812.579....517.......................*.............730.........
+......#......*...586.........312..................806............435...259...........................573........453.282*132.243.............
+..........224.................#.......468@............-...%.............*..............453...................$.....................-........
+....................................................227.673....881......828..&.....632*...................589.....................284..-....
+.....680.........871....17+................117.................*.............506..................#...410...................616.........519.
+........*..386................78*762.........@........28..557.655.......359........-............124..#......&..........843./................
+......724...*..584.....552............................*...&.................209..857...633-..............602...932......*........132&.......
+..........41../.........*..........................#..427.............=370....*................................*...353...902...........529..
+.....................150.......868.......370....549.........779...................284...........431.....3.....889.............189..103.=....
+.......530..355..........442...*............*63............+.......852.....935.....*..............%.....*..................@....*.-.........
+..........*...*...976.....*...500....@...........572...........940....*990..*....627.790.................460..904..601-..821..930....699....
+..........643.824.......248........358...4.........&..301.........&........538.........*.%436....565..........*......................../....
+.768..$.....................186..........*...178........*.......................*.&520..............%........782..........497.-......*......
+......762..828*...972......*..............3.*.......................@....../..836...............278..............666......*...927.413.185...
+....&..........40.......86.122..........&....450....................1....202............42...51....*..............*.....215.................
+.353.................94*.................995.....655.....520...828....*...........612..........&.119...........486...............713........
+.........................255........................*.......+.....-..463..........*........235........836....................668............
+...................................................286........338........=.393....398........*....199./............631..........*631........
+................64%....704...928.........470...125............*....708.15...*.............193.......*........641....*......687..............
+........$..............*...................&.....*..........582......*....652.@358..643..........125.....458........168....$.......$194.....
+........293.........305......417...............117....................612............*......262.............*903............................
+.....$...................615*..........581.........335...139..505.419.............656.........+.......506................710.....956........
+776..110.....+............................-........#..........*....*...447......*......................*...*.....938.366*.......#....376....
+..........366............844....305..761......780......560........236........725.272.....450.............67.126.....................*.......
+.................669$.......$.......=............*220./.....+665........495................*.@103....992....................&........600....
+.......*......................812/.........................................$............940...........+...................146...975.........
+....410.650.282.....*...............696.833....957...............996...*......772.287...................921..935................%.....$.....
+............*....413.921...713....................%.....769.........@.390.216..#.....@..........................=...........*.......46......
+.....798.136..............%....150.....236..............*......31...........*..........@.64..17......616..........901......344..............
+..............................-........*.....402......873.......*......692...592....390...*.............*277................................
+......539.....799.../.....272....%.@....694.#.............667...318.......=...............762.......71%.......-153......................531.
+..........556*......573.......465...916...................*..........602.........................=.......145...........................*....
+........................451.............../....%.....625.401.........*........428-.....493......479.427....$.........60......951......281...
+..947+....36....270....*............517....521..258.*............108..812.............*................*........................*372........
+...........*....*....957.823...290.....*.............415..........*...............908..730..........589......+..............................
+857.........843............*........794......................677..27........................121...........670.........548.837*....&.....664.
+......175..........-.....=........................422.......*..................226-..344.......*...................2....%..........474......
+...................283..190..@...........458........*.162@.666.517....202...............*..@...545.%.........705.............*..............
+...............*............296.466.....#.........................*..*.....852..208...999.475......256..........=....642..188.386...........
+............504.888..................52....416......394...349.....53.953...*......*...........@521.........213........*.....................
+......225...............272*32........*.....*..........*...%..............728.........827.513..........287*.........924..388%.........&.....
+..453...*..................................71.....*..437.......501...869.......928....%...#....................%225.............734@..157...
+....*..400...........810=.300@...13.15.537.....997........./......*.....*.........+.........407.758...674............604....500.............
+..970..........409...............*...*...*................159...788....338..............636*...../....#.......#895....*......./.............
+..................................52.....872........+...........................-........................524.........297............314.....
+...........=...469.....408.............&.........641......364%.780...526.........540.865....742............*..............549..505...*......
+........404.......*...-....58..%....577...............655......*.............613......*.............343..779./854............*....*...567...
+...103............284......./...999....................=.....640.....284..............566.982..........$...........476...478.793..556.......
+......*.....436........916.................941.............@.........&...........284.........*183.........857.953...........................
+...............*.404=.....*910..703@...20......266......815.....201.....54.332...........................@......*...........95..............
+.............898........................*........*..........13.....*806...*.......280.........................905........63*................
+........&.........642..271.627..920.+....534...96..780......@....=...........246../......99........................................../......
+....$....518.......@......*......*..323..............-............477....*4...*...........*....979......810.................366....697......
+.....439........................364.........161..594.....647..................802.........234..............*17......125..82....*............
+................187....667....................*..#.......*.......*................604..................946.............*....414.............
+....585...218.....*...*.............-....536.396........950...200......296*935...*..........#...382..........883......182.......326....*....
+.....+......-...557.349...........217............................./105..........527..387....394...*...........#..430*.....501.......393.190.
+.......*474.............16....................675.....999..............362..............*..........576...................*..................
+....449.....+.296*468.....................607....*...........-..#.................619....177...............31...........194..198..187.......
+.........156......................330.......+..332...631...936...477................*...........658..........%..845..........*..............
+....*262.........$......362......*.....429=..............................*324....296...........+.......161.....*....57.....309..............
+.403............492..97.@.....695..696......$.840..&.................21.....................@.........*.......178...+....$.............364..
+......178..692*.....%.....82..........=...176.......456.....517........+...238.704.......682......266.................&..222..........*.....
+......*........993........*....931*...........445..............*.................=...........@...*.......448.......251................222...
+.......824............467..232.......664..299*.......322*512..850..............@..........585....259........$..................&............
+...458.....572.................379....*........123.....................-........298..................-................336...908....*........
+....&......*....&..732...701/....*....440.....$...........739..636.....65..../.......%151.............823.455............&..........119.....
+........550....391..%.............259....................#....*............834............232.179............*.........4...795.784..........
+.............%...............729...............568.............936...............952........*..*..............726..........*.........-......
+...627.....87....@...........-...........6.....%...106.......................458*.....281..811..282..500..............=....833....214..780..
+..............320................665..............*........584.........................*............................343...............*.....
+..................997....84.590.....*795.90*487.842..%431....*.......233..692....259....391.113*........*338............./..391.............
+.....62.....#689.*.........*.................................444.......*...*......*.............445..861...........498/.857..*.....505*.....
+......*...........436.869.....634@..663...599..901*678.100..........666....301..493.986....174.............838*492..........454........313..
+.....362.....983....../................+..*.............=.............................*....*.......259.............+....464.........27......
+...%........................580....68.....45.........................................21..768...267....*.+....661..879..@....&......$........
+.643....545......./435.....*.........+.............................823....919.......................20..102.*..............267.690.....55...
+.........*...............557....247.......653....584.5*....430....*........../...529+...........856..........305.254..212.............*.....
+........945...528................/...775..+............204...-.537....$..528................276*...................%....*....863......612...
+....572.......*.........614.........+................................810...............842........438.....26...&.....%.........*............
+.......*....201.@......*....671..$........................../.............................*...832*.......*....214.899..........795.421+.....
+994..797.........684.390....*....452../..................989..728............685....23+.856...........498.............443...................
+.....................................424.......%...............@.......228.....+..............+.......................$.....................
+.....2...812.517.........602*967.........262....953...*.....*....67...*...........+......1.431.....721.....402%..&.......*.....504..........
+.............*....%..................963*...........96...287.255.*...548.........534....*.............*..........896..531.789.=.......855...
+...........579....595...........8................................781...............................547......................................
diff --git a/advent-of-code/2023/03/part1.c b/advent-of-code/2023/03/part1.c
new file mode 100644
index 0000000..4ae9ef9
--- /dev/null
+++ b/advent-of-code/2023/03/part1.c
@@ -0,0 +1,130 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "vec.h"
+#include "str.h"
+
+void* read_input() {
+    FILE* fp = fopen("./input", "r");
+    void *vec = new_vec();
+    while(1) {
+        char *line = fgetline(fp);
+        if (line == NULL) break;
+        char *stripped = str_strip(line);
+        if (strlen(stripped) == 0) break;
+        vec_push_back(vec, stripped);
+    }
+    return vec;
+}
+
+typedef struct {
+    int line;
+    int column;
+    int value;
+    int length;
+} num_t;
+
+void *parse_nums(void *schema) {
+    void *nums = new_vec();
+    int j = 0;
+    const int IN_NUM = 0, IDLE = 1;
+    int state = IDLE;
+    for (int i = 0; i < vec_size(schema); i++) {
+        char *line = vec_get(schema, i);
+        int line_len = strlen(line);
+        int value = 0;
+        int length = 0;
+        state = IDLE;
+        j = 0;
+        while (1) {
+            char c = '.';
+            if (j < line_len) c = line[j];
+            if (state == IDLE) {
+                if (isdigit(c)) {
+                    state = IN_NUM;
+                    continue;
+                } else {
+                    j++;
+                    if (j >= line_len) break;
+                    continue;
+                }
+            } else if (state == IN_NUM) {
+                if (isdigit(c)) {
+                    value = value * 10 + (c - '0'); 
+                    length++;
+                    j++;
+                    continue;
+                } else {
+                    num_t *n = malloc(sizeof(num_t));
+                    *n = (num_t){
+                        .line = i,
+                        .column = j - length,
+                        .value = value,
+                        .length = length
+                    };
+                    vec_push_back(nums, n);
+                    value = 0;
+                    length = 0;
+                    state = IDLE;
+                    if (j >= line_len) break;
+                    continue;
+                }
+            }
+        }
+    }
+    return nums;
+}
+
+int is_symbol(char c) {
+    if (c >= '0' && c <= '9') return 0;
+    if (c == '.') return 0;
+    return 1;
+}
+
+int is_a_part(void *schema, num_t *num) {    
+    int line_len = vec_size(schema);
+    int col_len = strlen(vec_get(schema, 0));
+    for (int i = num->column - 1; i < num->column + num->length + 1; i++) {
+        if (num->line - 1 < 0) continue;
+        if (i < 0 || i >= col_len) continue;
+        if (is_symbol(((char*)vec_get(schema, num->line - 1))[i])) {
+            return 1;
+        }
+    }
+    for (int i = num->column - 1; i < num->column + num->length + 1; i++) {
+        if (num->line + 1 >= line_len) continue;
+        if (i < 0 || i >= col_len) continue;
+        if (is_symbol(((char*)vec_get(schema, num->line + 1))[i])) {
+            return 1;
+        }
+    }
+    if (num->column - 1 >= 0) {
+        if (is_symbol(((char*)vec_get(schema, num->line))[num->column - 1])) {
+            return 1;
+        }
+    }
+    if (num->column + num->length < col_len) {
+        char *line = vec_get(schema, num->line);
+        if (is_symbol(line[num->column + num->length])) {
+            return 1;
+        }
+    }
+    return 0;
+}
+
+int main() {
+    void *schema = read_input();
+    void *nums = parse_nums(schema);
+    int sum = 0;
+    for (int i = 0; i < vec_size(nums); i++) {
+        num_t *num = vec_get(nums, i);
+        if (is_a_part(schema, num)) {
+            sum += num->value;
+        }
+    }
+    printf("%d\n", sum);
+    return 0;
+}
diff --git a/advent-of-code/2023/03/part2.c b/advent-of-code/2023/03/part2.c
new file mode 100644
index 0000000..a5ab825
--- /dev/null
+++ b/advent-of-code/2023/03/part2.c
@@ -0,0 +1,149 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "vec.h"
+#include "str.h"
+#include "map.h"
+
+void* read_input() {
+    FILE* fp = fopen("./input", "r");
+    void *vec = new_vec();
+    while(1) {
+        char *line = fgetline(fp);
+        if (line == NULL) break;
+        char *stripped = str_strip(line);
+        if (strlen(stripped) == 0) break;
+        vec_push_back(vec, stripped);
+    }
+    return vec;
+}
+
+typedef struct {
+    int line;
+    int column;
+    int value;
+    int length;
+} num_t;
+
+char *compose_key(int x, int y) {
+    void* ss = new_ss();
+    ss_add(ss, "%d,%d", x, y);
+    return ss_cstr(ss);
+}
+
+void *parse_nums(void *schema) {
+    void *nums = new_vec();
+    int j = 0;
+    const int IN_NUM = 0, IDLE = 1;
+    int state = IDLE;
+    for (int i = 0; i < vec_size(schema); i++) {
+        char *line = vec_get(schema, i);
+        int line_len = strlen(line);
+        int value = 0;
+        int length = 0;
+        state = IDLE;
+        j = 0;
+        while (1) {
+            char c = '.';
+            if (j < line_len) c = line[j];
+            if (state == IDLE) {
+                if (isdigit(c)) {
+                    state = IN_NUM;
+                    continue;
+                } else {
+                    j++;
+                    if (j >= line_len) break;
+                    continue;
+                }
+            } else if (state == IN_NUM) {
+                if (isdigit(c)) {
+                    value = value * 10 + (c - '0'); 
+                    length++;
+                    j++;
+                    continue;
+                } else {
+                    num_t *n = malloc(sizeof(num_t));
+                    *n = (num_t){
+                        .line = i,
+                        .column = j - length,
+                        .value = value,
+                        .length = length
+                    };
+                    vec_push_back(nums, n);
+                    value = 0;
+                    length = 0;
+                    state = IDLE;
+                    if (j >= line_len) break;
+                    continue;
+                }
+            }
+        }
+    }
+    return nums;
+}
+
+char char_at(void *schema, int line, int column) {
+    char *buf = vec_get(schema, line);
+    return buf[column];
+}
+
+void mark_asterisks(void *asterisks, num_t *num, int x, int y) {
+    const char *key = compose_key(x, y);
+    void *num_list = dict_get(asterisks, key);
+    if (num_list == NULL) {
+        num_list = new_vec();
+        dict_set(asterisks, key, num_list);
+    }
+    vec_push_back(num_list, num);
+}
+
+void find_asterisks(void *schema, void *asterisks, num_t *num) {    
+    int line_len = vec_size(schema);
+    int col_len = strlen(vec_get(schema, 0));
+    for (int i = num->column - 1; i < num->column + num->length + 1; i++) {
+        if (num->line - 1 < 0) continue;
+        if (i < 0 || i >= col_len) continue;
+        char c = char_at(schema, num->line - 1, i);
+        if (c == '*') mark_asterisks(asterisks, num, num->line - 1, i);
+    }
+    for (int i = num->column - 1; i < num->column + num->length + 1; i++) {
+        if (num->line + 1 >= line_len) continue;
+        if (i < 0 || i >= col_len) continue;
+        char c = char_at(schema, num->line + 1, i);
+        if (c == '*') mark_asterisks(asterisks, num, num->line + 1, i);
+    }
+    if (num->column - 1 >= 0) {
+        char c = char_at(schema, num->line, num->column - 1);
+        if (c == '*') mark_asterisks(asterisks, num, num->line, num->column - 1);
+    }
+    if (num->column + num->length < col_len) {
+        char c = char_at(schema, num->line, num->column + num->length);
+        if (c == '*') mark_asterisks(asterisks, num, num->line, num->column + num->length);
+    }
+}
+
+int main() {
+    void *schema = read_input();
+    void *nums = parse_nums(schema);
+    int sum = 0;
+    void *asterisks = new_dict();
+    for (int i = 0; i < vec_size(nums); i++) {
+        num_t *num = vec_get(nums, i);
+        find_asterisks(schema, asterisks, num);
+    }
+    for (void *iter = dict_begin(asterisks);
+            iter != NULL;
+            iter = dict_next(asterisks, iter)) {
+        void *list = dict_iter_value(iter);
+        if (vec_size(list) == 2) {
+            num_t* n1 = vec_get(list, 0);
+            num_t* n2 = vec_get(list, 1);
+            sum += n1->value * n2->value;
+        }
+    }
+    printf("%d\n", sum);
+    return 0;
+}