commit b2215616c2ba2f386f48f8714beeaa034072cd6a
parent 7ef5ddd38b62e5e0f587e8632281994345b43ff1
Author: bsandro <[email protected]>
Date: Mon, 13 Dec 2021 23:33:38 +0200
Day 13, puzzle 1
Diffstat:
5 files changed, 1253 insertions(+), 0 deletions(-)
diff --git a/day13/Makefile b/day13/Makefile
@@ -0,0 +1,25 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.c ../common/*.c)
+DEPS:=$(wildcard *.h ../common/*.h)
+OBJ:=$(SRC:.c=.o)
+CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common
+LDFLAGS=-lc
+
+all: $(NAME)
+
+.PHONY: clean run
+
+clean:
+ rm -f $(OBJ) $(NAME)
+
+%.o : %.c $(DEPS)
+ @$(CC) $(CFLAGS) -c $< -o $@
+
+$(NAME): $(OBJ)
+ @$(CC) $(OBJ) -o $@ $(LDFLAGS)
+
+run: $(NAME)
+ @./$(NAME) input.txt
+
+test: $(NAME)
+ @./$(NAME) test.txt
diff --git a/day13/input.txt b/day13/input.txt
@@ -0,0 +1,987 @@
+982,10
+1094,887
+895,815
+1216,453
+1258,747
+162,663
+552,568
+271,662
+333,863
+1252,65
+1009,687
+900,887
+199,273
+254,352
+345,787
+688,502
+825,325
+137,879
+1258,467
+547,42
+251,275
+446,628
+108,84
+1257,668
+1141,316
+679,548
+930,831
+463,700
+785,393
+485,578
+678,78
+1047,37
+1123,613
+586,535
+65,275
+1233,665
+137,15
+1115,210
+306,890
+946,234
+959,122
+518,814
+229,204
+985,439
+44,534
+48,838
+1258,483
+237,250
+763,852
+1134,117
+857,324
+674,310
+1032,537
+1148,809
+900,623
+549,178
+157,137
+721,247
+244,623
+584,351
+438,518
+527,674
+1292,86
+977,618
+420,667
+1170,812
+445,627
+438,887
+224,814
+1263,197
+738,409
+1262,504
+393,199
+1302,16
+259,50
+934,357
+470,451
+460,414
+552,684
+585,789
+1131,367
+23,346
+1089,245
+827,42
+200,819
+917,666
+1295,807
+58,289
+678,816
+1201,497
+176,320
+269,716
+130,602
+826,854
+758,344
+1009,262
+499,60
+1191,329
+905,453
+1262,761
+180,82
+162,309
+189,658
+547,341
+460,793
+1285,434
+162,809
+189,684
+48,761
+708,147
+378,884
+15,807
+751,395
+1163,831
+708,35
+484,40
+827,597
+1243,789
+15,620
+281,381
+944,773
+221,875
+1203,456
+1126,3
+1272,325
+137,572
+518,528
+171,297
+1073,644
+711,753
+137,836
+902,210
+90,318
+976,532
+185,546
+1272,345
+681,465
+796,82
+826,317
+208,628
+1255,680
+77,665
+1183,526
+181,647
+857,570
+290,884
+294,406
+974,767
+974,575
+596,381
+1148,757
+1164,28
+1215,340
+850,190
+89,740
+661,651
+1310,75
+893,602
+999,870
+1113,379
+1300,135
+925,551
+596,737
+770,404
+662,653
+184,136
+6,294
+930,483
+713,579
+803,24
+763,135
+585,105
+694,325
+179,611
+699,278
+82,572
+147,831
+661,549
+18,361
+1164,448
+976,362
+1205,492
+663,54
+912,127
+1240,44
+813,345
+740,243
+1014,10
+530,121
+1222,308
+218,702
+710,341
+1057,250
+0,317
+961,124
+57,271
+585,278
+1190,627
+671,172
+716,579
+1081,432
+782,422
+179,472
+1101,388
+263,597
+1226,651
+982,458
+796,760
+467,579
+1146,663
+1228,322
+914,217
+382,894
+872,518
+363,99
+209,53
+1148,585
+475,646
+38,345
+458,852
+319,278
+200,747
+1141,662
+648,241
+140,642
+887,453
+120,179
+623,679
+1283,539
+508,28
+383,5
+1170,642
+716,331
+420,543
+262,807
+237,154
+927,835
+857,122
+1019,795
+753,652
+518,808
+140,700
+996,789
+719,149
+127,220
+890,799
+768,393
+253,250
+1091,365
+1036,707
+45,211
+1079,117
+57,789
+845,98
+977,326
+751,843
+320,824
+397,434
+140,194
+448,235
+1146,585
+60,255
+1251,605
+594,331
+597,346
+1213,652
+1111,273
+82,85
+619,289
+89,74
+1021,558
+18,808
+376,357
+415,815
+137,711
+647,54
+619,605
+1061,441
+425,690
+905,217
+216,875
+555,73
+671,807
+1310,317
+1273,425
+1136,494
+1200,824
+527,560
+1258,259
+775,329
+1101,53
+288,325
+206,101
+67,423
+473,602
+806,768
+1221,740
+699,502
+453,122
+1279,175
+557,320
+877,649
+251,619
+474,84
+1203,553
+217,688
+1130,476
+557,126
+214,477
+293,449
+714,157
+749,117
+549,850
+333,774
+925,445
+600,362
+1305,91
+934,628
+326,877
+1192,259
+582,576
+68,117
+301,499
+596,157
+883,796
+599,889
+766,287
+982,595
+468,312
+430,219
+1041,716
+649,243
+1116,345
+768,865
+412,355
+1052,105
+1198,571
+497,773
+1081,14
+1084,309
+293,445
+542,865
+1119,86
+930,747
+716,315
+1034,10
+1278,406
+934,852
+514,760
+164,232
+497,809
+1155,644
+1304,294
+1173,15
+600,782
+187,281
+852,42
+1056,352
+763,589
+185,98
+80,747
+1238,318
+140,252
+818,679
+80,658
+499,698
+95,51
+320,70
+984,877
+318,319
+234,227
+421,777
+187,21
+60,563
+1057,644
+395,641
+403,171
+458,70
+445,659
+597,623
+60,479
+37,105
+820,309
+32,392
+1086,366
+353,744
+82,124
+507,24
+474,866
+1079,441
+273,194
+1170,252
+416,572
+326,429
+1052,329
+562,239
+689,841
+591,149
+1089,651
+826,488
+274,383
+959,469
+1292,310
+719,597
+990,308
+673,471
+686,10
+1102,259
+1208,326
+17,23
+761,626
+1166,422
+328,884
+278,852
+1241,278
+263,37
+244,53
+843,579
+990,362
+755,423
+446,259
+335,610
+393,703
+1108,569
+836,84
+170,742
+765,170
+970,105
+465,658
+714,737
+763,813
+303,469
+992,575
+1145,567
+10,135
+12,264
+792,534
+810,575
+209,235
+52,35
+537,627
+1123,281
+517,183
+1033,208
+343,696
+1245,275
+991,616
+596,605
+1228,533
+656,436
+950,831
+880,770
+781,234
+1153,549
+1130,364
+380,595
+365,660
+185,12
+474,810
+547,852
+726,351
+639,172
+334,756
+69,168
+1304,742
+1184,422
+231,453
+1213,242
+856,299
+288,569
+636,584
+1104,101
+835,611
+1081,515
+1241,504
+1153,773
+156,40
+662,488
+544,287
+1310,10
+1153,345
+137,183
+1163,876
+1121,731
+518,360
+473,647
+1255,214
+242,355
+970,341
+333,618
+180,250
+716,663
+380,511
+776,627
+380,747
+802,0
+1295,620
+925,343
+636,86
+246,7
+874,362
+333,887
+75,198
+261,666
+793,836
+827,149
+130,292
+1146,309
+793,711
+974,127
+1134,544
+796,812
+989,618
+430,80
+497,85
+1009,150
+80,595
+343,847
+740,651
+629,520
+1163,422
+363,347
+984,429
+1253,579
+341,498
+435,789
+1207,294
+492,348
+127,674
+549,47
+661,354
+622,502
+759,294
+930,595
+1218,655
+144,757
+910,749
+1203,135
+796,816
+1253,693
+693,336
+874,282
+649,578
+334,653
+380,63
+656,765
+560,553
+457,1
+237,644
+984,884
+542,323
+55,589
+770,40
+512,218
+112,393
+1036,187
+219,38
+837,247
+360,392
+1253,5
+808,46
+631,346
+782,248
+37,10
+301,262
+87,463
+781,525
+803,831
+179,367
+229,880
+1004,442
+1126,891
+147,63
+381,418
+32,502
+483,490
+954,518
+1084,361
+52,427
+545,497
+408,371
+827,404
+1211,423
+528,248
+135,497
+436,362
+52,707
+713,623
+462,824
+1285,15
+187,613
+825,578
+130,490
+495,441
+237,602
+508,194
+393,666
+1037,476
+1121,796
+1036,511
+1193,625
+982,884
+1064,147
+725,12
+291,617
+919,597
+108,560
+328,877
+403,723
+484,294
+627,355
+763,81
+109,2
+691,289
+453,570
+190,814
+271,232
+1278,488
+907,171
+1015,231
+945,201
+1221,74
+1086,120
+254,542
+1081,686
+826,294
+393,695
+504,126
+836,810
+1130,530
+749,329
+5,540
+1267,145
+1125,546
+766,824
+572,389
+1295,422
+1051,844
+88,124
+1230,595
+890,95
+169,680
+164,214
+1094,7
+930,35
+1094,831
+813,773
+753,320
+525,515
+290,635
+25,744
+629,15
+1076,799
+1089,875
+1173,711
+880,124
+181,602
+103,294
+930,299
+542,193
+95,395
+0,877
+340,630
+599,441
+864,259
+1129,602
+364,187
+890,667
+929,220
+865,501
+1202,84
+877,243
+18,533
+792,814
+1272,569
+873,276
+155,834
+853,1
+1148,886
+764,670
+1230,236
+585,385
+108,670
+1088,605
+436,702
+818,546
+15,870
+551,294
+410,299
+810,319
+1081,242
+975,610
+1066,361
+333,467
+1215,395
+432,289
+408,147
+639,807
+305,124
+152,232
+602,187
+1053,49
+244,85
+191,86
+1096,234
+82,147
+782,646
+1081,208
+852,852
+928,58
+43,278
+57,665
+1217,609
+437,838
+462,376
+525,893
+524,292
+738,837
+52,187
+872,159
+261,247
+873,504
+169,662
+1129,647
+385,178
+200,595
+562,655
+249,453
+1262,56
+103,600
+278,357
+930,147
+229,275
+48,504
+229,462
+547,135
+1089,467
+761,492
+15,274
+1228,847
+383,423
+609,795
+880,568
+811,250
+888,399
+927,59
+1139,597
+192,518
+977,887
+483,404
+1037,504
+1253,229
+448,101
+522,380
+545,728
+95,340
+864,266
+1292,808
+142,676
+1215,843
+401,708
+880,331
+162,886
+967,422
+1175,497
+157,533
+1295,274
+48,56
+547,813
+898,539
+1126,443
+932,458
+1059,619
+184,539
+547,387
+274,411
+925,178
+484,317
+589,320
+589,23
+915,105
+1171,794
+459,684
+1245,890
+217,618
+828,15
+57,5
+469,546
+967,696
+674,533
+475,395
+361,561
+165,567
+699,33
+676,4
+761,268
+863,257
+200,75
+396,217
+470,193
+929,418
+124,345
+162,585
+60,639
+376,728
+43,145
+37,425
+751,106
+318,767
+570,243
+656,129
+508,0
+528,24
+80,819
+555,471
+1036,383
+1027,705
+599,141
+195,210
+157,361
+586,105
+364,707
+1305,757
+1072,348
+711,305
+959,91
+381,674
+1015,679
+311,198
+222,605
+528,870
+1180,602
+1165,740
+499,834
+229,242
+1037,838
+1118,824
+1064,684
+679,133
+1285,744
+192,376
+196,70
+710,500
+1006,101
+1131,472
+632,78
+1119,808
+902,371
+691,347
+159,5
+378,436
+594,31
+758,568
+962,679
+257,105
+425,652
+328,465
+1020,635
+433,649
+1121,658
+1071,82
+1093,56
+755,471
+761,21
+93,609
+179,646
+100,585
+295,231
+1283,91
+1173,431
+557,652
+396,341
+992,319
+320,308
+1146,231
+216,600
+1258,635
+700,360
+94,341
+913,789
+1068,91
+1250,639
+502,232
+1115,658
+102,98
+1203,507
+1191,565
+401,260
+599,453
+602,147
+60,679
+706,169
+114,854
+1141,680
+360,831
+738,505
+1086,80
+1170,700
+946,707
+1064,7
+126,422
+1004,890
+544,607
+1170,526
+801,824
+117,267
+1267,189
+928,894
+701,795
+865,267
+274,467
+31,719
+43,705
+396,553
+484,630
+758,684
+107,456
+542,501
+365,201
+572,837
+144,137
+333,7
+77,229
+1243,105
+1165,824
+194,414
+333,455
+172,431
+1086,774
+765,497
+1128,86
+328,299
+892,318
+504,768
+545,892
+157,757
+565,74
+753,59
+773,267
+1215,51
+383,59
+710,112
+1235,143
+895,79
+1104,316
+31,175
+517,611
+1203,387
+544,635
+872,887
+1201,28
+1037,390
+460,190
+835,248
+438,691
+677,348
+277,208
+1056,542
+765,688
+985,455
+340,105
+1039,507
+1019,347
+703,88
+88,586
+589,275
+639,759
+1051,50
+1121,684
+23,735
+52,483
+1125,12
+492,585
+840,539
+
+fold along x=655
+fold along y=447
+fold along x=327
+fold along y=223
+fold along x=163
+fold along y=111
+fold along x=81
+fold along y=55
+fold along x=40
+fold along y=27
+fold along y=13
+fold along y=6
diff --git a/day13/main.c b/day13/main.c
@@ -0,0 +1,29 @@
+#include <stdio.h>
+#include <time.h>
+#include <string.h>
+
+void puzzle(const char *filename, long long *res1, long long *res2);
+
+int main(int argc, char *argv[]) {
+ printf("Advent of Code: day 13\n");
+ double time_start = clock();
+
+ if (argc <= 1) {
+ printf("Usage: %s inputfile.txt\n", argv[0]);
+ return -1;
+ }
+
+ const char *filename = argv[1];
+ long long counter1 = -1;
+ long long counter2 = -1;
+
+ puzzle(filename, &counter1, &counter2);
+
+ printf("Puzzle #1: %lld\n", counter1);
+ printf("Puzzle #2: %lld\n", counter2);
+
+ double elapsed = clock() - time_start;
+ printf("Elapsed: %f\n", elapsed / CLOCKS_PER_SEC);
+
+ return 0;
+}
diff --git a/day13/puzzle.c b/day13/puzzle.c
@@ -0,0 +1,191 @@
+#define _DEFAULT_SOURCE
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <strings.h>
+#include <assert.h>
+#include <ctype.h>
+#include <limits.h>
+#include <stdbool.h>
+
+#include "util.h"
+
+#define STR_LEN 128
+
+struct point_t {
+ int x;
+ int y;
+};
+
+struct fold_t {
+ int x;
+ int y;
+};
+
+void parse_point(struct array_t *points, const char *str);
+void parse_fold(struct array_t *folds, const char *str);
+void print_points(struct array_t *points);
+struct point_t flip_point(const struct point_t point, const struct point_t fold);
+void add_point(struct array_t *points, struct point_t point);
+void draw_points(const struct array_t *points);
+
+void puzzle(const char *filename, long long *result1, long long *result2) {
+ FILE *infile = fopen(filename, "r");
+ if (infile == NULL) {
+ fprintf(stderr, "fopen() error: %s\n", strerror(errno));
+ return;
+ }
+
+ char buf[STR_LEN] = {0};
+ unsigned int line_num = 0;
+
+ *result1 = 0;
+ *result2 = 0;
+
+ struct array_t points = { .data = NULL };
+ array_init(&points, sizeof(struct point_t), 10);
+ struct array_t folds = { .data = NULL };
+ array_init(&folds, sizeof(struct fold_t), 10);
+
+ bool folds_started = false;
+ while (fgets(buf, STR_LEN, infile) != NULL) {
+ if (strlen(buf) == 1) {
+ folds_started = true;
+ continue;
+ }
+
+ if (folds_started) {
+ parse_fold(&folds, buf);
+ } else {
+ parse_point(&points, buf);
+ }
+
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+
+ for (size_t f = 0; f < folds.count; ++f) {
+ struct array_t points_folded = { .data = NULL };
+ array_init(&points_folded, sizeof(struct point_t), 10);
+
+ struct point_t fold = ((struct point_t *)folds.data)[f];
+ //printf("fold x: %d, y: %d\n", fold.x, fold.y);
+
+ for (size_t i = 0; i < points.count; ++i) {
+ const struct point_t *data = points.data;
+ add_point(&points_folded, flip_point(data[i], fold));
+ }
+
+ //printf("points: %zu\n", points_folded.count);
+ if (f == 0) {
+ *result1 = points_folded.count;
+ }
+
+ // copy folded points over old ones
+ free(points.data);
+ points.data = points_folded.data;
+ points.cap = points_folded.cap;
+ points.count = points_folded.count;
+ }
+
+ // mutiny! ignoring feof/ferror.
+ fclose(infile);
+}
+
+struct point_t flip_point(const struct point_t point, const struct point_t fold) {
+ struct point_t p1 = point;
+ if (fold.x > 0 && point.x > fold.x) {
+ p1.x = 2 * fold.x - point.x;
+ } else if (fold.y > 0 && point.y > fold.y) {
+ p1.y = 2 * fold.y - point.y;
+ }
+ //printf("%2d,%2d -> %2d,%2d\n", point.x, point.y, p1.x, p1.y);
+ return p1;
+}
+
+void add_point(struct array_t *points, struct point_t point) {
+ assert(points != NULL);
+ struct point_t *data = points->data;
+ for (size_t i = 0; i < points->count; ++i) {
+ if (data[i].x == point.x && data[i].y == point.y) {
+ return;
+ }
+ }
+
+ if (points->count >= points->cap) {
+ array_expand(points);
+ }
+ data = points->data;
+ data[points->count++] = point;
+}
+
+void parse_point(struct array_t *points, const char *str) {
+ assert(points != NULL);
+ assert(str != NULL);
+ char *tmp = strndup(str, STR_LEN);
+ assert(tmp != NULL);
+ char *token = NULL;
+
+ int numbers[2] = {0};
+ int i = 0;
+ while ((token = strsep(&tmp, ",\n")) != NULL) {
+ if (*token != '\0') {
+ assert(i < 2);
+ numbers[i] = atoi(token);
+ ++i;
+ }
+ }
+
+ if (points->count >= points->cap) {
+ array_expand(points);
+ }
+
+ struct point_t *data = points->data;
+ data[points->count++] = (struct point_t){ .x=numbers[0], .y=numbers[1] };
+}
+
+void parse_fold(struct array_t *folds, const char *str) {
+ assert(folds != NULL);
+ assert(str != NULL);
+ char *tmp = strndup(str, STR_LEN);
+ assert(tmp != NULL);
+ char *token = NULL;
+
+ int i = 0;
+ int is_x = -1; // 0 is y, 1 is x
+ struct point_t fold = {0};
+ while ((token = strsep(&tmp, "=\n")) != NULL) {
+ if (*token != '\0') {
+ assert(i < 2);
+ if (is_x == -1) {
+ size_t len = strlen(token);
+ // we're just taking last character and checking if it is 'x'
+ is_x = token[len-1] == 'x';
+ } else if (is_x == 0) {
+ fold.y = atoi(token);
+ } else if (is_x == 1) {
+ fold.x = atoi(token);
+ } else {
+ assert(0 == 1);
+ }
+ ++i;
+ }
+ }
+
+ if (folds->count >= folds->cap) {
+ array_expand(folds);
+ }
+
+ struct point_t *data = folds->data;
+ data[folds->count++] = fold;
+}
+
+void print_points(struct array_t *points) {
+ assert(points != NULL);
+ struct point_t *data = points->data;
+ for (size_t i = 0; i < points->count; ++i) {
+ printf("x: %2d, y: %2d\n", data[i].x, data[i].y);
+ }
+}
diff --git a/day13/test.txt b/day13/test.txt
@@ -0,0 +1,21 @@
+6,10
+0,14
+9,10
+0,3
+10,4
+4,11
+6,0
+6,12
+4,1
+0,13
+10,12
+3,4
+3,0
+8,4
+1,10
+2,14
+8,10
+9,0
+
+fold along y=7
+fold along x=5
