315 lines
12 KiB
C
315 lines
12 KiB
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 26
|
||
|
|
|
||
|
|
typedef struct valve {
|
||
|
|
char name[2];
|
||
|
|
int ppm;
|
||
|
|
char nextValveNames[16][2];
|
||
|
|
struct valve **nextValves;
|
||
|
|
int valve_count;
|
||
|
|
} VALVE;
|
||
|
|
|
||
|
|
unsigned findBestPPM(VALVE, VALVE, int, unsigned, VALVE*, int, VALVE*, int, VALVE*, int, int, int);
|
||
|
|
unsigned bestMax = 0;
|
||
|
|
int bestPpm = 0;
|
||
|
|
|
||
|
|
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(2 * MAX_TIME * sizeof(VALVE));
|
||
|
|
memset(opened, 0, 2 * MAX_TIME * sizeof(VALVE));
|
||
|
|
VALVE *walked = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
|
||
|
|
memset(walked, 0, MAX_TIME * sizeof(VALVE));
|
||
|
|
VALVE *elephantWalked = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
|
||
|
|
memset(elephantWalked, 0, MAX_TIME * sizeof(VALVE));
|
||
|
|
printf("%u\n", findBestPPM(curr, curr, MAX_TIME, 0, opened, 0, walked, 0, elephantWalked, 0, 0, 0));
|
||
|
|
free(opened);
|
||
|
|
free(walked);
|
||
|
|
free(elephantWalked);
|
||
|
|
for (int i = 0; i < valve_count; i++) {
|
||
|
|
free(valves[i].nextValves);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
unsigned findBestPPM(VALVE valve, VALVE elephantValve, int time, unsigned sum, VALVE* opened, int opened_count, VALVE* walked, int walk_length, VALVE* elephantWalked, int elephantWalk_length, int skipNext, int elephantSkipNext) {
|
||
|
|
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];
|
||
|
|
}
|
||
|
|
VALVE elephantWalked_copy[MAX_TIME];
|
||
|
|
for (int i = 0; i < MAX_TIME; i++) {
|
||
|
|
elephantWalked_copy[i] = elephantWalked[i];
|
||
|
|
}
|
||
|
|
|
||
|
|
// 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 < elephantWalk_length; i++) {
|
||
|
|
if (elephantWalked[i].name[0] == elephantValve.name[0] && elephantWalked[i].name[1] == elephantValve.name[1]) {
|
||
|
|
return sum;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
// Both can move
|
||
|
|
if (!skipNext && !elephantSkipNext) {
|
||
|
|
// Not opening, just running on both
|
||
|
|
for (int i = 0; i < valve.valve_count; i++) {
|
||
|
|
for (int j = 0; j < elephantValve.valve_count; j++) {
|
||
|
|
walked[walk_length] = valve;
|
||
|
|
elephantWalked[elephantWalk_length] = elephantValve;
|
||
|
|
tmp = findBestPPM(*valve.nextValves[i], *elephantValve.nextValves[j], time - 1, sum, opened, opened_count, walked, walk_length + 1, elephantWalked, elephantWalk_length + 1, 0, 0);
|
||
|
|
for (int k = 0; k < MAX_TIME; k++) {
|
||
|
|
walked[k] = walked_copy[k];
|
||
|
|
}
|
||
|
|
for (int k = 0; k < MAX_TIME; k++) {
|
||
|
|
elephantWalked[k] = elephantWalked_copy[k];
|
||
|
|
}
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Opening human valve only
|
||
|
|
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;
|
||
|
|
for (int j = 0; j < elephantValve.valve_count; j++) {
|
||
|
|
elephantWalked[elephantWalk_length] = elephantValve;
|
||
|
|
tmp = findBestPPM(*valve.nextValves[i], *elephantValve.nextValves[j], time - 1, sum + openedPressure, opened, opened_count+1, walked, 1, elephantWalked, elephantWalk_length + 1, 1, 0);
|
||
|
|
for (int k = 0; k < MAX_TIME; k++) {
|
||
|
|
elephantWalked[k] = elephantWalked_copy[k];
|
||
|
|
}
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Opening elephantValve only
|
||
|
|
if (elephantValve.ppm > 0) {
|
||
|
|
tmp = 0;
|
||
|
|
for (int i = 0; i < opened_count; i++) {
|
||
|
|
if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
|
||
|
|
tmp = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (!tmp) {
|
||
|
|
unsigned openedPressure = elephantValve.ppm * (time-1);
|
||
|
|
for (int i = 0; i < elephantValve.valve_count; i++) {
|
||
|
|
opened[opened_count] = elephantValve;
|
||
|
|
elephantWalked[0] = elephantValve;
|
||
|
|
for (int j = 0; j < valve.valve_count; j++) {
|
||
|
|
walked[walk_length] = valve;
|
||
|
|
tmp = findBestPPM(*valve.nextValves[j], *elephantValve.nextValves[i], time - 1, sum + openedPressure, opened, opened_count+1, walked, walk_length + 1, elephantWalked, 1, 0, 1);
|
||
|
|
for (int k = 0; k < MAX_TIME; k++) {
|
||
|
|
walked[k] = walked_copy[k];
|
||
|
|
}
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Both opening
|
||
|
|
if (elephantValve.ppm > 0 && valve.ppm > 0 && !(elephantValve.name[0] == valve.name[0] && elephantValve.name[1] == valve.name[1])) {
|
||
|
|
tmp = 0;
|
||
|
|
for (int i = 0; i < opened_count; i++) {
|
||
|
|
if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
|
||
|
|
tmp = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
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 = elephantValve.ppm * (time-1) + valve.ppm * (time-1);
|
||
|
|
opened[opened_count] = elephantValve;
|
||
|
|
opened[opened_count+1] = valve;
|
||
|
|
elephantWalked[0] = elephantValve;
|
||
|
|
walked[0] = valve;
|
||
|
|
for (int i = 0; i < elephantValve.valve_count; i++) {
|
||
|
|
for (int j = 0; j < valve.valve_count; j++) {
|
||
|
|
tmp = findBestPPM(*valve.nextValves[j], *elephantValve.nextValves[i], time - 2, sum + openedPressure, opened, opened_count+2, walked, 1, elephantWalked, 1, 0, 0);
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
} else if (skipNext && !elephantSkipNext) {
|
||
|
|
// Human is opening valve, only elephant has a choice
|
||
|
|
for (int i = 0; i < elephantValve.valve_count; i++) {
|
||
|
|
elephantWalked[elephantWalk_length] = elephantValve;
|
||
|
|
tmp = findBestPPM(valve, *elephantValve.nextValves[i], time - 1, sum, opened, opened_count, walked, walk_length, elephantWalked, elephantWalk_length + 1, 0, 0);
|
||
|
|
for (int k = 0; k < MAX_TIME; k++) {
|
||
|
|
elephantWalked[k] = elephantWalked_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 (elephantValve.ppm > 0) {
|
||
|
|
tmp = 0;
|
||
|
|
for (int i = 0; i < opened_count; i++) {
|
||
|
|
if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
|
||
|
|
tmp = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (!tmp) {
|
||
|
|
unsigned openedPressure = elephantValve.ppm * (time-1);
|
||
|
|
for (int i = 0; i < elephantValve.valve_count; i++) {
|
||
|
|
opened[opened_count] = elephantValve;
|
||
|
|
elephantWalked[0] = elephantValve;
|
||
|
|
tmp = findBestPPM(valve, *elephantValve.nextValves[i], time - 1, sum + openedPressure, opened, opened_count+1, walked, walk_length, elephantWalked, 1, 0, 1);
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
} else if (!skipNext && elephantSkipNext) {
|
||
|
|
// Elephant is opening valve???, only human has a choice
|
||
|
|
for (int i = 0; i < valve.valve_count; i++) {
|
||
|
|
walked[walk_length] = valve;
|
||
|
|
tmp = findBestPPM(*valve.nextValves[i], elephantValve, time - 1, sum, opened, opened_count, walked, walk_length + 1, elephantWalked, elephantWalk_length, 0, 0);
|
||
|
|
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], elephantValve, time - 1, sum + openedPressure, opened, opened_count+1, walked, 1, elephantWalked, elephantWalk_length, 1, 0);
|
||
|
|
if (max < tmp) {
|
||
|
|
max = tmp;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (max > bestMax) {
|
||
|
|
bestMax = max;
|
||
|
|
}
|
||
|
|
return max;
|
||
|
|
}
|