87 lines
1.7 KiB
C
87 lines
1.7 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
unsigned int hash_int(unsigned int key) {
|
|
/* Robert Jenkins' 32 bit Mix Function */
|
|
key += (key << 12);
|
|
key ^= (key >> 22);
|
|
key += (key << 4);
|
|
key ^= (key >> 9);
|
|
key += (key << 10);
|
|
key ^= (key >> 2);
|
|
key += (key << 7);
|
|
key ^= (key >> 12);
|
|
|
|
/* Knuth's Multiplicative Method */
|
|
key = (key >> 3) * 2654435761;
|
|
|
|
return key;
|
|
}
|
|
|
|
#define TABLE_SIZE 16384
|
|
#define BUFFER_SIZE 1024
|
|
|
|
int main(void) {
|
|
FILE *fp = fopen("input", "r");
|
|
|
|
size_t lineCount = 0;
|
|
|
|
char buffer[BUFFER_SIZE] = {0};
|
|
|
|
// get number of lines
|
|
size_t read = 0;
|
|
|
|
while ((read = fread(&buffer, sizeof(char), BUFFER_SIZE, fp))) {
|
|
for (size_t i = 0; i < read; i++) {
|
|
if (buffer[i] == '\n') {
|
|
lineCount++;
|
|
}
|
|
}
|
|
}
|
|
|
|
rewind(fp);
|
|
|
|
// get data from file
|
|
unsigned int *left = malloc((lineCount * 2 + 1) * sizeof(int));
|
|
// haha pointer arithmetic go brrr
|
|
unsigned int *right = left + lineCount;
|
|
|
|
for (size_t i = 0; i < lineCount; i++) {
|
|
unsigned int leftNum, rightNum;
|
|
int numsGot = fscanf(fp, "%u %u\n", &leftNum, &rightNum);
|
|
|
|
if (numsGot == 2) {
|
|
left[i] = leftNum;
|
|
right[i] = rightNum;
|
|
}
|
|
}
|
|
|
|
unsigned int hash_map[TABLE_SIZE] = {0};
|
|
|
|
unsigned sum = 0;
|
|
for (size_t i = 0; i < lineCount; i++) {
|
|
const unsigned int key = hash_int(left[i]) % TABLE_SIZE;
|
|
|
|
if (hash_map[key] == 0) {
|
|
unsigned int similarity_score = 0;
|
|
for (size_t j = 0; j < lineCount; j++) {
|
|
if (left[i] == right[j]) {
|
|
similarity_score++;
|
|
}
|
|
}
|
|
|
|
similarity_score *= left[i];
|
|
|
|
hash_map[key] = similarity_score;
|
|
}
|
|
|
|
sum += hash_map[key];
|
|
}
|
|
|
|
printf("%d\n", sum);
|
|
|
|
free(left);
|
|
fclose(fp);
|
|
|
|
return 0;
|
|
}
|