AdventOfCode C 2024 day 6

#include <stdio.h>
#include <stdbool.h>
#define SIZE 1000
#define POINTS 16900
#define LENGTH 130

struct point_t {
    int x;
    int y;
    int added_blockage;
};
typedef struct point_t Point;
struct encountered_t {
    int x;
    int y;
    enum Direction dir; // Is either 0, 1, 2, or 3. 3 means both directions
};
typedef struct encountered_t Encounter;

enum Direction {
    NONE,
    UP,   // 1
    LEFT, // 2
    UNUSED1,
    DOWN, // 4
    UNUSED2,
    UNUSED3,
    UNUSED4,
    RIGHT // 8
};

enum Direction direction(int dx, int dy) {
    if (dx == 0 && dy == 1) {
        // South
        return 4;
    }
    else if (dx == 0) {
        return 1;
    }
    else if (dx == 1) {
        // Right
        return 8;
    }
    else {
        return 2;
    }
}

bool compPoint(Point* point1, Point* point2) {
    return point1->x == point2->x && point1->y == point2->y;
}
bool compEncounter(Point point1, Encounter* point2) {
    return point1.x == point2->x && point1.y == point2->y;
}

bool in_bounds(int x, int y, int* bounds) {
    return !(x < 0 || y < 0 || x >= bounds[0] || y >= bounds[1]);
}

bool is_occupied(Point* point, Point* garbage, int size) {
    for (size_t i = 0; i < size; i++) {
        if (compPoint(point, garbage + i)) {
            return true;
        }
    }
    return false;
}

void print_map(Encounter* path, Point* garbage, int* bounds, int encounter_size, int garbage_size) {
    // Transform into a list of lists.
    // Then print
    // Set the default
    char items[LENGTH + 1][LENGTH];
    for (size_t i = 0; i < LENGTH; i++) {
        for (size_t j = 0; j < LENGTH; j++) {
            items[i][j] = '.';
        }
        items[LENGTH][i] = '\0';
    }
    // Set the path
    for (size_t i = 0; i < encounter_size; i++) {
        Encounter encounter = *(path + i);
        char val = 'E'; // This shouldn't end up
        // if more than 1 flag is set, it's going in multiple directions.
        // Print a pretty +
        int dir = encounter.dir;
        if (dir & 5 && dir & 10) {
            val = '+';
        }
        else if (dir & 1 || dir & 4) {
            val = '|';
        }
        else if (dir & 2 || dir & 8) {
            val = '-';
        }
        items[encounter.y][encounter.x] = val;
    }
    // Set the blockages
    for (size_t i = 0; i < garbage_size; i++) {
        Point point = *(garbage + i);
        if (point.added_blockage == 1) {
            items[point.y][point.x] = 'O';
        }
        else {
            items[point.y][point.x] = '#';
        }
    }
    for (size_t i = 0; i < LENGTH; i++) {
        for (size_t j = 0; j < LENGTH; j++) {
            printf("%c", items[i][j]);
            /* code */
        }
        printf("\n");
    }

}



int parse(FILE* ptr, Point* places, Point* guard, int bounds[2]) {
    int index = 0;
    int y = 0;
    int x = 0;
    int c;
    int val;
    while ((c = fgetc(ptr)) != EOF) {
        if (c == '\n') {
            y++;
            x = -1;
        }
        else if (c == '#') {
            Point point = { x, y,0 };
            *(places + index) = point;
            index++;
        }
        else if (c == '^') {
            Point point = { x, y,0 };
            *guard = point;
        }
        x++;
    }
    bounds[0] = x;
    bounds[1] = y;
    return index;
}


