commit 611849971270657c9e0a448daa378bde4fd349a2
parent 35af63181a8d7493308737dc0d8a4094a5fc0100
Author: bsandro <[email protected]>
Date: Wed, 8 Dec 2021 00:19:04 +0200
Added day 07 puzzle 2 bruteforce solution
Diffstat:
10 files changed, 168 insertions(+), 99 deletions(-)
diff --git a/common/quicksort.h b/common/quicksort.h
@@ -0,0 +1,30 @@
+#pragma once
+
+/* ******************* quicksort ***********************/
+
+static void qs_swap(int *a, int *b) {
+ int tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+static long long qs_partition(int *numbers, long long low, long long high) {
+ int pivot = numbers[high];
+ long long i = low - 1;
+ for (long long j = low; j <= high - 1; ++j) {
+ if (numbers[j] < pivot) {
+ i++;
+ qs_swap(&numbers[i], &numbers[j]);
+ }
+ }
+ qs_swap(&numbers[i+1], &numbers[high]);
+ return i + 1;
+}
+
+static void qs(int *numbers, long long low, long long high) {
+ if (low < high) {
+ long long p = qs_partition(numbers, low, high);
+ qs(numbers, low, p - 1);
+ qs(numbers, p + 1, high);
+ }
+}
diff --git a/common/util.c b/common/util.c
@@ -0,0 +1,40 @@
+#include <string.h>
+#include <stdlib.h>
+#include "util.h"
+
+void array_init(struct array_t *array, size_t elem_size, size_t cap) {
+ assert(array->data == NULL);
+ array->cap = cap;
+ array->elem_size = elem_size;
+ array->data = calloc(cap, elem_size);
+ assert(array->data != NULL);
+}
+
+void array_expand(struct array_t *array) {
+ size_t new_cap = array->cap * 2;
+ array->data = realloc(array->data, array->elem_size * new_cap);
+ assert(array->data != NULL);
+ array->cap = new_cap;
+}
+
+/* ******************* parse plain numbers array *******************/
+void parse_numbers_array(struct array_t *numbers, const char *str, const char *delim) {
+ assert(numbers != NULL);
+ char *tmp = strndup(str, STR_LEN_LIMIT);
+ char *token = NULL;
+ assert(tmp != NULL);
+
+ while ((token = strsep(&tmp, delim)) != NULL) {
+ int num = atoi(token);
+
+ if (numbers->count >= numbers->cap) {
+ array_expand(numbers);
+ }
+
+ int *data = (int *)numbers->data;
+ data[numbers->count++] = num;
+ }
+
+ free(tmp);
+}
+
diff --git a/common/util.h b/common/util.h
@@ -1,11 +1,15 @@
+#pragma once
+
#include <stdio.h>
#include <assert.h>
+#define STR_LEN_LIMIT 8192
#define PRINT_ERR(func) fprintf(stderr, #func "() error: %s\n", strerror(errno));
#define FMT_(l) #l
#define FMT(l) FMT_(l)
+/* ************** simple arrays **********************/
struct array_t {
void *data;
size_t elem_size;
@@ -23,18 +27,8 @@ struct array_t {
printf("\n"); \
} while (0);
-void array_init(struct array_t *array, size_t elem_size, size_t cap) {
- assert(array->data == NULL);
- array->cap = cap;
- array->elem_size = elem_size;
- array->data = calloc(cap, elem_size);
- assert(array->data != NULL);
-}
-
-void array_expand(struct array_t *array) {
- size_t new_cap = array->cap * 2;
- array->data = realloc(array->data, array->elem_size * new_cap);
- assert(array->data != NULL);
- array->cap = new_cap;
-}
+void array_init(struct array_t *array, size_t elem_size, size_t cap);
+void array_expand(struct array_t *array);
+/* ******************* parse plain numbers array *******************/
+void parse_numbers_array(struct array_t *numbers, const char *str, const char *delim);
diff --git a/day04/Makefile b/day04/Makefile
@@ -1,6 +1,6 @@
NAME=$(shell basename ${PWD})
CC=cc
-SRC=$(wildcard *.c)
+SRC=$(wildcard *.c ../common/*.c)
DEPS:=$(wildcard *.h ../common/*.h)
OBJ:=$(SRC:.c=.o)
diff --git a/day04/puzzle12.c b/day04/puzzle12.c
@@ -22,7 +22,6 @@ struct board_t {
bool won;
};
-void make_numbers_array(struct array_t *numbers, const char *str);
void fill_board(struct board_t *board, int row, const char *str);
int check_board(struct board_t *board, int num);
void print_boards(const struct array_t *boards);
@@ -53,7 +52,7 @@ void puzzle(const char *filename, int *result1, int *result2) {
while (fgets(buf, STR_LEN, infile) != NULL) {
// first line is always random numbers sequence
if (line_num == 0) {
- make_numbers_array(&numbers, buf);
+ parse_numbers_array(&numbers, buf, ",");
} else if (strlen(buf) == 1) { // line sized 1 is a separator before boards
if (boards.count >= boards.cap) {
@@ -150,25 +149,6 @@ void print_boards(const struct array_t *boards) {
}
}
-void make_numbers_array(struct array_t *numbers, const char *str) {
- char *tmp = strndup(str, STR_LEN);
- char *token = NULL;
- assert(tmp != NULL);
-
- while ((token = strsep(&tmp, ",")) != NULL) {
- int num = atoi(token);
-
- if (numbers->count >= numbers->cap) {
- array_expand(numbers);
- }
-
- int *data = (int *)numbers->data;
- data[numbers->count++] = num;
- }
-
- free(tmp);
-}
-
void fill_board(struct board_t *board, int row, const char *str) {
char *tmp = strndup(str, STR_LEN);
assert(tmp != NULL);
diff --git a/day05/Makefile b/day05/Makefile
@@ -1,6 +1,6 @@
NAME=$(shell basename ${PWD})
CC=cc
-SRC=$(wildcard *.c)
+SRC=$(wildcard *.c ../common/*.c)
DEPS:=$(wildcard *.h ../common/*.h)
OBJ:=$(SRC:.c=.o)
diff --git a/day07/Makefile b/day07/Makefile
@@ -1,9 +1,9 @@
NAME=$(shell basename ${PWD})
CC=cc
-SRC=$(wildcard *.c)
+SRC=$(wildcard *.c ../common/*.c)
DEPS:=$(wildcard *.h ../common/*.h)
OBJ:=$(SRC:.c=.o)
-CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common
+CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common
LDFLAGS=-lc -lm
all: $(NAME)
@@ -24,3 +24,6 @@ run: $(NAME)
test: $(NAME)
./$(NAME) test.txt
+
+brute: $(NAME)
+ ./$(NAME) -b input.txt
diff --git a/day07/main.c b/day07/main.c
@@ -1,7 +1,9 @@
#include <stdio.h>
#include <time.h>
+#include <string.h>
void puzzle(const char *filename, size_t *res1, size_t *res2);
+void puzzle_brute(const char *filename, size_t *res1, size_t *res2);
int main(int argc, char *argv[]) {
printf("Advent of Code: day 07\n");
@@ -10,17 +12,30 @@ int main(int argc, char *argv[]) {
if (argc <= 0) {
return -1;
}
- if (argc <= 1) {
+
+ if (argc == 1) {
printf("Usage: %s inputfile.txt\n", argv[0]);
return -1;
}
- const char *filename = argv[1];
+ const char *filename = argv[1]; //NULL;
+ int is_brute = 0;
+
+ if (argc == 2) {
+ filename = argv[1];
+ } else { // > 2
+ is_brute = strlen(argv[1]) == 2 && strncmp(argv[1], "-b", 2) == 0;
+ filename = argv[2];
+ }
size_t counter1 = 0;
size_t counter2 = 0;
- puzzle(filename, &counter1, &counter2);
+ if (is_brute) {
+ puzzle_brute(filename, &counter1, &counter2);
+ } else {
+ puzzle(filename, &counter1, &counter2);
+ }
printf("Puzzle #1: %zu\n", counter1);
printf("Puzzle #2: %zu\n", counter2);
diff --git a/day07/puzzle.c b/day07/puzzle.c
@@ -11,17 +11,10 @@
#include <math.h>
#include "util.h"
+#include "quicksort.h"
#define STR_LEN 16384
-void make_numbers_array(struct array_t *numbers, const char *str);
-
-void qs_swap(int *a, int *b);
-long long qs_partition(int *numbers, long long low, long long high);
-void qs(int *numbers, long long low, long long high);
-
-/* ****************************************************************** */
-
void puzzle(const char *filename, size_t *result1, size_t *result2) {
FILE *infile = fopen(filename, "r");
if (infile == NULL) {
@@ -36,7 +29,7 @@ void puzzle(const char *filename, size_t *result1, size_t *result2) {
array_init(&numbers, sizeof(int), 100);
while (fgets(buf, STR_LEN, infile) != NULL) {
- make_numbers_array(&numbers, buf);
+ parse_numbers_array(&numbers, buf, ",");
++line_num;
bzero(buf, STR_LEN);
}
@@ -66,51 +59,3 @@ void puzzle(const char *filename, size_t *result1, size_t *result2) {
free(numbers.data);
fclose(infile);
}
-
-/* ************************* BOILERPLATE ************************* */
-
-void make_numbers_array(struct array_t *numbers, const char *str) {
- char *tmp = strndup(str, STR_LEN);
- char *token = NULL;
- assert(tmp != NULL);
-
- while ((token = strsep(&tmp, ",")) != NULL) {
- int num = atoi(token);
-
- if (numbers->count >= numbers->cap) {
- array_expand(numbers);
- }
-
- int *data = (int *)numbers->data;
- data[numbers->count++] = num;
- }
-
- free(tmp);
-}
-
-void qs_swap(int *a, int *b) {
- int tmp = *a;
- *a = *b;
- *b = tmp;
-}
-
-long long qs_partition(int *numbers, long long low, long long high) {
- int pivot = numbers[high];
- long long i = low - 1;
- for (long long j = low; j <= high - 1; ++j) {
- if (numbers[j] < pivot) {
- i++;
- qs_swap(&numbers[i], &numbers[j]);
- }
- }
- qs_swap(&numbers[i+1], &numbers[high]);
- return i + 1;
-}
-
-void qs(int *numbers, long long low, long long high) {
- if (low < high) {
- long long p = qs_partition(numbers, low, high);
- qs(numbers, low, p - 1);
- qs(numbers, p + 1, high);
- }
-}
diff --git a/day07/puzzle_brute.c b/day07/puzzle_brute.c
@@ -0,0 +1,62 @@
+#define _DEFAULT_SOURCE
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <strings.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <time.h>
+#include <math.h>
+#include <limits.h>
+
+#include "util.h"
+#include "quicksort.h"
+
+#define STR_LEN 16384
+
+void puzzle_brute(const char *filename, size_t *result1, size_t *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;
+
+ struct array_t numbers = { .data = NULL };
+ array_init(&numbers, sizeof(int), 100);
+
+ while (fgets(buf, STR_LEN, infile) != NULL) {
+ parse_numbers_array(&numbers, buf, ",");
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+
+ qs((int *)numbers.data, 0, numbers.count - 1);
+
+ // median average
+ size_t index = numbers.count / 2;
+ int *data = (int *)numbers.data;
+ int mid = data[index];
+ for (size_t i = 0; i < numbers.count; ++i) {
+ *result1 += abs(data[i] - mid);
+ }
+
+ // dumb bruteforcing
+ *result2 = ULONG_MAX;
+ for (int i = data[0]; i < data[numbers.count - 1]; ++i) {
+ size_t sum = 0;
+ for (size_t j = 0; j < numbers.count; ++j) {
+ int dist = abs(i - data[j]);
+ sum += dist * (1 + dist) / 2;
+ }
+ *result2 = fmin(*result2, (double)sum);
+ }
+
+ // mutiny! ignoring feof/ferror.
+ free(numbers.data);
+ fclose(infile);
+}
