adventofcode2022/day16/pressure.c

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

#define BUFFER_SIZE 128
#define MAX_TUNNELS 16
#define MAX_VALVES 128
#define MAX_TIME 30

typedef struct valve {
    char name[2];
    int ppm;
    char nextValveNames[16][2];
    struct valve **nextValves;
    int valve_count;
} VALVE;

unsigned findBestPPM(VALVE, int, unsigned, VALVE*, int, VALVE*, int);

unsigned bestMax = 0;
int bestPpm = 0;

int solution[6][3] = {
    {'D', 'D', 29},
    {'B', 'B', 26},
    {'J', 'J', 22},
    {'H', 'H', 15},
    {'E', 'E', 11},
    {'C', 'C', 7},
};

int main() {
    char buf[BUFFER_SIZE], *p, c;
    memset(buf, 0, BUFFER_SIZE);
    p = buf;
    VALVE valves[MAX_VALVES], curr;
    int valve_count = 0;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c == '\n') {
            p = buf;
            memset(&curr, 0, sizeof(VALVE));
            sscanf(p, "Valve %c%c has flow rate=%i; tunnels lead to valve", &curr.name[0], &curr.name[1], &curr.ppm);
            if (curr.ppm > bestPpm) {
                bestPpm = curr.ppm;
            }
            while(*p++ != 'v') {}
            while(*p++ != 'v') {}
            while(*p++ != ' ') {}
            while(*p != 0) {
                sscanf(p, "%c%c", &curr.nextValveNames[curr.valve_count][0], &curr.nextValveNames[curr.valve_count][1]);
                curr.valve_count++;
                while(*p != ',' && *p != 0) p++;
                if (*p == ',') p+=2;
            }
            curr.nextValves = (VALVE**)malloc(curr.valve_count * sizeof(VALVE*));
            memset(curr.nextValves, 0, curr.valve_count * sizeof(VALVE*));
            valves[valve_count] = curr;
            valve_count++;
            memset(buf, 0, BUFFER_SIZE);
            p = buf;
        }
    }

    // Create pointers instead of names
    for (int i = 0; i < valve_count; i++) {
        for (int j = 0; j < valves[i].valve_count; j++) {
            for (int k = 0; k < valve_count; k++) {
                if (valves[k].name[0] == valves[i].nextValveNames[j][0] && valves[k].name[1] == valves[i].nextValveNames[j][1]) {
                    valves[i].nextValves[j] = &valves[k];
                    break;
                }
            }
        }
    }

    // Find the starting point 'AA'
    for (int i = 0; i < valve_count; i++) {
        if (valves[i].name[0] == 'A' && valves[i].name[1] == 'A') {
            curr = valves[i];
            break;
        }
    }

    VALVE *opened = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
    memset(opened, 0, MAX_TIME * sizeof(VALVE));
    VALVE *walked = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
    memset(walked, 0, MAX_TIME * sizeof(VALVE));
    printf("%u\n", findBestPPM(curr, MAX_TIME, 0, opened, 0, walked, 0));
    free(opened);
    free(walked);
    for (int i = 0; i < valve_count; i++) {
        free(valves[i].nextValves);
    }
}

unsigned findBestPPM(VALVE valve, int time, unsigned sum, VALVE* opened, int opened_count, VALVE* walked, int walk_length) {
    unsigned max = 0, tmp = 0;
    if (time <= 0) {
        return sum;
    }

    for (int i = 1; i < time; i++) {
        tmp += bestPpm * (time - i);
    }
    // If we have no chance of beating the highScore, just skip
    if (bestMax > sum + tmp) {
        return sum;
    }
    tmp = 0;

    VALVE walked_copy[MAX_TIME];
    for (int i = 0; i < MAX_TIME; i++) {
        walked_copy[i] = walked[i];
    }
 
    // Not opening, just running
    // 
    // Shouldn't run in circles
    // Magyarorszag elore megy nem hatra
    for (int i = 0; i < walk_length; i++) {
        if (walked[i].name[0] == valve.name[0] && walked[i].name[1] == valve.name[1]) {
            return sum;
        }
    }
    for (int i = 0; i < valve.valve_count; i++) {
        walked[walk_length] = valve;
        tmp = findBestPPM(*valve.nextValves[i], time - 1, sum, opened, opened_count, walked, walk_length + 1);
        for (int k = 0; k < MAX_TIME; k++) {
            walked[k] = walked_copy[k];
        }
        if (max < tmp) {
            max = tmp;
        }
    }

    // Opening this valve if it was not opened before
    //
    // Only consider this if the flow rate here is > 0
    if (valve.ppm > 0) {
        tmp = 0;
        for (int i = 0; i < opened_count; i++) {
            if (opened[i].name[0] == valve.name[0] && opened[i].name[1] == valve.name[1]) {
                tmp = 1;
                break;
            }
        }
        if (!tmp) {
            unsigned openedPressure = valve.ppm * (time-1);
            for (int i = 0; i < valve.valve_count; i++) {
                opened[opened_count] = valve;
                walked[0] = valve;
                tmp = findBestPPM(*valve.nextValves[i], time - 2, sum + openedPressure, opened, opened_count+1, walked, 1);
                if (max < tmp) {
                    max = tmp;
                }
            }
        }
    }

    if (max > bestMax) {
        bestMax = max;
    }

    return max;
}