Advent of Code Day 23 Part 2

aoc.c

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

#define ROOM_A_ENTRANCE 2
#define ROOM_B_ENTRANCE 4
#define ROOM_C_ENTRANCE 6
#define ROOM_D_ENTRANCE 8

typedef struct GameState
{
    char hallway[11];
    char roomA[4];
    char roomB[4];
    char roomC[4];
    char roomD[4];
} GameState;

void initState(GameState *state)
{
    state->roomA[0] = 'D';
    state->roomA[1] = 'D';
    state->roomA[2] = 'D';
    state->roomA[3] = 'B';

    state->roomB[0] = 'A';
    state->roomB[1] = 'C';
    state->roomB[2] = 'B';
    state->roomB[3] = 'A';

    state->roomC[0] = 'B';
    state->roomC[1] = 'B';
    state->roomC[2] = 'A';
    state->roomC[3] = 'D';

    state->roomD[0] = 'C';
    state->roomD[1] = 'A';
    state->roomD[2] = 'C';
    state->roomD[3] = 'C';

    for (int i = 0; i < 11; i++)
    {
        state->hallway[i] = '.';
    }
}

void printState(GameState *state)
{
    printf("#############\n#");
    for (int i = 0; i < 11; i++)
    {
        putchar(state->hallway[i]);
    }
    puts("#");

    printf("###%c#%c#%c#%c###\n", state->roomA[0], state->roomB[0], state->roomC[0], state->roomD[0]);
    for (int i = 1; i < 4; i++)
    {
        printf("  #%c#%c#%c#%c#\n", state->roomA[i], state->roomB[i], state->roomC[i], state->roomD[i]);
    }
    puts("  #########");
}

uint64_t getCost(char c)
{
    switch(c)
    {
        case 'A':
            return 1;
        case 'B':
            return 10;
        case 'C':
            return 100;
        case 'D':
            return 1000;
    }
    printf("Invalid char found: %c\n", c);
    return 0;
}

bool pathIsFree(int start, int dest, GameState *state)
{
    for (int i = start + 1; i < dest; i++)
    {
        if (state->hallway[i] != '.')
        {
            return false;
        }
    }
    for (int i = start - 1; i > dest; i--)
    {
        if (state->hallway[i] != '.')
        {
            return false;
        }
    }
    return true;
}

bool everyoneInRoom(GameState *state)
{
    for (int i = 0; i < 4; i++)
    {
        if (state->roomA[i] != 'A' || state->roomB[i] != 'B' || state->roomC[i] != 'C' || state->roomD[i] != 'D')
        {
            return false;
        }
    }
    return true;
}

