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

typedef struct {
	void *prev;
	void *next;
	int value;
} Node;

Node* assembleRingNodes(int *nodeValues, int len){
	// assemble ring of `struct Node`s
	Node *firstNode = (Node*) malloc(sizeof(Node));
	firstNode->value = nodeValues[0];

	Node *nextNode, *lastNode = firstNode;
	for(int i=1; i<len; i+=1){
		nextNode = (Node*) malloc(sizeof(Node));

		nextNode->value = nodeValues[i];
		nextNode->prev = lastNode;

		lastNode->next = nextNode;

		lastNode = nextNode;
	}

	// connect the last node to the first node, thus forming a ring
	nextNode->next = firstNode;

	return firstNode;
}

int main(){
	// read in challenge input as ASCII codes
	int challengeInputLength;
	int challengeInput[1024];
	unsigned char buffer[1024];
	FILE *fp = fopen("day10challengeinput","rb");
	challengeInputLength = fread(buffer, 1, 1024, fp);
	for(int i=0; i<challengeInputLength; i+=1){
		challengeInput[i] = (int) buffer[i];
	}
	fclose(fp);

	int tailEndLengths[5] = {17, 31, 73, 47, 23};
	for(int i=0; i<5; i+=1){
		challengeInput[challengeInputLength] = tailEndLengths[i];
		challengeInputLength += 1;
	}

	// populate values: 0,1,2,3,4, ... 254,255
	int nodeValues[256];
	for(int i=0; i<256; i+=1) nodeValues[i] = i;

	// create a ring of nodes with the values in nodeValues
	Node *firstNode = assembleRingNodes(&nodeValues[0], sizeof(nodeValues)/sizeof(int));

	// start solving, runs 64 rounds
	int skipSize = 0;
	Node *position = firstNode;

	for(int round = 0; round < 64; round +=1){
		for(int i=0; i<challengeInputLength; i+=1){
			int currentLength = challengeInput[i];

			// collect values for this run
			int collectedValues[currentLength];
			Node *collectionNode = position;
			for(int j=0; j<currentLength; j+=1){
				collectedValues[j] = collectionNode->value;
				collectionNode = collectionNode->next;
			}

			// distribute values in reverse order AND move position forward
			for(int j=currentLength-1; j>=0; j-=1){
				position->value = collectedValues[j];
				position = position->next;
			}

			// move position node forward skip times
			for(int j=0; j<skipSize; j+=1){
				position = position->next;
			}

			// increment skip by 1
			skipSize += 1;
		}
	}

	// populate sparsehash
	unsigned char sparseHash[256];
	position = firstNode;
	for(int i=0; i<256; i+=1){
		sparseHash[i] = (unsigned char) position->value;
		position = position->next;
	}

	// calculate denseHash
	unsigned char denseHash[16] = {0};
	for(int i=0; i<16; i+=1){
		for(int j=0; j<16; j+=1){
			denseHash[i] ^= sparseHash[i*16 + j];
		}
	}

	// print the denseHash
	printf("Dense Hash hex representation: ");
	for(int i=0; i<16; i+=1){
		printf("%02x", denseHash[i]);
	}
	printf("\n");

	return 0;
}