79 lines
1.9 KiB
C
79 lines
1.9 KiB
C
#include <stdio.h>
|
|
#include <stdint.h>
|
|
#include <stdlib.h>
|
|
|
|
#include "puzzle_input.h"
|
|
#include "day.h"
|
|
|
|
#define MAX_POSITIONS 1024
|
|
|
|
//#define DEBUG
|
|
|
|
int int64_t_cmp(const void * a, const void * b) {
|
|
int64_t * a_int = (int64_t *)a;
|
|
int64_t * b_int = (int64_t *)b;
|
|
|
|
return (int)*a_int - (int)*b_int;
|
|
}
|
|
|
|
static int64_t part_1(int64_t *positions, uint16_t len) {
|
|
int64_t median;
|
|
int64_t fuel_cost = 0;
|
|
qsort((void *) positions, len, sizeof(uint64_t), int64_t_cmp);
|
|
median = positions[len/2];
|
|
|
|
for (int pos_ndx = 0; pos_ndx < len; pos_ndx++) {
|
|
fuel_cost += labs(positions[pos_ndx] - median);
|
|
}
|
|
|
|
return fuel_cost;
|
|
}
|
|
|
|
static int64_t part_2(const int64_t *positions, uint16_t len) {
|
|
int64_t max = positions[len-1];
|
|
int64_t min = positions[0];
|
|
int64_t best_pos = INT64_MAX;
|
|
int64_t best_fuel_cost = INT64_MAX;
|
|
|
|
for (int64_t i = min; i <= max; i++) {
|
|
int64_t total_fuel_cost = 0;
|
|
for (int pos_ndx = 0; pos_ndx < len; pos_ndx++) {
|
|
int64_t fuel_cost;
|
|
int64_t distance;
|
|
|
|
distance = labs(i - positions[pos_ndx]);
|
|
fuel_cost = ((distance << 6) * ((1 + distance) << 8)) >> 15;
|
|
|
|
total_fuel_cost += fuel_cost;
|
|
}
|
|
|
|
if (total_fuel_cost < best_fuel_cost) {
|
|
best_fuel_cost = total_fuel_cost;
|
|
best_pos = i;
|
|
}
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
printf("PART 2: Best Pos %ld\n", best_pos);
|
|
#endif
|
|
return best_fuel_cost;
|
|
}
|
|
|
|
int day_7() {
|
|
int64_t positions[MAX_POSITIONS] = {0};
|
|
uint16_t len;
|
|
parse_ret_t res;
|
|
|
|
res = read_input_split_on("../inputs/day_7.txt", (void *)positions, MAX_POSITIONS, parse_long_from_buff, &len, ',');
|
|
|
|
if (res != PARSER_OK) {
|
|
printf("Unable to parse input: %d\n", res);
|
|
return -1;
|
|
}
|
|
|
|
|
|
printf("PART 1: Total fuel cost is %ld\n", part_1(positions, len));
|
|
printf("PART 2: Total fuel cost is %ld\n", part_2(positions, len));
|
|
|
|
return 0;
|
|
} |