#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "input.h"

#define ABS(x) (x < 0 ? -(x) : x)
#define MIN(x, y) (x < y ? x : y)

#define INPUT "input/07.txt"
#define INPUT_DOMAIN_MAX 2000

#define EXPECTED1 349769L
#define EXPECTED2 99540554L

void part1(struct input_str* input) {
	char* start = input->lines[0];
	char* end = start;
	int sub_count_by_alt[INPUT_DOMAIN_MAX] = { 0 };

	// parse input
	long sub_count = 0;
	while(*end != '\n') {
		long alt = strtol(start, &end, 0);
		start = end;
		if(*end == ',')
			start++;

		sub_count_by_alt[alt]++;
		sub_count++;
	}

	// brute force
	long fuel_min = LONG_MAX;
	for(int a = 0; a < INPUT_DOMAIN_MAX; a++) {
		long current_fuel = 0;
		for(int b = 0; b < INPUT_DOMAIN_MAX; b++) {
			current_fuel += sub_count_by_alt[b] * ABS(b - a);
		}
		fuel_min = MIN(fuel_min, current_fuel);
	}
	
	CHECK(fuel_min, EXPECTED1);
}

long compute_fuel(int distance, long* lookup_table) {
	if(distance <= 0)
		return 0;
	if(lookup_table[distance] != 0)
		return lookup_table[distance];

	lookup_table[distance] = distance + compute_fuel(distance - 1, lookup_table);
	return lookup_table[distance];
}

void part2(struct input_str* input) {
	char* start = input->lines[0];
	char* end = start;
	int sub_count_by_alt[INPUT_DOMAIN_MAX] = { 0 };

	// parse input
	long sub_count = 0;
	while(*end != '\n') {
		long alt = strtol(start, &end, 0);
		start = end;
		if(*end == ',')
			start++;

		sub_count_by_alt[alt]++;
		sub_count++;
	}

	// brute force
	// computing the fuel needed from the distance is costly so we use a lookup table to compute fuel only the first time it's needed for a given distance
	// exec time with lookup table = 0.2s
	// exec time without = 12.7s
	long fuel_min = LONG_MAX;
	long lookup_table[INPUT_DOMAIN_MAX] = { 0 };
	for(int a = 0; a < INPUT_DOMAIN_MAX; a++) {
		long current_fuel = 0;
		for(int b = 0; b < INPUT_DOMAIN_MAX; b++) {
			current_fuel += sub_count_by_alt[b] * compute_fuel(ABS(b - a), lookup_table);
		}
		fuel_min = MIN(fuel_min, current_fuel);
	}
	
	CHECK(fuel_min, EXPECTED2);
}

int main() {
	// read input
	struct input_str input;
	input_str_read(&input, INPUT);

	// do stuff
	part1(&input);
	part2(&input);

	// cleanup & exit
	input_str_free(&input);
	return 0;
}