adventofcode2022/day18/cubes.c

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

#define BUFFER_SIZE 64
#define MAX_CUBES 4096
#define MAX_SCAN 16*1024

#define diff(a,b) (abs(a-b))

int main() {
    char buf[BUFFER_SIZE], *p, c;
    memset(buf, 0, BUFFER_SIZE);
    p = buf;
    int cubes[MAX_CUBES][3], cubeCount = 0;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c == '\n') {
            sscanf(buf, "%i,%i,%i", &cubes[cubeCount][0], &cubes[cubeCount][1], &cubes[cubeCount][2]);
            cubeCount++;
            memset(buf, 0, BUFFER_SIZE);
            p = buf;
        }
    }

    int matches = 0;

    for (int i = 0; i < cubeCount; i++) {
        matches += 6;
        for (int j = 0; j < cubeCount; j++) {
            if (diff(cubes[i][0],cubes[j][0]) + diff(cubes[i][1], cubes[j][1]) + diff(cubes[i][2], cubes[j][2]) == 1) {
                matches--;
            }
        }
    }

    printf("%i\n", matches);

    int maxX = 0, maxY = 0, maxZ= 0;
    for (int i = 0; i < cubeCount; i++) {
        if (cubes[i][0] > maxX) {
            maxX = cubes[i][0];
        }
        if (cubes[i][1] > maxY) {
            maxY = cubes[i][1];
        }
        if (cubes[i][2] > maxZ) {
            maxZ = cubes[i][2];
        }
    }
    // Create a 3D cubeMap
    int ***cubeMap = (int***)malloc((maxX+3) * sizeof(int**));
    for (int i = 0; i < maxX + 3; i++) {
        cubeMap[i] = (int**)malloc((maxY+3) * sizeof(int*));
        for (int j = 0; j < maxY+3; j++) {
            cubeMap[i][j] = (int*)malloc((maxZ+3) * sizeof(int));
            memset(cubeMap[i][j], 0, (maxZ+3)*sizeof(int));
        }
    }

    // Fill map
    for (int i = 0; i < cubeCount; i++) {
        cubeMap[cubes[i][0]+1][cubes[i][1]+1][cubes[i][2]+1] = 1;
    }

    int sides[6][3] = {
        {1,0,0},
        {-1,0,0},
        {0,1,0},
        {0,-1,0},
        {0,0,1},
        {0,0,-1},
    };
    //Rescan cubes
    matches = 0;
    for (int i = 0; i < cubeCount; i++) {
        matches += 6;
        for (int j = 0; j < 6; j++) {
            if (cubeMap[cubes[i][0]+sides[j][0]+1][cubes[i][1]+sides[j][1]+1][cubes[i][2]+sides[j][2]+1] == 1) {
                matches--;
            } else if (cubeMap[cubes[i][0]+sides[j][0]+1][cubes[i][1]+sides[j][1]+1][cubes[i][2]+sides[j][2]+1] == 2) {
                continue;
            } else {
                // Else check if point 0,0,0 is reachable
                int fifo[MAX_SCAN][3], scanned[MAX_SCAN][3];
                int fifo_count = 0, scanned_count = 0;

                fifo[fifo_count][0] = cubes[i][0]+sides[j][0]+1;
                fifo[fifo_count][1] = cubes[i][1]+sides[j][1]+1;
                fifo[fifo_count][2] = cubes[i][2]+sides[j][2]+1;
                fifo_count++;

                do {
                    scanned[scanned_count][0] = fifo[0][0];
                    scanned[scanned_count][1] = fifo[0][1];
                    scanned[scanned_count][2] = fifo[0][2];
                    scanned_count++;

                    for (int k = 0; k < fifo_count - 1; k++) {
                        fifo[k][0] = fifo[k+1][0];
                        fifo[k][1] = fifo[k+1][1];
                        fifo[k][2] = fifo[k+1][2];
                    }
                    fifo_count--;

                    // Check each side
                    for (int k = 0; k < 6; k++) {
                        int x = scanned[scanned_count-1][0] + sides[k][0];
                        int y = scanned[scanned_count-1][1] + sides[k][1];
                        int z = scanned[scanned_count-1][2] + sides[k][2];

                        if (x < 0 || y < 0 || z < 0 || x > maxX + 2 || y > maxY + 2 || z > maxZ + 2 || cubeMap[x][y][z] == 1) {
                            continue;
                        }

                        if (x == 0 && y == 0 && z == 0) {
                            fifo_count = -1;
                            break;
                        }

                        int toBreak = 0;
                        for (int l = 0; l < scanned_count; l++) {
                            if (scanned[l][0] == x && scanned[l][1] == y && scanned[l][2] == z) {
                                toBreak = 1;
                                break;
                            }
                        }
                        for (int l = 0; l < fifo_count; l++) {
                            if (fifo[l][0] == x && fifo[l][1] == y && fifo[l][2] == z) {
                                toBreak = 1;
                                break;
                            }
                        }
                        if (toBreak) {
                            continue;
                        }
                        fifo[fifo_count][0] = x;
                        fifo[fifo_count][1] = y;
                        fifo[fifo_count][2] = z;
                        fifo_count++;
                    }
                } while(fifo_count > 0);
                if (fifo_count != -1) {
                    matches--;
                    for (int k = 0; k < scanned_count; k++) {
                        cubeMap[scanned[k][0]][scanned[k][1]][scanned[k][2]] = 1;
                    }
                } else {
                    for (int k = 0; k < scanned_count; k++) {
                        cubeMap[scanned[k][0]][scanned[k][1]][scanned[k][2]] = 2;
                    }
                }
            }
        }
    }
    
    printf("%i\n", matches);

    for (int i = 0; i < maxX + 2; i++) {
        for (int j = 0; j < maxY+2; j++) {
            free(cubeMap[i][j]);
        }
        free(cubeMap[i]);
    }
    free(cubeMap);
}