Gothic 1 Remake lockpick solver

gothic-lockpick-solver.cpp

//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
// GOTHIC 1 REMAKE LOCKPICK SOLVER
// Uses bidirectional Dijkstra's algorithm
// This version only optimizes total moves
// Made by Viktor Chlumsky on 2026-07-26

/* EXAMPLE RUN (new camp tavern underwater chest):

Initial positions (0 to 6): 41623
A: -C
B: +A -E
C: +BD -E
D: +E -B
E: -CD
30-step solution: -2E -2A +B -4C +2B +4D +3B -3A -3C +3B -3A

(linkages can also be abbreviated as "c-be" etc.) */

#include <cstdlib>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define LEFTMOST_POSITION 0 // change to 1 to specify initial positions as 1 to 7 instead
#define ONE_WAY_SEARCH 0 // switches to unidirectional Dijkstra

#define MAX_GATES 7

/// Each 3 bits (starting from LSB) represent 1 gate with values 1 to 7 (0 indicates invalid or unset state)
typedef std::uint32_t State;

/// Each 3 bits (starting from LSB) are the delta for each gate, with valid values 0, 1 and 7 (-1)
typedef std::uint32_t Linkage;

/// Least significant bit indicates direction (0 = right, 1 = left), the following bits represent the moved gate, bit 6 = forward move, bit 7 = backward move
typedef std::uint8_t Move;

#define SOLVED_STATE    0b100100100100100100100100100100
#define VALIDATION_BITS 0b001001001001001001001001001001
#define EVEN_GATE_BITS  0b000111000111000111000111000111
#define ODD_GATE_BITS   0b111000111000111000111000111000

#define FORWARD  Move(0b01000000)
#define BACKWARD Move(0b10000000)
#define REVERSAL Move(0b11000001)
#define DIRECTION_BITS Move(FORWARD|BACKWARD)

State initialState;
/// Each gate has two consecutive linkage entries - for positive (even index) and negative (odd index) moves
Linkage linkages[64];
Move stateMap[1<<(3*MAX_GATES)] = { };

std::uint8_t GATES = 0;
State activeGateMask;
State validationMask;

void initializeGateCount(int gates) {
    GATES = gates;
    activeGateMask = (State(1)<<(3*gates))-1;
    validationMask = VALIDATION_BITS&activeGateMask;
}

#define VALIDATE_STATE(state) ((((state)|(state)>>1|(state)>>2)&validationMask) == validationMask)

inline State advanceState(State state, Move move) {
    Linkage linkage = linkages[move&63];
    State evenState = (state&EVEN_GATE_BITS)+(linkage&EVEN_GATE_BITS);
    State oddState = (state&ODD_GATE_BITS)+(linkage&ODD_GATE_BITS);
    state = ((evenState&EVEN_GATE_BITS)|(oddState&ODD_GATE_BITS))&activeGateMask;
    if (!VALIDATE_STATE(state))
        return 0;
    return state;
}

template <Move direction>
inline void searchBranch(std::queue<State> &dstQueue, State initialState, Move move) {
    if (State targetState = advanceState(initialState, move)) {
        Move stateEntry = stateMap[targetState];
    #if ONE_WAY_SEARCH
        if (stateEntry == Move(1))
    #else
        if (stateEntry&(direction^DIRECTION_BITS))
    #endif
            throw move;
        if (!stateEntry) {
            stateMap[targetState] = move;
            dstQueue.push(targetState);
        }
    }
}

template <Move direction>
inline void searchBranches(std::queue<State> &dstQueue, State initialState, Move lastMove) {
    unsigned lastMovedGate = GATES;
    if (lastMove) {
        searchBranch<direction>(dstQueue, initialState, lastMove);
        if (!(lastMove&direction))
            searchBranch<direction>(dstQueue, initialState, lastMove^1);
        lastMovedGate = lastMove>>1&31;
    }
    for (Move move = direction, end = move+2*GATES; move < end; ++move) {
        if ((move>>1&31) != lastMovedGate)
            searchBranch<direction>(dstQueue, initialState, move);
    }
}

std::vector<Move> connectSolution(State middleState, Move middleMove) {
    std::vector<Move> moves;
    State solvedState = SOLVED_STATE&activeGateMask;
    State state = middleState;
    if (middleMove&BACKWARD)
        state = advanceState(state, middleMove);
    while (state != initialState) {
        Move move = stateMap[state];
        moves.push_back(move);
        state = advanceState(state, move^REVERSAL);
    }
    std::reverse(moves.begin(), moves.end());
    state = middleState;
    if (middleMove&BACKWARD)
        moves.push_back(middleMove^REVERSAL);
    else {
        moves.push_back(middleMove);
        state = advanceState(state, middleMove);
    }
    while (state != solvedState) {
        Move forwardMove = stateMap[state]^REVERSAL;
        moves.push_back(forwardMove);
        state = advanceState(state, forwardMove);
    }
    return moves;
}

