原神 3.2 版本 花花琼脂蕈兽培养步数计算

genshin_fungus.py

from copy import deepcopy

IDENTIFIER_BASE = 3


def get_identifier(state):
    identifier = 0
    for line in state:
        for x in line:
            identifier *= IDENTIFIER_BASE
            identifier += x
    return identifier


def get_final_state_identifiers(state):
    result = set()
    for i in range(3):
        state[3][0] = i
        for j in range(3):
            state[3][1] = j
            for k in range(3):
                state[3][2] = k
                result.add(get_identifier(state))
    return result


FINAL_STATE_IDENTIFIERS = get_final_state_identifiers([[0, 0, 0], [1, 1, 1], [2, 2, 2], [0, 0, 0]])


def rotate(state):
    new_states = []
    for i in range(2):
        for j in range(2):
            new_state = deepcopy(state)
            temp = int(new_state[i][j])
            new_state[i][j] = new_state[i + 1][j]
            new_state[i + 1][j] = new_state[i + 1][j + 1]
            new_state[i + 1][j + 1] = new_state[i][j + 1]
            new_state[i][j + 1] = int(temp)
            new_states.append(new_state)
    return new_states


def swap(state):
    new_states = []
    for i in range(3):
        for j in range(2):
            new_state = deepcopy(state)
            new_state[i][j], new_state[i][j + 1] = new_state[i][j + 1], new_state[i][j]
            new_states.append(new_state)
            new_state = deepcopy(state)
            new_state[j][i], new_state[j + 1][i] = new_state[j + 1][i], new_state[j][i]
            new_states.append(new_state)
    return new_states


def paste(state):
    new_states = []
    for i in range(3):
        for j in range(3):
            for ii in range(3):
                for jj in range(3):
                    if state[i][j] != state[ii][jj]:
                        new_state = deepcopy(state)
                        new_state[ii][jj] = new_state[i][j]
                        new_states.append(new_state)
    return new_states


def preset(state, data):
    new_states = []
    i_offset = len(data) - 1
    j_offset = len(data[0]) - 1
    for i in range(3 - i_offset):
        for j in range(3 - j_offset):
            new_state = deepcopy(state)
            for ii in range(i_offset + 1):
                for jj in range(j_offset + 1):
                    new_state[i + ii][j + jj] = data[ii][jj]
            new_states.append(new_state)
    return new_states


def print_state_by_identifier(identifier):
    state = []
    for i in range(12):
        state.append(identifier % IDENTIFIER_BASE)
        identifier //= IDENTIFIER_BASE
    state.reverse()
    print("---")
    for i in range(3):
        print("{}{}{}".format(state[i * 3], state[i * 3 + 1], state[i * 3 + 2]))


def main():
    init_state = [[0, 0, 1], [0, 0, 2], [2, 1, 1], [1, 0, 0]]
    operators = [swap, rotate]
    limited_operators = (
        lambda s: preset(s, [[1], [2]]),
    )

    result = {}
    result[get_identifier(init_state)] = (0, None)
    queue = [init_state]
    final_state_identifier = None
    while len(queue) > 0:
        state = queue.pop(0)
        identifier = get_identifier(state)
        step = result[identifier][0]
        all_new_states = []
        for op in operators:
            all_new_states += op(state)
        for i in range(3):
            if state[3][i] > 0:
                op = limited_operators[i]
                new_states = op(state)
                for new_state in new_states:
                    new_state[3][i] -= 1
                all_new_states += new_states
        for new_state in all_new_states:
            new_identifier = get_identifier(new_state)
            if new_identifier not in result:
                result[new_identifier] = (step + 1, identifier)
                queue.append(new_state)
                if new_identifier in FINAL_STATE_IDENTIFIERS:
                    final_state_identifier = new_identifier
                    break
        if final_state_identifier is not None:
            break
    if final_state_identifier is None:
        print("No result!")
    else:
        print(f"{result[final_state_identifier][0]} steps in total")
        print("Steps (reversed):")
        while final_state_identifier is not None:
            print_state_by_identifier(final_state_identifier)
            final_state_identifier = result[final_state_identifier][1]


if __name__ == "__main__":
    main()