Skip to content

Instantly share code, notes, and snippets.

@weirddan455

weirddan455/aoc.c

Created December 20, 2021 02:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save weirddan455/b73cc3018d85412ef59ab56e6ef7bb29 to your computer and use it in GitHub Desktop.
Save weirddan455/b73cc3018d85412ef59ab56e6ef7bb29 to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code Day 19
Raw
aoc.c
#include <fcntl.h>
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
typedef struct Vector
{
int x;
int y;
int z;
} Vector;
typedef struct Scanner
{
int numBeacons;
Vector location;
Vector *beacons;
} Scanner;
bool isNumber(char c)
{
if (c == '-')
{
return true;
}
return c > 47 && c < 58;
}
Vector multiplyVectorMatrix(Vector *vec, int *matrix)
{
Vector result;
result.x = matrix[0] * vec->x + matrix[1] * vec->y + matrix[2] * vec->z;
result.y = matrix[3] * vec->x + matrix[4] * vec->y + matrix[5] * vec->z;
result.z = matrix[6] * vec->x + matrix[7] * vec->y + matrix[8] * vec->z;
return result;
}
Vector subtractVector(Vector *vec1, Vector *vec2)
{
Vector result;
result.x = vec1->x - vec2->x;
result.y = vec1->y - vec2->y;
result.z = vec1->z - vec2->z;
return result;
}
Vector addVector(Vector *vec1, Vector *vec2)
{
Vector result;
result.x = vec1->x + vec2->x;
result.y = vec1->y + vec2->y;
result.z = vec1->z + vec2->z;
return result;
}
void getRotationMatrix(int rotation, int *matrix)
{
switch(rotation)
{
case 0:
{
matrix[0] = 1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 1; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = 1;
break;
}
case 1:
{
matrix[0] = 1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = -1;
matrix[6] = 0; matrix[7] = 1; matrix[8] = 0;
break;
}
case 2:
{
matrix[0] = 1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = -1; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = -1;
break;
}
case 3:
{
matrix[0] = 1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = 1;
matrix[6] = 0; matrix[7] = -1; matrix[8] = 0;
break;
}
case 4:
{
matrix[0] = 0; matrix[1] = -1; matrix[2] = 0;
matrix[3] = 1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = 1;
break;
}
case 5:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = 1;
matrix[3] = 1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 1; matrix[8] = 0;
break;
}
case 6:
{
matrix[0] = 0; matrix[1] = 1; matrix[2] = 0;
matrix[3] = 1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = -1;
break;
}
case 7:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = -1;
matrix[3] = 1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = -1; matrix[8] = 0;
break;
}
case 8:
{
matrix[0] = -1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = -1; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = 1;
break;
}
case 9:
{
matrix[0] = -1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = -1;
matrix[6] = 0; matrix[7] = -1; matrix[8] = 0;
break;
}
case 10:
{
matrix[0] = -1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 1; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = -1;
break;
}
case 11:
{
matrix[0] = -1; matrix[1] = 0; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = 1;
matrix[6] = 0; matrix[7] = 1; matrix[8] = 0;
break;
}
case 12:
{
matrix[0] = 0; matrix[1] = 1; matrix[2] = 0;
matrix[3] = -1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = 1;
break;
}
case 13:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = 1;
matrix[3] = -1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = -1; matrix[8] = 0;
break;
}
case 14:
{
matrix[0] = 0; matrix[1] = -1; matrix[2] = 0;
matrix[3] = -1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 0; matrix[8] = -1;
break;
}
case 15:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = -1;
matrix[3] = -1; matrix[4] = 0; matrix[5] = 0;
matrix[6] = 0; matrix[7] = 1; matrix[8] = 0;
break;
}
case 16:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = -1;
matrix[3] = 0; matrix[4] = 1; matrix[5] = 0;
matrix[6] = 1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 17:
{
matrix[0] = 0; matrix[1] = 1; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = 1;
matrix[6] = 1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 18:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = 1;
matrix[3] = 0; matrix[4] = -1; matrix[5] = 0;
matrix[6] = 1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 19:
{
matrix[0] = 0; matrix[1] = -1; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = -1;
matrix[6] = 1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 20:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = -1;
matrix[3] = 0; matrix[4] = -1; matrix[5] = 0;
matrix[6] = -1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 21:
{
matrix[0] = 0; matrix[1] = -1; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = 1;
matrix[6] = -1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 22:
{
matrix[0] = 0; matrix[1] = 0; matrix[2] = 1;
matrix[3] = 0; matrix[4] = 1; matrix[5] = 0;
matrix[6] = -1; matrix[7] = 0; matrix[8] = 0;
break;
}
case 23:
{
matrix[0] = 0; matrix[1] = 1; matrix[2] = 0;
matrix[3] = 0; matrix[4] = 0; matrix[5] = -1;
matrix[6] = -1; matrix[7] = 0; matrix[8] = 0;
break;
}
}
}
int getMatchingPairs(Vector *v1, int n1, Vector *v2, int n2)
{
int matching = 0;
for (int i = 0; i < n1; i++)
{
for (int j = 0; j < n2; j++)
{
if (v1[i].x == v2[j].x && v1[i].y == v2[j].y && v1[i].z == v2[j].z)
{
matching++;
}
}
}
return matching;
}
void addIfMissing(Vector *v, Scanner *composite)
{
for (int i = 0; i < composite->numBeacons; i++)
{
if (composite->beacons[i].x == v->x && composite->beacons[i].y == v->y && composite->beacons[i].z == v->z)
{
return;
}
}
composite->beacons[composite->numBeacons] = *v;
composite->numBeacons++;
}
bool checkOverlap(Scanner *scanner, Scanner *composite)
{
Vector *compositeCopy = malloc(composite->numBeacons * sizeof(Vector));
Vector *scanRotation = malloc(scanner->numBeacons * sizeof(Vector));
Vector *scanTranslation = malloc(scanner->numBeacons * sizeof(Vector));
if (compositeCopy == NULL || scanRotation == NULL || scanTranslation == NULL)
{
puts("malloc failed");
return false;
}
for (int i = 0; i < 24; i++)
{
int matrix[9];
getRotationMatrix(i, matrix);
for (int j = 0; j < scanner->numBeacons; j++)
{
scanRotation[j] = multiplyVectorMatrix(&scanner->beacons[j], matrix);
}
for (int j = 0; j < composite->numBeacons; j++)
{
Vector *compositeRef = &composite->beacons[j];
for (int k = 0; k < composite->numBeacons; k++)
{
compositeCopy[k] = subtractVector(&composite->beacons[k], compositeRef);
}
for (int k = 0; k < scanner->numBeacons; k++)
{
Vector *scanRef = &scanRotation[k];
for (int l = 0; l < scanner->numBeacons; l++)
{
scanTranslation[l] = subtractVector(&scanRotation[l], scanRef);
}
int numPairs = getMatchingPairs(scanTranslation, scanner->numBeacons, compositeCopy, composite->numBeacons);
if (numPairs >= 12)
{
for (int l = 0; l < scanner->numBeacons; l++)
{
Vector absolute = addVector(compositeRef, &scanTranslation[l]);
addIfMissing(&absolute, composite);
}
scanner->location = subtractVector(compositeRef, scanRef);
free(compositeCopy);
free(scanRotation);
free(scanTranslation);
return true;
}
}
}
}
free(compositeCopy);
free(scanRotation);
free(scanTranslation);
return false;
}
int main()
{
int fd = open("input", O_RDONLY);
if (fd == -1)
{
perror("open");
return 1;
}
struct stat fileInfo;
if (fstat(fd, &fileInfo) != 0)
{
perror("fstat");
close(fd);
return 1;
}
char *data = malloc(fileInfo.st_size);
if (data == NULL)
{
puts("malloc failed");
close(fd);
return 1;
}
ssize_t bytesRead = read(fd, data, fileInfo.st_size);
close(fd);
if (bytesRead == -1)
{
perror("read");
free(data);
return 1;
}
if (bytesRead != fileInfo.st_size)
{
printf("Error: read %d bytes. %d expected.\n", bytesRead, fileInfo.st_size);
free(data);
return 1;
}
int numScanners = 0;
for (ssize_t i = 0; i < bytesRead; i++)
{
if (data[i] == '-' && data[i + 1] == '-')
{
numScanners++;
while(data[i] != '\n')
{
i++;
}
}
}
Scanner *scanners = calloc(numScanners, sizeof(Scanner));
if (scanners == NULL)
{
puts("calloc failed");
free(data);
return 1;
}
ssize_t dataIndex = 0;
for (int i = 0; i < numScanners; i++)
{
if (data[dataIndex] == '-' && data[dataIndex + 1] == '-')
{
while (data[dataIndex] != '\n')
{
dataIndex++;
}
dataIndex++;
}
while (isNumber(data[dataIndex]))
{
scanners[i].numBeacons++;
while (data[dataIndex] != '\n')
{
dataIndex++;
}
dataIndex++;
}
dataIndex++;
}
for (int i = 0; i < numScanners; i++)
{
scanners[i].beacons = malloc(scanners[i].numBeacons * sizeof(Vector));
if (scanners[i].beacons == NULL)
{
puts("malloc failed");
free(data);
return 1;
}
}
dataIndex = 0;
for (int i = 0; i < numScanners; i++)
{
if (data[dataIndex] == '-' && data[dataIndex + 1] == '-')
{
while (data[dataIndex] != '\n')
{
dataIndex++;
}
dataIndex++;
}
for (int j = 0; j < scanners[i].numBeacons; j++)
{
char string[8];
int stringIndex = 0;
while (isNumber(data[dataIndex]))
{
string[stringIndex++] = data[dataIndex++];
}
dataIndex++;
string[stringIndex] = 0;
scanners[i].beacons[j].x = atoi(string);
stringIndex = 0;
while (isNumber(data[dataIndex]))
{
string[stringIndex++] = data[dataIndex++];
}
dataIndex++;
string[stringIndex] = 0;
scanners[i].beacons[j].y = atoi(string);
stringIndex = 0;
while (isNumber(data[dataIndex]))
{
string[stringIndex++] = data[dataIndex++];
}
dataIndex++;
string[stringIndex] = 0;
scanners[i].beacons[j].z = atoi(string);
}
dataIndex++;
}
free(data);
int totalBecons = 0;
for (int i = 0; i < numScanners; i++)
{
totalBecons += scanners[i].numBeacons;
}
Scanner composite;
composite.numBeacons = scanners[0].numBeacons;
composite.beacons = malloc(totalBecons * sizeof(Vector));
memcpy(composite.beacons, scanners[0].beacons, scanners[0].numBeacons * sizeof(Vector));
bool foundAll = false;
while (!foundAll)
{
foundAll = true;
for (int i = 1; i < numScanners; i++)
{
if (!checkOverlap(&scanners[i], &composite))
{
foundAll = false;
}
}
}
int largestDistance = 0;
for (int i = 0; i < numScanners; i++)
{
for (int j = 0; j < numScanners; j++)
{
int distance = abs(scanners[i].location.x - scanners[j].location.x) + abs(scanners[i].location.y - scanners[j].location.y) + abs(scanners[i].location.z - scanners[j].location.z);
if (distance > largestDistance)
{
largestDistance = distance;
}
}
}
printf("Num Beacons: %d\n", composite.numBeacons);
printf("Largest Distance: %d\n", largestDistance);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment