2
1
Fork 0
aoc2021/19/solution.c

130 lines
4.6 KiB
C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
typedef struct beacon {
int x,y,z;
} beacon;
typedef struct scanner {
int nbeacons, known;
beacon *beacons;
} scanner;
inline static beacon transform(beacon b, int i) {
int x=b.x,y=b.y,z=b.z;
#define r(n,a,b,c) case n: return (beacon){a,b,c}
switch (i) {
r( 0, x, y, z); r( 1, x,-y,-z); r( 2, x, z,-y); r( 3, x,-z, y);
r( 4, y, x,-z); r( 5, y,-x, z); r( 6, y, z, x); r( 7, y,-z,-x);
r( 8, z, x, y); r( 9, z,-x,-y); r(10, z, y,-x); r(11, z,-y, x);
r(12,-x, y,-z); r(13,-x,-y, z); r(14,-x, z, y); r(15,-x,-z,-y);
r(16,-y, x, z); r(17,-y,-x,-z); r(18,-y, z,-x); r(19,-y,-z, x);
r(20,-z, x,-y); r(21,-z,-x, y); r(22,-z, y, x); r(23,-z,-y,-x);
}
return (beacon){0};
}
inline static beacon sub(beacon a, beacon b) {
return (beacon){a.x-b.x, a.y-b.y, a.z-b.z};
}
inline static int manhattan(beacon a, beacon b) {
return abs(a.x-b.x) + abs(a.y-b.y) + abs(a.z-b.z);
}
int main() {
scanner *scanners=NULL;
beacon *known_beacons;
int nscanners, known=1,knownb=0;
getchar();
while(scanf("-- scanner %d ---\n",&nscanners)==1) {
nscanners++;
scanners=realloc(scanners,nscanners*sizeof(scanner));
scanner *s = &scanners[nscanners-1];
s->beacons=NULL;
s->nbeacons=1;
s->known=nscanners==1;
beacon b;
while(scanf("%i,%i,%i",&b.x,&b.y,&b.z)==3) {
s->beacons=realloc(s->beacons,++s->nbeacons*sizeof(beacon));
s->beacons[s->nbeacons-1]=b;
knownb++;
}
memset(&s->beacons[0],0,sizeof(beacon));
scanf("%*[^-]");
}
known_beacons = malloc(knownb*sizeof(beacon));
knownb = scanners[0].nbeacons;
memcpy(known_beacons, scanners[0].beacons, knownb*sizeof(beacon));
while (known<nscanners) {
#pragma omp parallel for schedule(dynamic,10) collapse(2)
for (int i=0;i<nscanners;i++) {
for (int m=0;m<24;m++) {
if (scanners[i].known) continue;
for(int kb=0; kb<knownb; kb++) {
for(int tp=1;tp<scanners[i].nbeacons;tp++) {
int candidates=0;
beacon disp = sub(transform(scanners[i].beacons[tp],m), known_beacons[kb]);
for (int dp=1;dp<scanners[i].nbeacons;dp++) {
beacon c = sub(transform(scanners[i].beacons[dp],m),disp);
for (int ckb=0;ckb<knownb;ckb++) {
if (!memcmp(&c, &known_beacons[ckb], sizeof(beacon))){
candidates++;
if (candidates >= 12) {
#pragma omp critical
{
beacon tmp[scanners[i].nbeacons-1];
int ntmp=0;
for (int kdp=1;kdp<scanners[i].nbeacons;kdp++) {
beacon t = sub(transform(scanners[i].beacons[kdp],m),disp);
int found=0;
for (int kdc=0;kdc<knownb;kdc++)
if (!memcmp(&t, &known_beacons[kdc],sizeof(beacon))) {
found++;break;
}
if (!found)
tmp[ntmp++] = t;
}
memcpy(known_beacons+knownb,tmp,ntmp*sizeof(beacon));
knownb+=ntmp;
scanners[i].beacons[0] = (beacon){-disp.x,-disp.y,-disp.z};
scanners[i].known=1;
known++;
printf("%d/%d\n",known,nscanners);
}
goto next;
}
}
}
}
}
}
next:
}
}
}
printf("Silver: %d\n",knownb-1);
int G=0;
for(int i=0;i<nscanners;i++){
for(int j=0;j<nscanners;j++) {
int m = manhattan(scanners[i].beacons[0],scanners[j].beacons[0]);
if (m > G) G=m;
}
}
printf("Gold: %d\n",G);
for(int i=0;i<nscanners;i++)
free(scanners[i].beacons);
free(scanners);
free(known_beacons);
}