advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs | README | LICENSE

puzzle_brute.c (1506B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <errno.h>
      6 #include <string.h>
      7 #include <strings.h>
      8 #include <stdbool.h>
      9 #include <assert.h>
     10 #include <time.h>
     11 #include <math.h>
     12 #include <limits.h>
     13 
     14 #include "util.h"
     15 
     16 #define STR_LEN 16384
     17 
     18 static int compare(const void *l, const void *r) {
     19 	return *(long long *)l - *(long long *)r;
     20 }
     21 
     22 void puzzle_brute(const char *filename, size_t *result1, size_t *result2) {
     23 	FILE *infile = fopen(filename, "r");
     24 	if (infile == NULL) {
     25 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     26 		return;
     27 	}
     28 
     29 	char buf[STR_LEN] = {0};
     30 	unsigned int line_num = 0;
     31 
     32 	struct array_t numbers = { .data = NULL };
     33 	array_init(&numbers, sizeof(long long), 100);
     34 
     35 	while (fgets(buf, STR_LEN, infile) != NULL) {
     36 		parse_numbers_array_ll(&numbers, buf, ",");
     37 		++line_num;
     38 		bzero(buf, STR_LEN);
     39 	}
     40 
     41 	qsort(numbers.data, numbers.count, numbers.elem_size, compare);
     42 
     43 	// median average
     44 	size_t index = numbers.count / 2;
     45 	long long *data = (long long *)numbers.data;
     46 	long long mid = data[index];
     47 	for (size_t i = 0; i < numbers.count; ++i) {
     48 		*result1 += llabs(data[i] - mid);
     49 	}
     50 
     51 	// dumb bruteforcing
     52 	*result2 = ULONG_MAX;
     53 	for (long long i = data[0]; i < data[numbers.count - 1]; ++i) {
     54 		size_t sum = 0;
     55 		for (size_t j = 0; j < numbers.count; ++j) {
     56 			long long dist = llabs(i - data[j]);
     57 			sum += dist * (1 + dist) / 2;
     58 		}
     59 		*result2 = fmin(*result2, (double)sum);
     60 	}
     61 
     62 	// mutiny! ignoring feof/ferror.
     63 	free(numbers.data);
     64 	fclose(infile);
     65 }