uint64_t doThing(GameState *state, uint64_t costSoFar)
{
    if (everyoneInRoom(state))
    {
        return costSoFar;
    }
    uint64_t lowestCost = UINT64_MAX;
    int roomAPosition = -1;
    int roomBPosition = -1;
    int roomCPosition = -1;
    int roomDPosition = -1;
    for (int i = 3; i >= 0; i--)
    {
        if (state->roomA[i] == '.')
        {
            roomAPosition = i;
            break;
        }
        if (state->roomA[i] != 'A')
        {
            break;
        }
        if (i == 0 && state->roomA[0] == 'A')
        {
            roomAPosition = -2;
        }
    }
    for (int i = 3; i >= 0; i--)
    {
        if (state->roomB[i] == '.')
        {
            roomBPosition = i;
            break;
        }
        if (state->roomB[i] != 'B')
        {
            break;
        }
        if (i == 0 && state->roomB[0] == 'B')
        {
            roomBPosition = -2;
        }
    }
    for (int i = 3; i >= 0; i--)
    {
        if (state->roomC[i] == '.')
        {
            roomCPosition = i;
            break;
        }
        if (state->roomC[i] != 'C')
        {
            break;
        }
        if (i == 0 && state->roomC[0] == 'C')
        {
            roomCPosition = -2;
        }
    }
    for (int i = 3; i >= 0; i--)
    {
        if (state->roomD[i] == '.')
        {
            roomDPosition = i;
            break;
        }
        if (state->roomD[i] != 'D')
        {
            break;
        }
        if (i == 0 && state->roomD[0] == 'D')
        {
            roomDPosition = -2;
        }
    }
    for (int i = 0; i < 11; i++)
    {
        switch(state->hallway[i])
        {
            case 'A':
            {
                if (roomAPosition > -1 && pathIsFree(i, ROOM_A_ENTRANCE, state))
                {
                    uint64_t moveCost = getCost('A');
                    GameState newState = *state;
                    newState.roomA[roomAPosition] = state->hallway[i];
                    newState.hallway[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * abs(ROOM_A_ENTRANCE - i)) + (moveCost * (roomAPosition + 1)));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
            case 'B':
            {
                if (roomBPosition > -1 && pathIsFree(i, ROOM_B_ENTRANCE, state))
                {
                    uint64_t moveCost = getCost('B');
                    GameState newState = *state;
                    newState.roomB[roomBPosition] = state->hallway[i];
                    newState.hallway[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * abs(ROOM_B_ENTRANCE - i)) + (moveCost * (roomBPosition + 1)));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
            case 'C':
            {
                if (roomCPosition > -1 && pathIsFree(i, ROOM_C_ENTRANCE, state))
                {
                    uint64_t moveCost = getCost('C');
                    GameState newState = *state;
                    newState.roomC[roomCPosition] = state->hallway[i];
                    newState.hallway[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * abs(ROOM_C_ENTRANCE - i)) + (moveCost * (roomCPosition + 1)));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
            case 'D':
            {
                if (roomDPosition > -1 && pathIsFree(i, ROOM_D_ENTRANCE, state))
                {
                    uint64_t moveCost = getCost('D');
                    GameState newState = *state;
                    newState.roomD[roomDPosition] = state->hallway[i];
                    newState.hallway[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * abs(ROOM_D_ENTRANCE - i)) + (moveCost * (roomDPosition + 1)));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
        }
    }
    if (roomAPosition == -1)
    {
        for (int i = 0; i < 4; i++)
        {
            if (state->roomA[i] != '.')
            {
                uint64_t moveCost = getCost(state->roomA[i]);
                for (int j = ROOM_A_ENTRANCE - 1; j >= 0; j--)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomA[i];
                    newState.roomA[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_A_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                for (int j = ROOM_A_ENTRANCE + 1; j < 11; j++)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_B_ENTRANCE || j == ROOM_C_ENTRANCE || j == ROOM_D_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomA[i];
                    newState.roomA[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_A_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
        }
    }
    if (roomBPosition == -1)
    {
        for (int i = 0; i < 4; i++)
        {
            if (state->roomB[i] != '.')
            {
                uint64_t moveCost = getCost(state->roomB[i]);
                for (int j = ROOM_B_ENTRANCE - 1; j >= 0; j--)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_A_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomB[i];
                    newState.roomB[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_B_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                for (int j = ROOM_B_ENTRANCE + 1; j < 11; j++)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_C_ENTRANCE || j == ROOM_D_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomB[i];
                    newState.roomB[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_B_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
        }
    }
    if (roomCPosition == -1)
    {
        for (int i = 0; i < 4; i++)
        {
            if (state->roomC[i] != '.')
            {
                uint64_t moveCost = getCost(state->roomC[i]);
                for (int j = ROOM_C_ENTRANCE - 1; j >= 0; j--)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_A_ENTRANCE || j == ROOM_B_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomC[i];
                    newState.roomC[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_C_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                for (int j = ROOM_C_ENTRANCE + 1; j < 11; j++)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_D_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomC[i];
                    newState.roomC[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_C_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
        }
    }
    if (roomDPosition == -1)
    {
        for (int i = 0; i < 4; i++)
        {
            if (state->roomD[i] != '.')
            {
                uint64_t moveCost = getCost(state->roomD[i]);
                for (int j = ROOM_D_ENTRANCE - 1; j >= 0; j--)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    if (j == ROOM_A_ENTRANCE || j == ROOM_B_ENTRANCE || j == ROOM_C_ENTRANCE)
                    {
                        continue;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomD[i];
                    newState.roomD[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_D_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                for (int j = ROOM_D_ENTRANCE + 1; j < 11; j++)
                {
                    if (state->hallway[j] != '.')
                    {
                        break;
                    }
                    GameState newState = *state;
                    newState.hallway[j] = state->roomD[i];
                    newState.roomD[i] = '.';
                    uint64_t cost = doThing(&newState, costSoFar + (moveCost * (i + 1 + abs(ROOM_D_ENTRANCE - j))));
                    if (cost < lowestCost)
                    {
                        lowestCost = cost;
                    }
                }
                break;
            }
        }
    }
    return lowestCost;
}

int main(void)
{
    GameState state;
    initState(&state);
    uint64_t cost = doThing(&state, 0);
    printf("Cost: %lu\n", cost);
    return 0;
}