hmmmm

3 files changed, 302 insertions, 0 deletions

diff --git a/2021/15/Makefile b/2021/15/Makefile
new file mode 100644
index 0000000..1fb60ab
--- /dev/null
+++ b/2021/15/Makefile
@@ -0,0 +1,19 @@
+DEBUG = -Wno-error -Og -g -s -fsanitize=undefined -fsanitize=address -fstack-protector-all
+CFLAGS = -Wall -Wextra -Werror -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wformat=2 -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -Wvla -pedantic -Ofast -std=gnu99
+
+# Not the best makefile but idc
+
+debug:
+	@gcc $(CFLAGS) $(DEBUG) solve.c -o solve.o -L/usr/lib -lcrypto
+
+build:
+	@gcc $(CFLAGS) solve.c -o solve.o -L/usr/lib -lcrypto
+
+clean:
+	@rm -f *.o
+
+run: debug
+	@./solve.o
+
+time: build
+	@./solve.o
diff --git a/2021/15/input b/2021/15/input
new file mode 100644
index 0000000..88734b9
--- /dev/null
+++ b/2021/15/input
@@ -0,0 +1,100 @@
+2331388323638161787399391263569123115292618342227141295826631182191129426253118171436238115111124362
+8329311651253148931214679312159191282297394511936411514975191845522598161261792128373372964255217623
+5213996517311119375469717261791142598367189818137751564212444658171138245154643871418242984159164719
+3261939455331818312911416132186221132321568221122492545597298133872134993351311999312265952833225595
+5114894127689414631321151717117981112191451649143987312267584216922145142912231221181254138984353619
+8317953617943139627171182229512313116498152122111715112193229613912451432949947421437869512929111533
+7346597213791139114811111729819641351164484293149919499181923111312242243621944519235621423223918131
+8471435541514253262128911215486613121917239411191311318922652863619488911222231298631381722241462127
+1626114218162522973115882121194869183168693245229811114152758125413224845114411914146712614134811156
+4149895923531224511952638143822416688399811214819118852213516842422229333221613481364245726739111864
+4638958152311545152179625233196891575823191141919467518892318292425531542113357113255616193318355147
+1821249355121523129219211114415681151124655211871421665423731279528348391518661727226142287731365142
+8413559611119363323614181472261911675123312911172351627741431495721399113364294516212129617148322891
+5551317411648134419511366211727611151681113423721331491614741518312715858718317526211181212111714127
+8911717279115491242677142481122122921469121134391211162636471231193261334112652261315782214359719348
+4391767161119431264111836243663789121118963411942396214212291221758412511522717319293571186382293351
+2684627241961834768541144419312441479224717375243628129627942981325793331111925438915569394112134731
+1114162814298182615125394318411227531332847921317227374128227313271428932116413111113411185117916881
+2859558751269189119214763954923212116112568598691111825112141348132942696121464868712294174912945119
+3331194912154241448534211328211592373463331114681161421131969731464932715931521112819235713716148121
+2419152281333711234482291291127652183831941911819285417289416162311441331629152111415752521213286621
+2338187119794239119111171711913134166583318438183953573176551324313321129299521293471311233543693138
+8427916973226194311418414191141815332937912118653339726628272231616461115149397655943556851435811742
+3194191911322328338911713382556126255619784115679241112629124111323399276339524912128889123781732391
+5283641716316291146175232381844113145111917211741895694211454911653768178731711951143712131813126432
+3526132881494293171611151148148115511121625152769751412225231961314154714211229962561333227413181129
+2231173658926187291742396213168822911986848413642729272326131529357296943461119461939335231894153549
+1421381179114212224597271754917294792113811241732117121168211621919131125627891662166212291249133912
+3574259918296381137781428111331334572591621542782211994171252933691339749221811632247523121118115416
+4637962271333341118523414932319811114711182774391931231217653164252351633264343321119792349615491761
+6171127773639615241118529314115637453184613341134515234123799126812115142951165164213162111212952111
+3194279342118127567318149911711795841724155299749142811551412652616415414129134643621231139273332956
+1119152939341516178399128141294522359133271732211111941945346119429159185415312214422118349147894479
+6731998835914512311928861172839162157824393141731941168131681649917241249511827592849711591211553261
+7291825322116926612125171151121419792985312223759991511496122211371572243239414632139935919731211126
+5231112632156976323459141531841538695241113541959671917111223191898212119196111993561884689117331869
+8116513159881924972112152125215911922276311144442995532198132613823448137852923171186841851128351161
+1911929296211217235123111944258211136127114162396111241143952241518965811161775488392311925859249412
+2261962892122482851989143122561474611588225211121692162291115474813281121116616111927911595111151251
+8244832422126789296999314195811451259318972243111167365694341116399912217124215373523831387131352931
+1853311151516591716219792228578133193941664942111684412533585128434692332222473659142281765787621138
+9537851675123143211254384515612313819157127968531245552472141769281312213317126279813354529942191529
+1141116261511243841336616189229732419662333929431152411316327496525123952914132534182849618212259615
+5212129135355974379191112317221251911633159921671124917134637536155122122463974671741914675524111192
+3536351927157121812412511287122282994113328861124314333897211351113737932171951331153721948439148123
+8122721112922911192171191411141779221882187933186431179119236298323432496116193463341521892121394791
+1174615131611222429397228112416911318479856462136173899396359212111215354228939116491237912291879354
+5143198771712179261652441172132334496813937911518119116742812169231987226419112247214949125224316632
+1291249312218614141149931141919285711811823827762639169412482915715213719517145191991972382963116143
+3628713162563278519269726352712171263661216771218146124584112932481121621815154131911182111417511247
+7119589917319532131231259944423311131121823441211144132141116912167261151841168817273919267216132317
+2682588417311117111428111721183128211912171341512113541411191148788625511187919966428145478111146431
+5712471119433113112956932711793966283486213315871413147925494871313363242334119191221132179945643219
+1413144174858192981331211113912134318433912118511729731229118899116722223252834913126362628218722926
+2677691297988621154239141972154569191821482211916629333433121423241294876291613113176419144225211912
+1243446191935215393133235427164517149444889232331272522123977181624839744132118125319763861228234656
+7142814181185129341212713213641812481579593512312717113835741356411921334129162128551619212187111391
+2896172447819622251434121552197843881566317713225958412115651313421672128191153111325228392413114386
+9522821169115122532144311113194129833135511128458418511316889372256915141258511136322914141916115116
+7585995191216321624558573928919631517132274693121711141111155544283492541316536199862111277177114359
+6161629818791453821698899372431347971231521311139311721113354271387353426129993688424435496332611637
+9865254212697314671436471321422442794688322691411911182161868213259647418695911567376222572117176953
+9119991151125413352235611331762922111415865913177957211312832942251617125241141432254795951544882913
+8711931139115422441911223419444371944353269182714121448326131218114474131812112162314245936269913113
+5511155412529391431111348811465427243911114757567852148645114248911692935661116141393174112185731165
+3897171672274113524321178231151241122654348182477879431621117411228194711919111143192412212131377281
+2567948419641115769121453142586116841892845833419762611815112431933181679513759163117116943152135712
+1214919441225715121198162339431121326711999118312165622215183743461895225319954192171226822641511267
+1325311917911488991212491113281322123561171489393178618119791335641612366472791113444785342554912169
+7149113311148949119599817294857152311312199113763371119132531191112929715235133733723521133114433614
+9716428791617211319218441141683478292374525319819252415928188911712191231731539483665387131821415119
+7761142623691912236213811174278782273621742191192278195311183732161172489372731292157112591251651922
+1723862352229281142132211211115313339159442672841181559637187351998151432175895811531721977181429154
+8232971449518151321212261688453413961364984562661211711449346944364932346111881212114111322538818216
+2133711322131361291911951251332159252297117319124312381867431183518791194971656286469394199613282941
+1791834418333119215121241695912162475851393129129272833318324391659791521211957811962137933921921172
+4211881814412523191861824314912113116441614693613468692649282965146551544621884879344819851821196289
+4239934411879317281461993916212418592669129435754241141443791559232422341147864715185731173151112348
+2278515211119833259531189141257182899522149415162225516823181614835171948111132791219637215114739319
+6111791351361541662255193898217142391242113969612113198911122247796936977131111742221689739621713311
+9812123351219181139337922111819541588534111311262115215144123159138489421339611161699924617856137417
+1122631413493173914413141939694182481111233924475437229841396231226174336227677171511415131347953373
+9311221919485212177184171257146292521271915854242911111521178414621112712132121818584391934875126896
+1949461911533111919951733122161131519431189251112617211678219844732361941985814765136334739612363322
+1912315561836316169111127235223862981499131112833659732167334325163789612155411242574121761428241829
+3431132521197319216417211319961461995412112546133283157111288971181113125937811869444193641239255169
+8272128161944812371451127913329972728611399466628112462411465893561975591157152599497218629715241173
+5929613292142529182113299825358632281894673135231342523641128339869918282114368411722256158712311217
+1613984821985188114169613413195221248757458129911422119545114125913239899112531175211359713559411461
+1841144121251597386994119516254123387269162154657382219941511191319629819651151233553198556131158319
+6181486282549195127382569891291911145525492132413512532115548123122114931381144971673232178461692241
+2122931131552576121211214269519112318141119669497172691711419711829684188216741961166423362114211763
+7331249612114924111139849955721214636832111559983458112217919118362371613762113182211695213568776151
+8839116538213331742413272581583112567925592551159141127221333119844972117444633188513121313132186116
+1449163396715312116378711719987129521114341224536914414993212639721138591112512598219355179521252164
+1162361871117422823359213425112346372893191111733991943311731128169855181183246114153159158759811551
+1496274421162915212192943813121362369923161249623166391314619497283319214511185211641111825312892553
+1821111931141395137619416345127152199118541251197225895217856156445231633941321398318194115629913292
+2461131231965974129721167115524443521891352525461448321145339316647126211269238831498512659298396159
+6112851322783221514154142291126293349181211111135663126974495414222811141375711391289743412348124497
diff --git a/2021/15/solve.c b/2021/15/solve.c
new file mode 100644
index 0000000..c0c16cb
--- /dev/null
+++ b/2021/15/solve.c
@@ -0,0 +1,183 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#define COUNT(a) ((int)(sizeof(a) / sizeof 0 [a]))
+
+#define WHOLE                                                                                      \
+	fseek(fp, 0, SEEK_END);                                                                    \
+	long fsize = ftell(fp);                                                                    \
+	fseek(fp, 0, SEEK_SET);                                                                    \
+	char *data = malloc(fsize + 1);                                                            \
+	fread(data, 1, fsize, fp);                                                                 \
+	data[fsize] = 0;
+
+struct node {
+	int x, y;
+	int risk;
+};
+
+// prioritized queue
+struct queue {
+	struct node *heap;
+	int size, max;
+};
+
+static void pop(struct queue *queue, struct node *out)
+{
+	if (queue->size <= 0) {
+		fprintf(stderr, "Can't pop null node\n");
+		exit(1);
+	}
+
+	*out = queue->heap[0];
+	queue->heap[0] = queue->heap[--queue->size];
+
+	for (int i = 0, curr = 0;; curr = i) {
+		int child = (curr << 1) + 1;
+		if (child < queue->size && queue->heap[child].risk < queue->heap[curr].risk)
+			i = child;
+		child++;
+		if (child < queue->size && queue->heap[child].risk < queue->heap[i].risk)
+			i = child;
+		if (i == curr)
+			break;
+		struct node temp = queue->heap[curr];
+		queue->heap[curr] = queue->heap[i];
+		queue->heap[i] = temp;
+	}
+}
+
+static void push(struct queue *queue, int x, int y, int risk)
+{
+	if (queue->size >= queue->max) {
+		fprintf(stderr, "Queue size too big\n");
+		exit(1);
+	}
+
+	queue->heap[queue->size].x = x;
+	queue->heap[queue->size].y = y;
+	queue->heap[queue->size].risk = risk;
+	int p = 0;
+	for (int i = queue->size++; i > 0; i = p) {
+		p = (i - 1) >> 1;
+		if (queue->heap[p].risk <= queue->heap[i].risk)
+			break;
+		// Swap
+		struct node temp = queue->heap[i];
+		queue->heap[i] = queue->heap[p];
+		queue->heap[p] = temp;
+	}
+}
+
+static struct queue *create(int size)
+{
+	struct queue *queue = malloc(sizeof(*queue));
+	queue->heap = malloc(sizeof(*queue->heap) * size);
+	queue->size = 0;
+	queue->max = size;
+	return queue;
+}
+
+#define SIZE 100
+#define GET(x, y) (data[(y) * (SIZE + 1) + (x)] - '0')
+static int part_one(FILE *fp)
+{
+	int risk = 0;
+
+	WHOLE;
+
+	int visited[SIZE][SIZE] = { 0 };
+
+	struct queue *queue = create(500);
+	push(queue, 0, 0, 0);
+
+	while (1) {
+		struct node node;
+		pop(queue, &node);
+		int x = node.x;
+		int y = node.y;
+		risk = node.risk;
+
+		if (visited[x][y])
+			continue;
+		if (x == SIZE - 1 && y == SIZE - 1)
+			break;
+
+		visited[x][y] = 1;
+		if (x + 1 < SIZE && !visited[x + 1][y])
+			push(queue, x + 1, y, risk + GET(x + 1, y));
+		if (y + 1 < SIZE && !visited[x][y + 1])
+			push(queue, x, y + 1, risk + GET(x, y + 1));
+	}
+
+	free(data);
+	free(queue->heap);
+	free(queue);
+
+	return risk;
+}
+
+#define SIZE2 (SIZE * 5)
+#define GET2(x, y)                                                                                 \
+	(((data[((y) % SIZE) * (SIZE + 1) + ((x) % SIZE)] - '0' + ((x) / SIZE + (y) / SIZE)) -     \
+	  1) % 9 +                                                                                 \
+	 1)
+static int part_two(FILE *fp)
+{
+	int risk = 0;
+
+	WHOLE;
+
+	int visited[SIZE2][SIZE2] = { 0 };
+
+	struct queue *queue = create(1500);
+	push(queue, 0, 0, 0);
+
+	while (1) {
+		struct node node;
+		pop(queue, &node);
+		int x = node.x;
+		int y = node.y;
+		risk = node.risk;
+
+		if (visited[x][y])
+			continue;
+		if (x == SIZE2 - 1 && y == SIZE2 - 1) {
+			risk -= GET2(x, y); // Hmmm
+			break;
+		}
+
+		visited[x][y] = 1;
+		if (x + 1 < SIZE2 && !visited[x + 1][y])
+			push(queue, x + 1, y, risk + GET2(x + 1, y));
+		if (y + 1 < SIZE2 && !visited[x][y + 1])
+			push(queue, x, y + 1, risk + GET2(x, y + 1));
+	}
+
+	free(data);
+	free(queue->heap);
+	free(queue);
+
+	return risk;
+}
+
+int main(int argc, char *argv[])
+{
+	(void)argc;
+	(void)argv;
+
+	FILE *fp = fopen("input", "r");
+	if (!fp)
+		exit(EXIT_FAILURE);
+
+	clock_t tic = clock();
+	printf("%d\n", part_one(fp));
+	rewind(fp);
+	printf("%d\n", part_two(fp));
+	clock_t toc = clock();
+	printf("TIME: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
+
+	fclose(fp);
+	return 0;
+}