#include <console.h>
#include <stdio.h>
#include <stdlib.h>

// CONSTANTS

#define MAX_LINE_LENGTH 32
#define MAX_LIST_SIZE 1024

// TYPES

typedef struct {
	long int key;
	int value;
} kv;

// GLOBALS

long int firstList[MAX_LIST_SIZE];
long int secondList[MAX_LIST_SIZE];

kv secondHist[MAX_LIST_SIZE];

// FUNCTIONS

int compare_longs(const void *a, const void *b) {
	long int int_a = *(const long int *)a;
	long int int_b = *(const long int *)b;
	
	if (int_a < int_b) return -1;
	if (int_a > int_b) return 1;
	return 0;
}

int build_histogram(kv hist[], long int arr[], int count) {
	int i = 0;
	int keyCount = 0;
	
	for (i = 0; i < count; i++) {
		long int key = arr[i];
		int histIndex = findHistIndex(hist, keyCount, key);
		
		if (histIndex == -1) {
			histIndex = keyCount;
			keyCount++;
		}
		
		hist[histIndex].key = key;
		hist[histIndex].value++;
	}
	
	return keyCount;
}

int findHistIndex(kv hist[], int count, long int key) {
	int i = 0;
	
	for (i = 0; i < count; i++) {
		if (hist[i].key == key) {
			return i;
		}
	}
	
	return -1;
}
	
void main(int argc, char* argv) {
	//char *filename = "01-input.txt";
	char *filename = "01-example.txt";

	int index = 0;
	long int firstAnswer = 0;
	long int secondAnswer = 0;
	int i = 0;
	int histCount, histIndex;
	
	FILE *file;
	char line[MAX_LINE_LENGTH];
	
	file = fopen(filename, "r");
	if (file == NULL) {
		perror("Error opening file");
		return;
	}
	
	printf("Reading %s... ", filename);
	
	while (fgets(line, sizeof(line), file) != NULL) {
		long int num1, num2;
		if (sscanf(line, "%ld %ld", &num1, &num2) != 2) {
			printf("error parsing line %d", index);
			return;
		}
		
		firstList[index] = num1;
		secondList[index] = num2;
		index++;
	}
	
	fclose(file);
	
	printf("read %d lines\n", index);
	
	// PART 1
	
	printf("Sorting first list...\n");
	qsort(firstList, index, sizeof(long int), compare_longs);
	
	printf("Sorting second list...\n");
	qsort(secondList, index, sizeof(long int), compare_longs);
	
	for (i = 0; i < index; i++) {
		firstAnswer = firstAnswer + abs(firstList[i] - secondList[i]);
	}
	
	// PART 2
	
	printf("Calculating histogram...\n");
	histCount = build_histogram(secondHist, secondList, index);
	
	//for (i = 0; i < histCount; i++) {
	//	printf("%ld => %d\n", secondHist[i].key, secondHist[i].value);
	//}
	
	for (i = 0; i < index; i++) {
		histIndex = findHistIndex(secondHist, histCount, firstList[i]);
		if (histIndex == -1) continue;
		
		secondAnswer += firstList[i] * secondHist[histIndex].value;
	}
	
	printf("Part 1: %ld\n", firstAnswer);
	printf("Part 2: %ld\n", secondAnswer);
}