int part_one(Point* guard, Point places[SIZE], int* bounds, int size) {
    Point locations[POINTS];
    int index = 0;
    int dx = 0;
    int dy = -1;
    int x = guard->x;
    int y = guard->y;
    // Rotating clockwise means dx, dy = -dy, dx
    while (in_bounds(x, y, bounds)) {
        Point new_loc = { x + dx, y + dy,0 };
        if (is_occupied(&new_loc, places, size)) {
            int temp = dx;
            dx = -dy;
            dy = temp;
        }
        else {
            x += dx;
            y += dy;
            bool found = false;
            for (size_t i = 0; i < index; i++) {
                if (compPoint(&new_loc, locations + i)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                locations[index] = new_loc;
                index++;
            }
        }
    }
    return index;
}


int detect_previous(Encounter* locations, int index, Point point, enum Direction dir) {
    //printf("Need to look through %d locations for place %d,%d\n", index, point.x, point.y);
    for (size_t i = 0; i < index; i++) {
        if (compEncounter(point, locations + i)) {
            int val = locations[i].dir;
            if (val & dir) {
                // We already went in this direction
                return 3;
            }
            locations[i].dir |= dir; // If turning, always ends up a crossing
            return 1;
        }
    }
    return 0;
}

bool detect_loop(Point* guard, Point places[SIZE], int* bounds, int size) {
    // We will record where it's been.
    // Then for all locations it's been, we try and add to places.
    // Then we do cycle detection, aka if it goes over a place twice in the same direction
    Encounter locations[POINTS];
    int index = 0;
    int dx = 0;
    int dy = -1;
    int x = guard->x;
    int y = guard->y;
    // Rotating clockwise means dx, dy = -dy, dx
    while (in_bounds(x, y, bounds)) {
        Point new_loc = { x + dx, y + dy ,0 };
        if (is_occupied(&new_loc, places, size)) {
            int temp = dx;
            dx = -dy;
            dy = temp;
            Point old_loc = { x,y,0 };
            if (detect_previous(locations, index, old_loc, direction(dx, dy)) == 3) {
                //print_map(locations, places, bounds, index, size);
                //printf("\n");
                return true;
            }
        }
        else {
            x += dx;
            y += dy;
            int found = detect_previous(locations, index, new_loc, direction(dx, dy));
            if (!found) {
                // Need to make a new copy
                Encounter point = { x , y , direction(dx,dy) };
                locations[index] = point;
                index++;
            }
        }
    }
    return false;
}
int get_path(Encounter* locations, Point* guard, Point places[SIZE], int* bounds, int size) {
    // We will record where it's been.
    // Then for all locations it's been, we try and add to places.
    // Then we do cycle detection, aka if it goes over a place twice in the same direction
    int index = 0;
    int dx = 0;
    int dy = -1;
    int x = guard->x;
    int y = guard->y;
    // Rotating clockwise means dx, dy = -dy, dx
    while (in_bounds(x, y, bounds)) {
        Point new_loc = { x + dx, y + dy,0 };
        if (is_occupied(&new_loc, places, size)) {
            int temp = dx;
            dx = -dy;
            dy = temp;
            Point old_loc = { x,y,0 };
            detect_previous(locations, index, old_loc, direction(dx, dy));
        }
        else {
            x += dx;
            y += dy;
            bool found = detect_previous(locations, index, new_loc, direction(dx, dy));
            if (!found) {
                // Need to make a new copy
                Encounter point = { x , y , direction(dx,dy) };
                locations[index] = point;
                index++;
            }
        }
    }
    print_map(locations, places, bounds, index, size);
    return index;
}

int part_two(Point* guard, Point places[SIZE], int* bounds, int size) {
    // We will record where it's been.
    // Then for all locations it's been, we try and add to places.
    // Then we do cycle detection, aka if it goes over a place twice in the same direction
    Encounter locations[POINTS];
    int index = get_path(locations, guard, places, bounds, size);
    printf("Trying %d blockages\n", index);
    int total = 0;
    for (size_t i = 0; i < index; i++) {
        Encounter encounter = locations[i];
        Point point = { encounter.x,encounter.y, 1 };
        if (compPoint(guard, &point)) {
            continue;
        }
        places[size] = point;
        if (detect_loop(guard, places, bounds, size + 1)) {
            total++;
        }
    }
    return total;
}

int main() {
    Point garbage[SIZE];
    Point guard;
    int bounds[2] = { 0 };

    FILE* file = fopen("2024-6.txt", "r");
    int size = parse(file, garbage, &guard, bounds);
    printf("Parsed\n");
    fclose(file);
    printf("Location: %d, %d\n", guard.x, guard.y);

    printf("Part one: %d\n", part_one(&guard, garbage, bounds, size));
    printf("Location: %d, %d\n", guard.x, guard.y);
    printf("Part two: %d\n", part_two(&guard, garbage, bounds, size));
}