std::vector<Move> solve() {
    struct {
        std::queue<State> forward, backward;
    } queues[2], *dstQueues, *srcQueues;
    dstQueues = queues+0;
    srcQueues = queues+1;
    State solvedState = SOLVED_STATE&activeGateMask;
    if (initialState != solvedState) {
        stateMap[initialState] = (GATES-1)<<1;
        stateMap[solvedState] = 1;
        dstQueues->forward.push(initialState);
        dstQueues->backward.push(solvedState);
    }
    State curState;
    try {
        while (std::swap(dstQueues, srcQueues), !(srcQueues->forward.empty() && srcQueues->backward.empty())) {
            while (!srcQueues->forward.empty()) {
                curState = srcQueues->forward.front();
                srcQueues->forward.pop();
                searchBranches<FORWARD>(dstQueues->forward, curState, stateMap[curState]);
            }
        #if !ONE_WAY_SEARCH
            while (!srcQueues->backward.empty()) {
                curState = srcQueues->backward.front();
                srcQueues->backward.pop();
                searchBranches<BACKWARD>(dstQueues->backward, curState, stateMap[curState]);
            }
        #endif
        }
    } catch (Move finalMove) {
        return connectSolution(curState, finalMove);
    }
    return std::vector<Move>();
}

bool verifySolution(const std::vector<Move> &solution) {
    State state = initialState;
    for (Move move : solution)
        state = advanceState(state, move);
    return state == (SOLVED_STATE&activeGateMask);
}

bool parseInitialState() {
    initialState = 0;
    char c;
    bool minus = false;
    int i = 0;
    State pos;
    while ((c = getchar()) != '\n') {
        switch (c) {
            case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
                pos = c-'0'-LEFTMOST_POSITION;
                if (i >= MAX_GATES || pos >= 7)
                    return false;
                initialState |= (pos+1)<<(3*i++);
        }
    }
    if (i <= 0)
        return false;
    initializeGateCount(i);
    return true;
}

bool parseLinkage(int i) {
    std::uint32_t mask = 0b111u<<(3*i);
    linkages[2*i+0] = 0b001u<<(3*i);
    linkages[2*i+1] = 0b111u<<(3*i);
    char c;
    bool minus = false;
    while ((c = getchar()) != '\n') {
        switch (c) {
            case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': case 'H': case 'I': case 'J':
                if (c-'A' >= GATES)
                    return false;
                linkages[2*i+0] |= (minus ? 0b111u : 0b001u)<<(3*(c-'A'));
                linkages[2*i+1] |= (minus ? 0b001u : 0b111u)<<(3*(c-'A'));
                break;
            case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j':
                if (c-'a' >= GATES)
                    return false;
                linkages[2*i+0] |= (minus ? 0b111u : 0b001u)<<(3*(c-'a'));
                linkages[2*i+1] |= (minus ? 0b001u : 0b111u)<<(3*(c-'a'));
                break;
            case '+':
                minus = false;
                break;
            case '-':
                minus = true;
                break;
        }
    }
    return (linkages[2*i+0]&mask) == (0b001u<<(3*i)) && (linkages[2*i+1]&mask) == (0b111u<<(3*i));
}

int main() {
    printf("Initial positions (%d to %d): ", LEFTMOST_POSITION, LEFTMOST_POSITION+6);
    if (!parseInitialState()) {
        fputs("Input error\n", stderr);
        return -1;
    }
    for (int i = 0; i < GATES; ++i) {
        printf("%c: ", char('A'+i));
        if (!parseLinkage(i)) {
            fputs("Input error\n", stderr);
            return -1;
        }
    }
    std::vector<Move> solution(solve());
    if (solution.empty()) {
        if (initialState == (SOLVED_STATE&activeGateMask))
            puts("Already solved");
        else
            puts("Solution not found");
    } else {
        if (!verifySolution(solution))
            return -1;
        printf("%d-step solution:", int(solution.size()));
        #ifdef WITHOUT_MULTIPLES
            for (Move move : solution)
                printf(" %c%c", move&1 ? '+' : '-', char('A'+(move>>1&31)));
        #else
            Move *move = solution.data(), *end = move+solution.size();
            while (move < end) {
                int multiplier = 1;
                while (move+1 < end && move[0] == move[1])
                    ++multiplier, ++move;
                if (multiplier != 1)
                    printf(" %c%d%c", *move&1 ? '+' : '-', multiplier, char('A'+(*move>>1&31)));
                else
                    printf(" %c%c", *move&1 ? '+' : '-', char('A'+(*move>>1&31)));
                ++move;
            }
        #endif
    }
    return 0;
}